第7章 图的基本概念

本章主要讨论图的基本知识，下章讨论几个特殊的图。

一、基本要求

1. 了解图的概念：结点、边、有向图，无向图、图的同构、简单图、完全图，补图、度数、子图、重数和平行边等。

理解握手定理。

2. 了解通路与回路概念：通路(简单通路、初级通路和复杂通路)，回路(简单回路、初级回路和复杂回路) 。

会求通路的长度。

3. 掌握图的连通性：无向连通图，连通分支；有向连通图(强连通(强分图)；单向连通(单侧分图)；弱连通(弱分图))；

了解点割集、割边、点连通度、边连通度等概念。

4. 了解(有向图、无向图)关联矩阵、(无向图)相邻矩阵、(有向图)邻接矩阵和(有向图)可达矩阵的概念，掌握其构造方法。

5. 了解带权的图、最短通路概念，知道关键路径概念。

本章重点：图的概念，握手定理，通路、回路以及图的矩阵表示。

二、学习辅导

1.图论知识系统表

2. 图的基本概念

| 图(结点(集)、边(集))，邻接点，孤立点，平行点(重数)，度数(deg(v))(入度、出度)。

| 。

| 握手定理：

| 路 通路(简单通路、初级通路、复杂通路、通路的长度)，回路(简单通路、初级通路、复杂通路)。

| 连通 连通图((结点)连通、连通分支)、割点(集)、割边、连通度、(有向图)单侧连通(单侧分图)、强连通(强分图)、(无向图)弱连通(弱分图)。

例5.1 设G＝(V,E)是一个无向图，

(1) 画出G的图解；

(2) 指出与v₃邻接的结点，以及与v₃关联的边；

(3) 指出与e₁邻接的边，以及与e₁关联的结点；

(4) 该图是否有孤立结点和孤立边？

(5) 求出各结点的度数，并判断是不是完全图？

(6) G＝<V,E>的½V½，½E½各是多少？

解 (1) 所给图G的一个图解如图5－1。

(2) 结点v₁, v₂, v₄是与v₃邻接，v₃关联

的边为e₁, e₂, e₃。

(3) 边e₂, e₃, e₄均与边e₃邻接；与边e₁

关联的结点为v₂, v₃。

(4) 结点v₆是孤立点；e₅是孤立边。

(5) deg(v₁)=3，deg(v₂)=2，deg(v₃)=3，

deg(v₄)=2，deg(v₅)=2，deg(v₆)=0，

deg(v₇)=1，deg(v₈)=1，

因为结点v₆是孤立点，所以这不是完全图。

(6) G=<V,E>是有½V½=8条个结点，½E½=7条边的图，故又称是8阶图。

例5.2 设图G是具有3个结点的完全图，试问

(1) G有多少个子图？

(2) G有多少个生成子图？

(3) 如果没有任何两个子图是同构的，则G的子图个数是多少？将它们构造出来。

解 (1) 因为含有1个结点的子图有个；

含有2个结点的子图有个；

含有3个结点的子图有个；

所以，G共有3＋6＋8＝17个子图。

(2) G的生成子图，含有G的所有结点，G有3条边，构成子图时，每条边有选中或不选中两种可能，所以G的生成子图的个数是2³＝8个。

(3) G的所有不同构的生成子图有7个，如图5－2所示。

例5.3 给定下列六个图(如图5－3)，

G₁＝<V₁,E₁>,其中V₁={a,b,c,d,e},E₁={<a,b>,<b,c>,<c,d>,<a,e>}

G₂＝<V₂,E₂>,其中V₂=V₁,E₂={<a,b>,<b,e>,<e,b>,<a,e>,<d,e>}

G₃＝<V₃,E₃>,其中V₃=V₁,E₃={<a,b>,<b,e>,<e,d>,<c,c>}

G₄＝<V₄,E₄>,其中V₄=V₁,E₄={<a,b>,<b,c>,<c,a>,<a,d>,<d,a>,<d,e>}

G₅＝<V₅,E₅>,其中V₅=V₁,E₅={<a,b>,<b,a>,<b,c>,<c,d>,<d,e>,<e,a>}

G₆＝<V₆,E₆>,其中V₆=V₁,E₆={<a,a>,<a,b>,<b,c>,<e,c>,<e,d>}

试问：

(1) 哪些图是有向图？哪些图是无向图？

(2) 哪些是简单图？

(3) 哪些是强连通图？哪些是单侧连通图？哪些是弱连通图？

解 (1) G₁, G₂, G₃是无向图；G₄, G₅, G₆是有向图。

(2) G₁, G₄, G₅, G₆中既无平行边，也无自回路，故为简单图。

(3) G₅是强连通图，也是单侧连通图和弱连通图；

G₄是单侧连通图，也是弱连通图；

G₆只是弱连通图。

例5.4 给定图G=<V,E>,如图5－4，

(1)在G中找出一条长度为7的通路；

(2) 在G中找出一条长度为4的简单通路；

(3) 在G中找出一条长度为5的初级通路；

(4) 在G中找出一条长度为8的复杂通路；

(5)在G中找出一条长度为7的回路；

(6) 在G中找出一条长度为4的简单回路；

(7) 在G中找出一条长度为5的初级回路；

(8) 在G中找出一条长度为7的复杂回路。

解 所选通(回)路都不是唯一的。

(1) 长度为7的通路：

v₁ v₄ v₃ v₇ v₈ v₆v₅v₂

(2) 长度为4的简单通路：

< v₁, v₄>,< v₄, v₃>,< v₃ ,v₇>,< v₇, v₄>

(边不重复的通路)

(3) 长度为5的初级通路：

v₁ v₅ v₂ v₆ v₈ v₄(结点不重复的通路)

(4) 长度为8的复杂通路：

<v₁, v₅>,< v₅, v₈>,< v₈, v₇>,< v₇, v₆>,< v₆, v₈>,< v₈, v₅>,< v₅, v₄>,< v₄, v₃>

(边有重复的通路)

(5) 长度为7的回路：

v₁ v₄ v₃ v₇ v₈ v₆v₅v₁

(6)长度为4的简单回路：

< v₁, v₄>,< v₄, v₈>,< v₈ ,v₅>,< v₅, v₁>

(边不重复的通路)

(7)长度为5的初级回路：

v₁ v₅ v₆ v₇ v₄ v₁(结点不重复的通路)

(8) 长度为8的复杂回路：

<v₁, v₅>,< v₅, v₈>,< v₈, v₇>,< v₇, v₆>,< v₆, v₈>,< v₈, v₅>,< v₅, v₄>,< v₄, v₁>

(边有重复的通路)

2. 图的矩阵表示

| (无向图)关联矩阵 设G=<V,E>, ，关联矩阵

M(G)=,其中m_ij=v_i与e_j的关联次数(行为结点，列为边)。

具有性质：

① (列元素之和为2)；

② ； ，表明v_I是孤立点；

③，即所有元素之和等于边数的2倍；

④ 平行边的列的元素完全对应相同。

| (无向图)相邻矩阵 设G＝<V，E>, ，相邻矩阵

A(G)=，其中a_ij=v_i与v_j相关联的边的条数(行、列均为结点)。

具有性质

① A(G)是对称矩阵；

② ，，表明v_I是孤立点；

| (有向图)关联矩阵设D＝<V,E>, ，关联矩阵

M(D)=，其中(结点为行，边为列) 。

具有性质：

① (列元素之和为 0〕；

② ；

③ 。

| (有向图)邻接矩阵 设D=<V,E>, ，邻接矩阵

A(D)=,其中a_ij=邻接v_i与v_j的边的个数 (与A(G)类似)( 以行和列均为结点)。

具有性质：

| (有向图)可达矩阵 设D=<V,E>，，可达矩阵

P(D)=，其中。

例5.5 求例5.3中图G₂的关联矩阵，图G₃的相邻矩阵，图G₄的邻接矩阵，图G₅的关联矩阵和图G₆的可达矩阵。

解 (1)已知图G₂的结点集V₂={a,b,c,d,e},边集

E₂={<a,b>,<b,e>,<e,b>,<a,e>,<d,e>}，n=5,m=5。

G₂是无向图，由关联矩阵的定义，，其中m_ij=v_i与e_j关联的次数。该图没有自回路，矩阵的元素要么是0，要么是1。有

(2) 因为G₃为V₃={a,b,c,d,e}, E₃={<a,b>,<b,e>,<e,d>,<c,c>}，是无向图，由相邻矩阵的定义，，其中a_ij=v_i与v_j关联的边的次数。n=5,故相邻矩阵为

(3) 因为图G₄为V₃={a,b,c,d,e}, E₄={<a,b>,<b,c>,<c,a>,<a,d>,<d,a>,<d,e>}，n=5,m=6,由有向图的邻接矩阵的定义，其中a_ij=v_i邻接到v_j的边的数目。于是所求邻接矩阵为

(4) 有向图G₅，V₅={a,b,c,d,e}, E₅={<a,b>,<b,a>,<b,c>,<c,d>,<d,e>,<e,a>}，由关联矩阵的定义，其中当v_i为e_j的始点时，m_ij=1；当v_I为e_j的终点时，m_ij=－1；当v_I与e_j不关联时，m_ij=0。于是所求关联矩阵为

(5) 有向图G₆的可达矩阵。V₆=》a,b,c,d,e〉, E₆={<a,a>,<a,b>,<b,c>,<e,c>,<e,d>}，由可达矩阵的定义，当v_i可达v_j时，p_ij=1,当v_i与v_j不关联时，p_ij=0。于是G₆的可达矩阵为

三、实例

例1 在图G＝<V,E>中，结点总度数与边数的关系是( )

(A) deg(v_i)=2½E½ (B) deg(v_i)=½E½ (C) (D)

答案：(C)

解答：见握手定理。

例2 设G是有n个结点的无向完全图，则图G的边数为( )；设D是有n个结点的有向完全图，则图D的边数为( )

(A) n(n－1) (B) n(n+1) (C) n(n－1)/2 (D) n(n+1)/2

答案：(C) （A）

解答：G有n个结点，任意两点有一条边，共有条边。故选择(C);有向图D中，任意两点有两条方向相反的边，才能互通，因此n个结点要有2×条，故选择(A)。

例3 仅有一个孤立结点组成的图称为( )

(A) 零图 (B) 平凡图 (C) 补图 (D) 子图

答案：(B)

解答：见定义，只有一个孤立结点的图称为平凡图；有孤立结点组成的图称为零图。

例4 设G＝<V,E>为无向简单图，½V½=n，D(G)为G的最大度，则有

(A) D(G)<n (B)D(G)£n (C) D(G)>n (D) D(G)³n

答案：(A)

解答：因为G中无平行边和环，任何结点最多有n－1条边与其它边联结，最大度数为n－1。故选择(A)

例5图G与G¢的结点和边分别存在一一对应关系，是G≌G¢(同构)的( )

(A) 充分条件 (B) 必要条件 (C)充分必要条件 (D)既非充分也非必要条件

答案：(B)

解答：见图的同构定义。

例6 设，则与V能构成强连通图的边集合是( )

(A) (A)

(B) (B)

(C) (C)

(D) (D)

答案：(A)

解答：有向图G任何一对结点间都互相可达，称该图是强连通的。(A)所给的边的集合满足定义的条件。故选择(A)。

例7相邻矩阵具有对称性的图一定是( )

(A) 有向图 (B) 无向图 (C) 混合图 (D) 简单图

答案：(B)

解答：只有无向图有相邻矩阵，且相邻矩阵是对称的。故选择(B)。

例8设图G＝<V，E>和G¢＝<V¢,E¢>,若 ，则G¢是G的真子图，若 ，则G¢是G的生成子图。

答案：

解答：见真子图和生成子图的定义。

例9 在无向图中，结点间的连通关系具有 性， 性， 性，是 关系。

答案：自反性，对称性，传递性，等价。

解答：见图的连通性质。

例10 无环有向图D的关联矩阵M(D)中，第i行值为1的元素个数为结点v_i的 ，

第j列值为－1的元素个数为结点v_j的 ，

答案：出度；入度

解答：见无环有向图关联矩阵的定义及具有的性质。

例11 给定有向图D如图(图5－5)，

试写出D中长度为1,2,3,4的通路有几条？

解

e₁e₆e₇e₂

e₁e₆e₇e₃

e₁e₆e₅e₄

e₁e₆e₅e₄