内容发布更新时间 : 2025/6/18 4:50:12星期一 下面是文章的全部内容请认真阅读。
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?