图论.doc

文档介绍：第七章图论

1.
非简单图;(有自圈)
非简单图;(有自圈)
简单图。
3.
证明:因为n个顶点的有向简单图中,每两个不同顶点之间最多有两条边,因此其边数最多为:。
4.
证明:因为任何图均有偶数个奇结点,而3度正则图的所有结点度数均为3,即均为偶结点。所以,3度正则图必有偶数个奇结点。
5.
6.
证明:假设六个人分别为:a, b, c, d, e, f。则分两种情况讨论。
①若a认识的人大于等于3个,即b, c, d, e, f中至少有3个与a认识。不妨设c, d, e与a认识,则c, d, e必定互相不认识。(否则,c, d, e中互相认识的两人与a就构成三个人互相都认识。产生矛盾。)
②若a认识的人小于3个,即b, c, d, e, f中至少有3个与a不认识。不妨设b, c, d与a均不认识。则因为没有3个人彼此都认识,所以b, c, d中必有两个人互相不认识。假设c, d互相不认识,则a, c, d三个人彼此都不认识。
a ) 图中有一个与两个度数为3的结点邻接的结点,其度数也为3。
而b ) 图中没有任何一个度数为3的结点与两个度数为3的结点邻接。
所以,a ) 与b ) 不同构。
9. b ) 图的中心结点其入度为0,而a ) 图中没有入度为0 的结点。所以两图不同构。
10. n阶简单无向图的结点度数不可能超过n-1,即取值范围为:{0, 1, 2, …, n-1}。
证明n(n>1)阶图中必有两个结点度数相等,抽屉原则应该可以使用,但n个结点,n种度数可能,抽屉原则似乎用不上。但我们发现,若图中有孤立点,则所有结点的度数只可能从0到n-2中取值,即只有n-1种可能性。于是分两种情况:
①若G中无孤立点(度数为0的结点),则G中n个结点的度数只能从1到n-1中取值。n个结点,n-1种可能的度数取值,由抽屉原则,G中必有两个结点的度数相等。
②若G中有孤立点,则G中n个结点的度数只能从0到n-2中取值。n个结点,n-1种可能的度数取值,由抽屉原则,G中必有两个结点的度数相等。
11. 。所以,
,即。

2. 显然G[V¢]重任意两点之间必定互有有向边,并且无自圈、无平行边。
4.
自反的;
反对称的、传递的;
自反的、对称的、传递的;
自反的、传递的;
无;
对称的;
自反的、反对称的、传递的;
对称的;
对称的;
反对称的;
自反的、反对称的;
反对称的、传递的。
4.
A上共有个不相同的自反关系;
A上共有个不相同的反自反关系;
A上共有个不相同的对称关系;
A上共有个不相同的反对称关系;
A上共有个不相同的既是对称的又是反对称的关系;

1. 最多能有n(A) 个元素为1。
2.
证明:
i) R È R-1为A上包含R的最小对称关系
① R Í R È R-1。所以,RÈR-1包含R。
② 因为对于任意<a, b> Î R È R-1,有<a, b> Î R或<a, b> Î R-1。
若<a, b> Î R,则<b, a> Î R-1;若<a, b> Î R-1,则<b, a> Î R。