离散数学CH04图论基本概念

1、会计学1离散数学离散数学CH04图论基本概念图论基本概念图的基本概念4.1连通图4.34.4图的矩阵表示路和回路4.2欧拉图和哈密顿图4.5二部图及匹配4.74.8平面图树4.6有趣的图论问题能否从河岸或小岛出发，通过每一座桥，且仅通过一次回到原地？问题ADBCabcdefg 图论是一个重要的数学分支。数学家欧拉1736年发表了关于图论的第一篇论文，解决了著名的哥尼斯堡七桥问题。克希霍夫对电路网络的研究、凯来在有机化学的计算中都应用了树和生成树的概念。以及在民间广为流传的一些游戏问题：例如迷宫问题、棋盘上马的行走路线问题等等。这些古老的问题当时吸引了许多学者的注意，从而在这些问题研究的基础上，

2、又提出了著名的四色猜想和环游世界各国的问题。有趣的图论问题（0，0）（0，3）（3，0）（5，1）（0，1） （1，0）（1，3）（3，3）（5，0） （2，3）（2，0） （0，2） （5，2） （4，3）（4，0）（5，3）图 有趣的图论问题有趣的图论问题有趣的图论问题有趣的图论问题4.1 图的基本概念abcdabcddcbabacdacbddcba4.1 图的基本概念下面表示的是同一个图4.1 图的基本概念4.1 图的基本概念4.1 图的基本概念4.1 图的基本概念【例4.1】 解：G的图形如图所示。4.1 图的基本概念4.1 图的基本概念4.1 图的基本概念有向图无向图混合图4.1 图

3、的基本概念4.1 图的基本概念4.1 图的基本概念2)deg(1v3)deg(2v2)deg(3v2)deg(4v5)deg(5v1v2v3v4v5v5)( G2)(G例4.1 图的基本概念EvVvii2)deg(一个图中有10个结点，每个结点的度数为6, 图中有多少条边？结点度数总和：6 10=60因为 2e = 60，所以 e = 30.解：4.1 图的基本概念下面哪些可以作为一个图的度数列（或称为可图化的）)5 , 4 , 4 , 3 , 2(.2)5 , 4 , 4 , 3 , 3 , 2(.1)3 , 3 , 3 , 1 (.3)6 , 6 , 5 , 4 , 3 , 3 , 1 (

4、.5)5 , 4 , 3 , 3 , 2 , 1 (.6)7 , 6 , 5 , 4 , 3 , 3 , 2(.4？V=v1, v2, , vn为无向图G的顶点集，称d(v1), d(v2), , d(vn)为G的度数列4.1 图的基本概念 在任何有向图中,所有结点入度之和等于出度之和.EvvVviVviii)(deg)(deg定理14.1.24.1 图的基本概念4.1 图的基本概念4.1 图的基本概念4.1 图的基本概念4.1 图的基本概念4.1 图的基本概念4.1 图的基本概念4.1 图的基本概念3K4K5K4.1 图的基本概念).1(21nn因为 Kn 中任意两点间都有边相连，而 n 个

5、结点中任取两点的组合数(即总边数)为:).1(212nnCn n阶有向完全图的边数为？4.1 图的基本概念4.1 图的基本概念正则图边数（由握手定理得）2nkm 4.1 图的基本概念4.1 图的基本概念4.1 图的基本概念G1 G24.1 图的基本概念充要条件4.1 图的基本概念4.1 图的基本概念必要条件4.1 图的基本概念1v1v2v2v3v3v6v6v4v4v5v5v例4.1 图的基本概念ddaabbcc例4.1 图的基本概念v1v2v3v4v5v6v1v2v3v4v5v6例4.1 图的基本概念1v1v2v2v3v3v4v4v5v5v6v6v例4.1 图的基本概念aabbccdd例4.1

6、 图的基本概念GGGG例4.1 图的基本概念例4.1 图的基本概念5v1v2v3v6v10v9v7v8v4v例(续)4.1 图的基本概念1v6v10v9v7v8v2v3v4v5v1v2v3v6v10v9v7v8v4v5v例(续)4.1 图的基本概念1v2v3v6v4v5v10v9v7v8v1v2v3v6v10v9v7v8v4v5v例(续)4.1 图的基本概念1v2v3v6v4v5v10v9v7v8v1v2v3v6v10v9v7v8v4v5v例(续)4.1 图的基本概念1v2v3v6v4v5v10v9v7v8v例(续)4.1 图的基本概念GG4.1 图的基本概念GGK54.1 图的基本概念在图中

7、，(b)是(a)的补图，(a)与(b)同构，所以(a)是自补图。 ？解G 是一个有 15 条边的简单图， 有 13 条边，请问 G 中有多少个结点? G共有 15 + 13 = 28 条边，GG 是一个完全图，它的结点数与 G 相同，设为 n，则GG n(n-1)/2 = 28n = 8问题4.1 图的基本概念4.1 图的基本概念包含 G 的所有结点的子图。生成子图G2G1G生成子图子图3G子图例4.1 图的基本概念生成子图子图不是子图v1v2v3v4v1v2v3v4v1v2v3v4v1v2v3v4例4.1 图的基本概念？请画出 4 阶 3 条边的所有非同构的无向简单图？问题4.1 图的基本概

8、念【例】 画出K4的所有非同构的生成子图。4.1 图的基本概念【例】 设G1,G2,G3,G4均是4阶3条边的无向简单图，则它们之间至少有几个是同构的？4.1 图的基本概念本节小结4.1 图的基本概念 图论是一个重要的数学分支。数学家欧拉1736年发表了关于图论的第一篇论文，解决了著名的哥尼斯堡七桥问题。克希霍夫对电路网络的研究、凯来在有机化学的计算中都应用了树和生成树的概念。以及在民间广为流传的一些游戏问题：例如迷宫问题、棋盘上马的行走路线问题等等。这些古老的问题当时吸引了许多学者的注意，从而在这些问题研究的基础上，又提出了著名的四色猜想和环游世界各国的问题。有趣的图论问题4.1 图的基本概念EvVvii2)deg(一个图中有10个结点，每个结点的度数为6, 图中有多少条边？结点度数总和：6 10=60因为 2e = 60，所以 e = 30.解：4.1 图的基本概念 在任何有向图中,所有结点入度之