图论基础知识(一) —— 图

一、定义

定义1：图

设V是一个非空集合，E是一个V中元素的无序对构成的多重集，有序对G=<V, E>称为一个图(graph)。其中，V称为顶点集，其元素称为顶点或点(vertex)，E称为边集，其元素为边(edge)。

定义2：关联、邻接

设G是一个图，u、v∈V(G)，e = uv ∈E(G)，称u、v为e的端点，e为连接u、v的边，并称顶点u、v与边e彼此关联(incident)，顶点u和v是邻接的(adjacent)。

定义3：相邻边、相邻点

在任意图中，同一条边关联的两个点，称为相邻点，同一个点关联的诸多边称为相邻边。

定义4：自环、多重边

设G是一个图，若e∈G的两端点重合为一点，即e = uu，则e为自环，若uv∈E(G)的重复度 > 1，则称uv是多重边。

定义5：度数、孤立点、悬挂点、奇顶点、偶顶点

设G是一个图，v∈V(G)，与v相关联的边数(自环计算两次)称为v的度数，记为 d G ( v ) d_G(v) dG(v)或简记为 d ( v ) d(v) d(v)。度数为0的点称为孤立点，度数为1的点称为悬挂点，度数为奇数的点称为奇顶点，度数为偶数的点称为偶顶点。

图G中顶点的最小度数即为 δ ( G ) delta(G) δ(G)，最大度数记为 Δ ( G ) Delta(G) Δ(G)，即 δ ( G ) = min ⁡ { d ( v ) ∣ v ∈ V ( G ) } Δ ( G ) = max ⁡ { d ( v ) ∣ v ∈ V ( G ) } delta(G) = min {d(v) | v in V(G)} \ Delta(G) = max {d(v) | v in V(G)} δ(G)=min{ d(v)∣v∈V(G)}Δ(G)=max{ d(v)∣v∈V(G)}

定义6：有限图、顶点数、边数

设G是图，若V(G)和E(G)均是有限集，则称G为有限图。用v(G)或v表示图G的点数，用ε(G)或ε表示图G的边数。

定义7：平凡图、零图、简单图、多重图

（1）设v = 1，ε = 0, 称G是平凡图。 （2）如果ε = 0，称G是零图。 （3）不含多重边和自环的图称为简单图。 （4）含有多重边的图称为多重图。

定义8：完全图

设G是一个简单图，如果G中任何两顶点之间均有边相连，则称G为完全图，具有n个顶点的完全图记为 K n K_n Kn。

定义9：二分图

设G是一个图，如果存在V(G)的子集 V 1 V_1 V1、 V 2 V_2 V2使得 V 1 ∪ V 2 = V ( G ) V_1 cup V_2 = V(G) V1∪V2=V(G)， V 1 ∩ V 2 = ∅ V_1 cap V_2 = emptyset V1∩V2=∅，且 V 1 V_1 V1中任意两点不相邻， V 2 V_2 V2中任意两点不相邻，则称G为二分图，并称 { V 1 , V 2 } {V_1,V_2} { V1,V2}为G的一个二划分，进一步，若 V 1 V_1 V1中每一点皆与 V 2 V_2 V2中所有点相邻，则称G为完全二分图，且当 ∣ V 1 ∣ = m |V_1|= m ∣V1∣=m， ∣ V 2 ∣ = n |V_2| = n ∣V2∣=n，将其记作 K m , n K_{m,n} Km,n。

定义10：正则图

设G是一个图，k是一个常数，若G中每个顶点的度数均为k，则称G为k次正则图。

定义11：子图、真子图、生成子图

设G、H是两个图，如果V(H)⊆V(G)，E(H)⊆E(G)，则称H是G的子图，记为H⊆G。若H⊆G且H≠G称H是G的真子图，记作H⊂G。若H⊆G且V(H) = V(G)，称H是G的生成子图。

定义12：边导出子图、点导出子图

设G是一个图， E 1 ⊆ E ( G ) E_1 subseteq E(G) E1⊆E(G)，以 E 1 E_1 E1为边集， E 1 E_1 E1中边的端点， E 1 E_1 E1中边的端点全体为顶点集构成的子图，称为由 E 1 E_1 E1导出的G的子图(边导出子图)，记为 G ( E 1 ) G(E_1) G(E1)。又设 V 1 ⊆ V ( G ) V_1 subseteq V(G) V1⊆V(G)，以 V 1 V_1 V1为顶点集，端点均在 V 1 V_1 V1中的边的全体为边集，构成的子图，称为由 V 1 V_1 V1导出的G的子图(点导出子图)，记为 G ( V 1 ) G(V_1) G(V1)。

定义13：补图

设G是具有n个顶点的简单图，从这n个点构成的完全图 K n K_n Kn中删去G的所有边，但保留顶点集V(G)所得到的图称为G的补图，简称G的补，记为~G。

定理

定理1(握手定理)

对任一图G，有 ∑ v ∈ V ( G ) d ( v ) = 2 ϵ sum_{v in V(G)}d(v) = 2 epsilon v∈V(G)∑d(v)=2ϵ 推论  任意图中奇顶点的个数必为偶数