图图的基本概念

发布网友发布时间：2024-10-06 13:06

共1个回答

热心网友时间：2024-10-08 16:59

图图的基本概念可以被理解为一个有序对 <V, E>，其中 V 是结点集，E 是边集。当 V 和 E 都是有限的，这样的图被称为有限图；反之，若 V 或 E 无限大，则称为无限图。

无向边是与无序结点对 (v, u) 相关联的边，而有向边则与有序结点对相关联。无向图中，每条边都无方向，记作 G = <V, E>；反之，所有边都有方向的图称为有向图，记作 D = <V, E>。混合图则是包含有向边和无向边的图。

平凡图只包含一个结点，零图则是边集为空的图，仅表示结点集合。自回路，即在同一个结点上关联的边，称为环。无向图中，每条边的两个端点连接的是同一条边，称为无向平行边；而在有向图中，如果两个结点之间有多条且方向相同的边，称为有向平行边。简单图不包含这些重复的边和自回路。

在无向图 G = <V, E> 中，一个结点 v (∈ V) 的关联边数称为它的度数，记作 deg(v) 或 d(v)。在有向图中，结点的出度（指向其他结点的边数）和入度（从其他结点指向的边数）之和定义为度数。

有向完全图是指所有 n 个结点间都有两条方向相反的边相连，记作 Kn*，对于无向图，所有结点间都有边相连的无向简单图则称为无向完全图，记作 Kn。生成子图是原图 G = <V, E> 的一部分，如果从 E 中去除某些边，形成的子集 <V, E′ 就是生成子图。补图 G' = <V, E′> 是在 G 中添加边使其成为完全图的图。

最后，两个图 G1 和 G2 如果存在双射函数 f，使得它们的边和结点的关联关系一一对应，并且度数的重数相同，那么我们说这两个图是同构的，记作 G1 ≌ G2。同构的充分条件是存在双射函数，而必要条件包括结点数相同、边数相同以及度数相同的结点个数相同。