图论习题考研习题与经典习题

图论习题课⼀、填空题1、对下列图，试填下表（是??类图的打〝√ 〞，否则打〝?〞）。

①②③2、若图G=中具有⼀条汉密尔顿回路，则对于结点集V 的每个⾮空⼦集S ，在 G 中删除S 中的所有结点得到的连通分⽀数为W ，则S 中结点数|S|与W 满⾜的关系式为。

3、设有向图D 为欧拉图，则图D 中每个结点的⼊度．4、数组{1，2，3，4，4}是⼀个能构成⽆向简单图的度数序列，此命题的真值是 .5、“3,3K 是欧拉图也是哈密顿图”这句话是_______。

(填对或错)6、极⼤可平⾯图的每⼀个⾯的次数都是_________．7、5阶完全图的边连通度是．8、图G是2-⾊的当且仅当G是．⼆、选择题1、下列⽆向图可能不是偶图的是( )(A) ⾮平凡的树(B)⽆奇圈的⾮平凡图(C) n(1)n ⽅体图(D) 平⾯图2、关于平⾯图，下列说法错误的是( )(A) 简单连通平⾯图中⾄少有⼀个度数不超过5的顶点；(B)极⼤外平⾯图的内部⾯是三⾓形，外部⾯也是三⾓形；(C) 存在⼀种⽅法，总可以把平⾯图的任意⼀个内部⾯转化为外部⾯；(D) 平⾯图的对偶图也是平⾯图。

3、已知图G的邻接矩阵为，则G有（）．A．5点，8边B．6点，7边C．6点，8边D．5点，7边4、设图G＝，则下列结论成⽴的是( )．A．deg(V)=2∣E∣B．deg(V)=∣E∣C．EvVv2)deg(=∑∈D．Vv=∑∈)deg(5、设完全图K n有n个结点(n≥2)，m条边，当（）时，K n中存在欧拉回路．A．m为奇数B．n为偶数C．n为奇数D．m为偶数6、设G是连通平⾯图，有v个结点，e条边，r个⾯，则r= ( )．A．e－v＋2 B．v＋e－2 C．e－v－2 D．e＋v＋27、下列定义正确的是( )．A含平⾏边或环的图称为多重B不含平⾏边或环的图称为简单图C含平⾏边和环的图称为多重D不含平⾏边和环的图称为简单图8、以下结论正确是( )．A仅有⼀个孤⽴结点构成的图是零图B⽆向完全图Kn每个结点的度数是nC有n(n>1)个孤⽴结点构成的图是平凡图D图中的基本回路都是简单回路9、下列数组能构成简单图的是( )．(A) (0,1,2,3) (B) (2,3,3,3) (C) (3,3,3,3) (D) (4,2,3,3)10、n阶⽆向完全图Kn中的边数为（）．(A) 2)1(+nn(B) 2)1(-nn(C) n (D)n(n+1)11、以下命题正确的是( )．(A) n(n≥1)阶完全图Kn都是欧拉图(B) n(n≥1)阶完全图Kn都是哈密顿图(C) 连通且满⾜m=n－1的图(∣V∣=n,∣E∣=m)是树(D) n(n≥5)阶完全图Kn都是平⾯图12、下列结论不正确是( )．(A) ⽆向连通图G是欧拉图的充分必要条件是G不含奇数度结点(B) ⽆向连通图G有欧拉路的充分必要条件是G最多有两个奇数度结点(C) 有向连通图D是欧拉图的充分必要条件是D的每个结点的⼊度等于出度(D) 有向连通图D有有向欧拉路的充分必要条件是除两个结点外，每个结点的⼊度等于出度13、⽆向完全图K4是（）．（A）欧拉图（B）哈密顿图（C）树（D）平⾯图14、在如下各图中（）欧拉图。

v G
G1的度序列为： (d1+1,d2+1,…,dn+1, n) 由条件：不存在小于(n+1)/2的正整数m,使得dm+1≦m,且 d(n+1)-m <(n+1)-m。于是由度序列判定定理知：G1是H图，得 G有H路。
G1Leabharlann 613.证明：若G不是H图，则G度弱于某个 Cm1 ,n ， 且有
v m1 2
3
32. （1）证明：考虑G=Cn˅H 的最小点割V。根据联图的定义， 则必有V包含Cn 或者H，否则G-V后一定连通。如果Cn ∈V，则 由H是K连通的可知|V|=n+k。若H ∈V，则V中至少还需要包含Cn 中两个不相邻的顶点，也可得|V|=n+k。故G是n+k连通的。 （2）在Cn 上任取相邻的两点x,y，设这两个点在Cn上的两条路分 别为P1和P2。考虑宽为n+k的x-y容器，因为H仅包含n+k-2个点， 经过H中的点，且独立的（x，y）路最多有n+k-2个，且每条路的 长度都为2。因此在每个容器中必包含P1和P2。故dn+k(x,y)=n-1。
1. 证明方法与p. 47 定理3类似
3. 设无环图G是阶数大于2的连通图，则下列命题等价 （1）G是块，即G是2-连通的； （2）G的任意两个顶点在某个圈上； （3）G的任一个顶点和任一条边在某个圈上； （4）G的任意两边在某个圈上； （5）G的任意两个顶点u，v及任一边e，总存在连接u，v 且过e的路； （6）G的任意三个顶点，总存在连接其中任意两个顶点， 并且通过第三个顶点的路 （7）G的任意三个顶点，总存在连接其中任意两个顶点， 并且不过第三个顶点的路 证明：1 2 2：p.48 定理4 3：令u是任一顶点，vw是任一边，由（2），存在

一、填空题1、对下列图，试填下表（是⨯⨯类图的打〝√ 〞，否则打〝⨯〞）。

① ② ③2、若图G=<V , E>中具有一条汉密尔顿回路，则对于结点集V 的每个非空子集S ，在 G 中删除S 中的所有结点得到的连通分支数为W ，则S 中结点数|S|与W 满 足的关系式为 。

3、设有向图D 为欧拉图，则图D 中每个结点的入度 ．4、数组{1，2，3，4，4}是一个能构成无向简单图的度数序列，此命题的真值是 .5、“3,3K 是欧拉图也是哈密顿图”这句话是_______。

(填对或错)6、极大可平面图的每一个面的次数都是_________．7、5阶完全图的边连通度是．8、图G是2-色的当且仅当G是．二、选择题1、下列无向图可能不是偶图的是( )(A) 非平凡的树(B)无奇圈的非平凡图(C) n(1)n 方体图(D) 平面图2、关于平面图，下列说法错误的是( )(A) 简单连通平面图中至少有一个度数不超过5的顶点；(B)极大外平面图的内部面是三角形，外部面也是三角形；(C) 存在一种方法，总可以把平面图的任意一个内部面转化为外部面；(D) 平面图的对偶图也是平面图。

3、已知图G的邻接矩阵为，则G有（）．A．5点，8边B．6点，7边C．6点，8边D．5点，7边4、设图G＝<V, E>，则下列结论成立的是( )．A．deg(V)=2∣E∣B．deg(V)=∣E∣C．EvVv2)deg(=∑∈D．EvVv=∑∈)deg(5、设完全图K n有n个结点(n≥2)，m条边，当（）时，K n中存在欧拉回路．A．m为奇数B．n为偶数C．n为奇数D．m为偶数6、设G是连通平面图，有v个结点，e条边，r个面，则r= ( )．A．e－v＋2 B．v＋e－2 C．e－v－2 D．e＋v＋27、下列定义正确的是( )．A含平行边或环的图称为多重B不含平行边或环的图称为简单图C含平行边和环的图称为多重D不含平行边和环的图称为简单图8、以下结论正确是( )．A仅有一个孤立结点构成的图是零图B无向完全图Kn每个结点的度数是nC有n(n>1)个孤立结点构成的图是平凡图D图中的基本回路都是简单回路9、下列数组能构成简单图的是( )．(A) (0,1,2,3) (B) (2,3,3,3) (C) (3,3,3,3) (D) (4,2,3,3)10、n阶无向完全图Kn中的边数为（）．(A) 2)1(+nn(B) 2)1(-nn(C) n (D)n(n+1)11、以下命题正确的是( )．(A) n(n≥1)阶完全图Kn都是欧拉图(B) n(n≥1)阶完全图Kn都是哈密顿图(C) 连通且满足m=n－1的图<V,E>(∣V∣=n,∣E∣=m)是树(D) n(n≥5)阶完全图Kn都是平面图12、下列结论不正确是( )．(A) 无向连通图G是欧拉图的充分必要条件是G不含奇数度结点(B) 无向连通图G有欧拉路的充分必要条件是G最多有两个奇数度结点(C) 有向连通图D是欧拉图的充分必要条件是D的每个结点的入度等于出度(D) 有向连通图D有有向欧拉路的充分必要条件是除两个结点外，每个结点的入度等于出度13、无向完全图K4是（）．（A）欧拉图（B）哈密顿图（C）树（D）平面图14、在如下各图中（）欧拉图。

bi 个 (i = 1,2,…,s)，则有 列。 定理 7
bi = n。故非整数组(b ,b ,…, b )是 n 的一个划分，称为 G 的频序
1 2 s
s
i 1
一个 n 阶图 G 和它的补图 G 有相同的频序列。
§1.2 子图与图的运算
且 H 中边的重数不超过 G 中对应边的 定义 1 如果 V H V G ，E H E G ， 重数，则称 H 是 G 的子图，记为 H G 。有时又称 G 是 H 的母图。 当 H G ，但 H G 时，则记为 H G ，且称 H 为 G 的真子图。G 的生成子图是 指满足 V(H) = V(G)的子图 H。 假设 V 是 V 的一个非空子集。以 V 为顶点集，以两端点均在 V 中的边的全体为边集 所组成的子图，称为 G 的由 V 导出的子图，记为 G[ V ]；简称为 G 的导出子图，导出子图 G[V\ V ]记为 G V ； 它是 G 中删除 V 中的顶点以及与这些顶点相关联的边所得到的子图。 若 V = {v}, 则把 G-{v}简记为 G–v。 假设 E 是 E 的非空子集。以 E 为边集，以 E 中边的端点全体为顶点集所组成的子图 称为 G 的由 E 导出的子图，记为 G E ；简称为 G 的边导出子图，边集为 E \ E 的 G 的 导出子图简记为 G E 。若 E e ，则用 G–e 来代替 G-{e}。 定理 8 简单图 G 中所有不同的生成子图（包括 G 和空图）的个数是 2m 个。 定义 2 设 G1，G2 是 G 的子图。若 G1 和 G2 无公共顶点，则称它们是不相交的；若 G1 和 G2 无公共边，则称它们是边不重的。G1 和 G2 的并图 G1∪G2 是指 G 的一个子图，其顶点 集为 V(G1)∪V(G2)，其边集为 E(G1)∪E(G2)；如果 G1 和 G2 是不相交的，有时就记其并图为 G1+G2。类似地可定义 G1 和 G2 的交图 G1∩G2，但此时 G1 和 G2 至少要有一个公共顶点。