PDF《图论习题课》

图论习题课 7-13章 习题7.

1 ? 设无向图G有16条边,有3个4度顶点、4个3 度顶点,其余顶点的度数均小于3,问G中 至少有几个顶点? 习题7.1解答 ? 设G至少有n个顶点,G有n-7个顶点的度数 至多为2,由于握手基本定理: 2m=32 ≤3*4+4*3+2(n-7) ? 解出n≥11,即G中至少有11个顶点,当度数 小于3的顶点都是2度顶点时,G有11个顶点 ,其中4个是2度顶点. 习题7.2 ? 设9阶无向图G中,每个顶点的度数不是5就是6,证明G中至少有5个6度顶点或至少6个 5度顶点. 习题7.2解答 ? 反证法.否则G至多有4个6度顶点,并且至多 有5个5度顶点,但是由于握手定理的推论 可知,G不可能有5个5度顶点,于是G至多 有8个顶点,这与G有9个顶点相矛盾. 习题7.3 ? 证明空间中不可能存在有奇数个面且每个 面均有奇数条棱的多面体. 习题7.3解答 ? 反证法.假设存在具有奇数个面且每个面都 有奇数条棱的多面体.令G=.其中, V={v|v为G的面}, E={(u,v)|u,v ∈ V ∧ u ≠ v ∧ u与v有公共棱}. ? 由假设可知,|V|为奇数,且每个点的度数 都是奇数,于是G有奇数个奇度顶点,这与 握手定理推论相矛盾 习题7.5 ? 设n阶无向简单图G为3次图(3-正则图),边数m与n满足如下关系: 2n-3=m ? 试问G有几种非同构情况?并证明你的结论. 习题7.5解答(1) ? 先给出一个命题: ? 设G1与G2同为n阶无向简单图,则G1 ≌G2当 且仅当G'1 ≌G'2,其中G'1 ,G'2分别是G1和G2的 补图. 习题7.5解答(2) ? 由已知条件和握手定理,知: 3n=2m,2n-3=m. ? 解方程组,得n=6,m=9.由此可知满足题设 的3-正则图都是6阶9条边的无向简单图,他 们都是K6的子图.这样的子图只有两种非同 构的: 习题7.5解答(2) ? 因为这两个图的补图对应下面两个图,6阶 9边的3-正则图的补图只有这两种 习题7.11 ? 设无向图G是n阶自补图,证明n=4k或n=4k+1,其中k为正整数. 习题7.11解答 ? 设G为n阶自补图,则G ≌ G'(G'为G的补图) ,于是G与G的边数相等,且他们边数之和 为n阶完全图Kn的边数,设G的边数为m, 则?m=Cn 2/2=n(n-1)/4 ? 即4m=n(n-1),由于n与n-1互素,必有n=4k 或n=4k+1. 习题7.14 ? 设n(nR3)阶无向简单图G是连通的,但不是 完全图,证明存在u,v,w∈V(G),使得 (u,v)(v,w) ∈E(G),而(u,w) ? E(G). 习题7.14解答 ? 反证法.否则?n,v,w ∈ V(G),只要(u,v)和(v,w) ∈ E(G),就有(u,v) ∈ E(G). ? ?u,v ∈ V(G),由G的连通性可知,u与v之间有通 路,设P=uv1v2…vrv为u与v之间的一条通路.因为 (u,v1),(v1,v2) ∈ E(G),由假设可知(u,v2) ∈ E(G). 以此类推,必有(u,v) ∈ E(G),有u,v的任意性,可知G为无向完全图Kn,与G不是完全图矛盾. 习题7.16 ? 设G是无向简单图,δ(G) R3,证明G中各圈 长度的最大公约数为1或2. 习题7.16解答(1) ? 不妨设G是连通简单图,否则可以对G的某个连通 分支讨论. ? 设P=vi0vi1vil为G中一条极大路径.则l R(G) R3.由于 vi0不与P外顶点相邻,又因为G为简单图,则在P上除vi0vil相邻外,有(G) R3,还至少存在两个顶点 ,设其为vir,vir(1