第四部分 图论 主要内容 图的基本概念：图、通路和回路、图的连通性、图的矩阵表示 图的可行遍性：欧拉图、哈密顿图、带权图及其应用

Presentation on theme: "第四部分 图论 主要内容 图的基本概念：图、通路和回路、图的连通性、图的矩阵表示 图的可行遍性：欧拉图、哈密顿图、带权图及其应用"— Presentation transcript:

1 第四部分 图论 主要内容 图的基本概念：图、通路和回路、图的连通性、图的矩阵表示 图的可行遍性：欧拉图、哈密顿图、带权图及其应用
树：无向树及其性质、生成树与最小生成树、根树及其应用

2

3 第十四章 图的基本概念

4 第一节 图

5 E = {(v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5)}
则G = <V,E>为一无向图，用图1表示G 图1

6

7

8 （7）顶点之间的相邻与邻接关系 设Ｇ＝<V,E>为无向图，vi,vj∈V,ek,el ∈E.若存在et ∈E,使得et=(vi,vj),则称vi与vj是相邻的。若ek与el至少有一个公共端点，则称ek与el是相邻的。 （8）标定图与非标定图：顶点或边用字母标定的图为标定图，否则为非标定图。 （9）基图：将有向图各有向边均改成无向边后的无向图称为原来图的基图。

9

10

11

12 （4）+(D)=max{ d+(v)| vV(G)}
+(D) =min{ d+(v)| vV(G)} (D) )=max{ d-(v)| vV(G)} (D) =min{ d-(v)| vV(G)} 分别称为D的最大出度，最小出度，最大入度，最小入度。 （5）奇顶点度：度为奇数的顶点 （6）偶度顶点：度为偶数的顶点 （7）悬挂顶点：度数为1的顶点

13

14

15

16

17

18

19

20

21

22 第二节 通路与回路

23

24

25 第三节 图的连通性

26

27

28

29 在上图中，{e1,e2}，{e1,e3,e5,e6}，{e8}等是边割集，e8是桥，{e7,e9,e5,e6}是边割集吗？

30

31

32

33

34

35

36 第四节 图的矩阵表示 (5)第i行元素和为零，当且仅当该vi是孤立点 P288图14.14 （每条边关联两个顶点）
（M（G）的第i行元素之和为vi的度数） （各顶点的度数之和等于边数的两倍） (5)第i行元素和为零，当且仅当该vi是孤立点 P284 图例

37 P288图14.15 （每列和为零，说明每条边既是始点也是终点） （M(D)中所有元素和为零) P285 图例

38 P289图14.16 (第i行为vi的出度） (第j行为vj的入度） (A（D）中所有元素之和） (A（D）中主对角线元素之和）

39

40

41

42

43 第十四章 习题课

44