图论及其应用1-3章习题答案(电子科大)4页.doc

习题一1. （题14）：证明图1-28中的两图是同构的图1-28证明 将图1-28的两图顶点标号为如下的(a)与(b)图作映射f : f(vi)ui (1 i 10)容易证明，对vivjE(a),有f(vivj)=uiujE(b) (1 i 10, 1j 10 )由图的同构定义知，图1-27的两个图是同构的。2. （题6）设G是具有m条边的n阶简单图。证明：m =当且仅当G是完全图。证明 必要性 若G为非完全图，则$ vV(G),有d(v) n-1 d(v) n(n-1) 2mn(n-1) m n(n-1)/2=, 与已知矛盾！ 充分性 若G为完全图，则 2m= d(v) =n(n-1) m= 。3. （题9）证明：若k正则偶图具有二分类V= V1V2，则 | V1| = |V2|。 证明 由于G为k正则偶图，所以，k| V1 | =m = k| V2 |