离散2-8-图概念&回路 for 16w

《离散2-8-图概念&回路 for 16w》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、主要内容：•图的基本概念¢图的定义¢顶点度数¢子图¢完全图和补图¢图同构•图的通路回路¢基本概念¢性质-吴扬扬-1§11.1图的基本概念4.完全图和补图(1)•完全图：¢设G=是无向简单图，

2、V

3、=n,若G中任何顶点与其余n-1个顶点都邻接,则称G为无向完全图,记作K。n¢设G=是有向简单图，

4、V

5、=n,若∀u∀v(u∈V∧v∈V∧u≠v→∈E∧∈E),则称G为有向完全图。aa讨论例6和P219例题bd例7：3顶点和4顶点的有向完全图：bc¢完全图的边数：cn个顶点无向完全图边数=1+2+3+…+(n-1)=n(n-

6、1)/2n个顶点的有向完全图边数-吴扬扬=n(n-1-）2§11.1图的基本概念4.完全图和补图(2)•补图：设G=是简单图，

7、V

8、=n，H=，若E∩E’=∅,且E∪E’=E(K),则称H是G的补图，记作：H=G.n例8：K的边集naaaabebebebecdcdcdcdaaaabcbcbcbc-吴扬扬-3§11.1图的基本概念5.图的同构•图同构:设G=,G=,若存在双射函数f:V→V,11122212使得∀u,v∈V,[u,v]∈Eiff[f(u),f(v)]∈E,且[u,v]与[f(u),f(v)]112的重

9、数相等，则称G与G同构，记作G≅G.(u,v)或1212a1例6:下列两个图同构：eb25∵f:{a,b,c,d,e}→{1,2,3,4,5},dc34f(a)=1,f(b)=3,f(c)=5,f(d)=2,f(e)=41adf双射且(a,b)与(f(a),f(b))=(1,3)重数相等,…4•同构必要条件：(1)

10、V1

11、=

12、V2

13、;(2)

14、E1

15、=

16、E2

17、;bc23(3)deg(v)=deg(v),且度数相同的顶点数相等。∑i∑ivi∈V1vi∈V2P223例题-吴扬扬-4§11.2通路回路和连通性1.通路和回路(1)例2»•定义:设G=

18、E>,v,v,…,v∈V,e,e,…,e∈E,01n12n其中e关联于v和v(i=1,2,…,n),ii-1i称veve…ev为顶点v到顶点v的通路，0112nn0n称v和v分别为该通路的起点和终点，0n称通路上边的数目为该通路的长度，若v=v,则称该通路为回路。0n若通路(回路)的所有边各不相同，则称之为简单通路(回路)。若通路(回路)的所有顶点各不相同，则称之为基本通路(回路)。例1：V1bV2vcvdvVa234基本通(回)路一定是5vcvdvevec2342简单通(回)路,fVvdvcvVd3432反之不一定成立。54§11.2通路回路和连通性1.

19、通路和回路(2)«通路定义通路性质»例2：v2e5v3ee91ev1e6e3e84e2ve7v54简单通路基本通路简单回路基本回路回路v1e2v5e3v2v1e2v5e3v2e1v1v1e2v5e3v2e4v5e3v2e6v4v4e8v3e9v3e5v2e4v5e3v2e6v4基本通(回)路一定是简单通(回)路,简单回路反之不一定成立。-吴扬扬-6§11.2通路回路和连通性1.通路和回路(3)推论»•性质:¢定理11.2.1设G=,

20、V

21、=n,u,v∈V,若存在从u到v的通路，则存在一条从u到v的长度不超过n-1的通路。证明:设veve…ev为顶

22、点u到顶点v的通路(v=u,v=v),长为m,0112mm0m若m≤n-1,则veve…ev为长度不超过n-1的从u到v的通路；0112mm若m>n-1,则m+1>n,veve…ev中至少有一个顶点重复出现，0112mm不妨设v=v(0≤i

23、定理¢推论11.2.1设G=,

24、V

25、=n,u,v∈V,若存在从u到v的通路,则存在一条从u到v的长度不超过n-1的基本通路。¢定理11.2.2设G=,

26、V

27、=n,u∈V,若存在从u到u的回路，则存在一条从u到u的长度不超过n的回路。¢推论11.2.2设G=,

28、V

29、=n,u∈V,若存在从u到u的回路，则存在一条从u到u的长度不超过n的基本回路。•设G=,

30、V

31、=n,则(1)任何基本通路的长度均不大于n-1。(2)任何基本回路的长度均不大于n。对简单通路(回路)是否也成立,为什么?-吴扬扬-8作业：习题11.15,7(任

32、选)，习题11.24实践项目4(附加题)：编写程序，实现求相容关系