a?,b?,c??L满足等式：

(a??b?)?(b??c?)?(c??a?)?(a??b?)?(b??c?)?(c??a?) (1)

于是式(1)的左边

?[((a?b)?(a?c))?(b?c)]?[(b?c)?a]?a?[(a?b)?(b?c)?(c?a)]?a左边

?[(a?b)?(b?c)?(c?a)]?a?(b?c)?a因为a?a?b，a?a?c，故a?(a?b)?(a?c) 所以a?[(a?b)?(a?c)]?(a?b)?(a?c)。 将a?,b?,c?带入(1)的右边得

?[((a?b)?(a?c))?(b?c)]?[(b?c)?a]?[a?((a?b)?(a?c))]?([((a?b)?(a?c))?(b?c)]?[(a?b)?(a?c)])?[(b?c)?a]右边?[(a?b)?(a?c)]?[(a?c)?b]?(a?b)?[(a?c)?((a?c)?b]?(a?b)?(a?c)所以有a?(b?c)?(a?b)?(a?c)。因此是分配格。

41

第8章 图论

1、图1所示之图是否同构于图2

图1 图2

h(v5)?u6,h(v6)?u5，显然h是双射且满足同构的定义。

答：根据点和边的关联关系，构造h:V1?V2,h(vi)?ui,i?1,2,3,4，

2、图3中所给出的两个8结点图是否同构？证明你的回答

图3(a) 图3(b) 答：上述两个图不同构。

证明：因为图3(b)中4个度数为3的结点中每一个均与另外两个度数为3的结点相邻，而图3(a)中的每个度数为3的结点只与另外一个度数为3的结点相邻，所以不同构。

3、证明在任何图中奇次度结点的个数是偶数。

证明：反证，假设图G中存在奇数个奇次度结点，则图中不论偶次度结点的个数是奇数还是偶数，该图的结点总度数为偶数，但是任何图的所有结点度的总和又为边数的两倍，因此必为偶数，矛盾！

4、设G是具有4个结点的完全图，试问： (1)G有多少个子图？ (2)G 有多少个生成子图？

42

(3)如果没有任何两个子图是同构的，则G的子图个数是多少？请将这些子图构造出来？

12?2个，含有三答：(1)含有一个结点的子图有C4个，含有两个结点的子图有C434?8个，含有4个结点的子图有C4?64个，所以共有112个个结点的子图有C4子图。

(2) G的生成子图包含G的所有结点，因为G有6条边，构成子图时，每条边有被选和不被选择两种情况，因此G生成的子图为26=64种。 (3)G的所有不同构的子图如下：共18个。

5、在图4中找出其所有的真路和环，该图是否包含有割边？

图4

解：真路：v1v2v5cv3v6等。环：v1v2v5v4v1等。其中{v3,v4}是割边，因为该条边不在G的任何环中出现。

6、图G的邻接矩阵为：

43

?00110?0?00001?1???10000?0 A???

?10000?0?01000?1??01001??0给出，G是否是连通的？

解：直接由邻接矩阵给出图G的一个图解，如下图所示，显然G是不连通的。

7、求下图中图(a)和图(b)的全部断集：

(a)

(b)

S6?{a,e,f,c}，S7?{b,d,e,f}都是边割集。

解：对于图(a)S1?{a,f,d}，S2?{a,e,b}，S3?{b,c,f}，S4?{c,f,d}，S5?{g}，对于图(b)S1?{a,b}，S2?{f,g}，S3?{c,d,e}，S4?{a,c,d,f}都是边割集。

8、证明图G的任一生成树和任一边割集至少有一条公共边。

证明：设图G中若有一个边割S与G的一棵生成树T没有公共边，那么删去S后所得子图G?S必包含T，这意味着G?S仍连通，与S是边割集矛盾，所以一定

44