PDF《离散数学图论作业 2 - 图的表示与图同构》

离散数学图论作业

2 - 图的表示与图同构 Problem

1 用邻接矩阵表示左侧的图;

并画出右侧邻接矩阵表示的有向图.

a b d c ? ? ? ? ? ? ? ?

0 1

2 0

1 2

1 1

0 1

1 0

1 0

0 2 ? ? ? ? ? ? ? ? Problem

2 1) 对下面两个简单图,先写出图的邻接矩阵 A,关联矩阵 B,然后计算矩阵 D = BBT ? A. a) K3,2 b) K2,3 2) D 与原来的图什么关系?试解释其原因. (D 是该图的什么矩阵? ) Problem

3 证明 [下左图] 和 [下右图的补图] 同构. a e f b g c h d A E F B G C H D

1 Problem

4 具有

4 个顶点的非同构简单图中,有多少个 1) 包含 C3? 2) 无孤立点? 3) 是二部图? Problem

5 若简单图 G 与?G是同构的,则G称为自补图 试证明:若正则图 G 是自补图,则图 G 的顶点数 V 满足 V ≡

1 (mod 4). Problem

6 对以下每组同构不变量的值找出一对不同构的图 1) 顶点数 =5,边数 =5,且子图中最大的完全图是 K3 2) 度序列 =(2, 2, 2, 2, 2, 2, 2) 2