图论(1)-图的基本概念
图的基本概念
一个图G是一个二重组 <V,E>, 其中V是非空的节点(vertex)的集合, E是边(edge)的集合.

若边e所对应的偶对<a, b>是有序的, 则称e是有向边。 有向边简称弧, a叫弧e的始点, b叫弧e的终点, 统称为e的端点。

若边e所对应的偶对(a,b)是无序的, 则称e是无向边。

每一条边都是有向边的图称为有向图。

每一条边都是无向边的图称为无向图。

如果在图中一些边是有向边,而另一些边是无向边,则称 这个图是混合图。

关联于同一结点的一条边称为自回路。

两结点间(包括结点自身间)若多于一条边,则称这几条边 为平行边或多重边。

不含自回路和多重边的图称为简单图。

每个顶点与其余顶点均相连的无向简单图，称为无向完全图

具有n (n>=1) 个顶点的无向完全图记作 K n K_nK?
n
?
?。

每对顶点之间均有两条方向相反的有向边的有向简单图，称为有向完全图。

设 G =<V,E> , G 1 G1G1= < V 1 , E 1 > <V1, E1><V1,E1>
(1) 若G ? \subseteq?G ，则称 G1为G的子图，G为G1的母图；
(2) 若G1? \subseteq? G 且V1=V，则称G1为G的生成子图；
(3) 若V1? \subset?V或E1 ? \subset?E，称G1为G的真子图；
(4) V1（V1? \subset?V且V1不为空）的导出子图，记作G[V1]；
(5) E1（E1? \subset?E且E1不为空）的导出子图，记作G[E1]。

设G=<V, E>为n阶无向简单图，以V为顶点集，以所有使G成为完全图k n k_nk?
n
?
?的添加边组成的集合为边集的图， 称为G的补图，记作G ￣ \overline{G}?
G
?。

出度: 在有向图中, 对于任何结点v,以v为始点的边的条数称为结点v的引出次数(或出度),记为deg+ ^+?
+
?(v);

入度: 以v为终点的边的条数称为结点v的引入次数(或入度),记为deg ? ^-?
?
?(v);

度数: 结点v的引出次数和引入次数之和称为结点v的次数(或度数),记作 deg(v) 。

在无向图中 ,结点v的度数是与结点v相关联的边的条数,也记为deg(v)。

孤立结点的次数为零。

握手定理: 设G=<V,E>为任意无向图, V={v 1 , v 2 , v 3 , . . . . , v n v_1,v_2,v_3,....,v_nv?
1
?
?,v?
2
?
?,v?
3
?
?,....,v?
n
?
?}, 所有的点的度数之和等于2倍的边的条数

握手定理: 设G=<V,E>为任意有向图, V={v 1 , v 2 , v 3 , . . . . , v n v_1,v_2,v_3,....,v_nv?
1
?
?,v?
2
?
?,v?
3
?
?,....,v?
n
?
?}, 所有的点的度数之和等于2倍的边的条数, 并且出度和入度相等并等于边数.

任何图 (无向或有向)中，度为 奇数的结点的个数是偶数。

各结点的度数均相同的图称为正则图,各结点的次数 均为k时称为k―正则图。

图的同构:设G1=< V 1 , E 1 > <V_1,E_1><V?
1
?
?,E?
1
?
?>, G2=< V 2 , E 2 > <V_2,E_2><V?
2
?
?,E?
2
?
?>为两个无向图(两个有向图)，若存在双射函数f: V1→ \rightarrow→V2 , 对于vi, vj∈ \in∈V1 ,
(vi, vj)∈ \in∈E1当且仅当 ( f ( v i ) , f ( v j ) ) ∈ (f(v_i), f(v_j))\in(f(v?
i
?
?),f(v?
j
?
?))∈E 2 E_2E?
2
?
?
(< v i , v j > <v_i, v_j><v?
i
?
?,v?
j
?
?>∈ \in∈E1当且仅当 < f ( v i ) , f ( v j ) > ∈ <f(v_i), f(v_j)>\in<f(v?
i
?
?),f(v?
j
?
?)>∈E 2 E_2E?
2
?
? )
并且, (v i v_iv?
i
?
? ,v j v_jv?
j
?
?)（< v i , v j > <v_i,v_j><v?
i
?
?,v?
j
?
?>）与 ( f ( v i ) , f ( v j ) ) (f(v_i), f(v_j))(f(v?
i
?
?),f(v?
j
?
?))（( < f ( v i ) , f ( v j ) > (<f(v_i), f(v_j)>(<f(v?
i
?
?),f(v?
j
?
?)>）的重数相同，则称G 1 G_1G?
1
?
?与G 2 G_2G?
2
?
?是同构的.
两图同构必要条件:
(1) 结点数相等;
(2) 边数相等;
(3) 度数相同的结点数相等.
但这不是充分条件。
?

cs