假设图中所有结点的度数都大于等于5。
由欧拉握手定理得v?Vdeg(v)=2|E|得 5n?2m。 又因为G=〈V,E,F〉是一个连通简单无向平面图， 所以对每个面f,deg(f)?3。
由公式f?Fdeg(f)=2|E|可得，2m?3k。
??221再由欧拉公式|V|-|E|+|F|=2可得2?5m-m+3m=15m
从而30?m,这与已知矛盾。
99、在一个连通简单无向平面图G=〈V，E，F〉中若|V|?3，则 |E|?3|V|－6。 证明：
? |V|?3，且G=〈V，E，F〉是一个连通简单无向平面图， ? d(f) ?3，?f?F。
由公式f?Fdeg (f)=2|E|可得，2|E|?3|F|。
?2再由欧拉公式|V|-|E|+|F|=2可得|V|-|E|+3|E|?2。 ?|E|?3|V|－6。
100、给定连通简单平面图G=
因为|V|=6?3，且G=〈V,E,F〉是一个连通简单无向平面图， 所以对任一f?F，deg(f)?3。 由欧拉公式|V|-|E|+|F|=2可得|F|=8。
再由公式f?Fdeg(f)=2|E|，f?Fdeg(f)=24。
因为对任一f?F，deg(f)?3，故要使上述等式成立， 对任一f?F，deg(f)=3。
101、设G=
若G 不连通，则它可分成两个独立的子图G1和G2，其中|V(G1)|+|V(G2)|-2=n ，且G1中的任一个顶点至多只和G1中的顶点邻接，而G2中的任一顶点至多只和G2中的顶点邻接。任取u?V(G1),v?V(G2),则 d(u)?|V(G1)|-1, d(v)?|V(G2)|-1。
故d(u)+d(v) ?(|V(G1)|-1)+(|V(G2)|-1)?|V(G1)|+|V(G2)|-2
45
??
=n-2 102、一次会议有20人参加，其中每个人都在其中有不下10个朋友。这20人围成一圆桌入席。有没有可能使任意相邻而坐的两个人都是朋友？为什么？ 证明： 可以。 将每个人对应成相应的顶点，若两人是朋友，则对应的两个顶点间连上一条无向边，作出一个简单无向图。由已知，图中每个顶点的度数都大于等于10。即图中任两个不相邻的顶点的度数大于等于20，即顶点数。故这个图是一个哈密尔顿图，从而存在哈密尔顿回路。任取一条哈密尔顿回路，按回路经过的顶点的次序安排对应的人的座位，就可满足要求。 103、证明在任何两个或两个以上人的组内，存在两个人在组内有相同个数的朋友。 证明： 将每个人对应成相应的顶点，若两人是朋友，则对应的两个顶点间连上一条无向边，作出一个简单无向图。则原命题相当于在该无向图中一定存在两个顶点的度数相等。 设该简单无向图中有n个顶点，则图中n个顶点的度数只能为0，1，2，…，n-1。若图中有两个或两个以上的顶点度数为0，则结论显然成立。否则所有顶点的度数都大于等于1。现用反证法证明该无向图中一定存在两个顶点的度数相等。 设该简单无向图中n个顶点中任何一对顶点的度数都不相等，即这n个顶点的度数两两不同。但每个顶点的度数只能是1,2,…,n-1这n-1个数中的某一种，这显然产生了矛盾。 因此该无向图中一定存在两个顶点的度数相等。从而在任何两个或两个以上人的组内，存在两个人在组内有相同个数的朋友。 104、设有如下有向图G= （1）求G的邻接矩阵；（2）G中v1到v4的长度为4 的通路有多少条？（3）G中经过v1的长度为3 的回路有多少条？（4）G中长度不超过4 的通路有多少条？其中有多少条通路？ 解： ?1?1??0?0A=??3?2??0?0A3=? 110??2?1010????0001???010?0，A2=?242??5 ?3131????0001??? 010?0 ，A4=? 121?111??010??001? 374?243??010? ? 001? G中v1到v4的长度为4 的通路有4条； G中经过v1的长度为3 的回路有3条； 46 （4） G中长度不超过4 的通路有72条，其中有19条回路。 ?v1 ?v4 ? v2 ?v3 题104图 105、求下列无向图中每个顶点的度数；求下列有向图中每个顶点的出度、入度和度。 解： a? ?d ?e ?c ?b ?f 在这个无向图中d(a)=3,d(b)=6, d(c)=4, d(d)=3, d(e)=0, d(f)=0。 c b a 在这个有向图中d(a)=3,d(b)=4, d(c)=3, d(a)=2, d(a)=1, d(b)=2 , d(b)=2,d(c)=1, d(a)=2。 a? ?d ?e 47 ?????? ?c ?b ?f 题106图 106、求下列无向图的子图、生成子图、由边集诱导的子图和由顶点集诱导的子图。 解： c b 它的一个子图 d a e c b f 它的一个生成子图 d a c b 48
相关推荐：
loading