《图论第2章 基本概念ppt课件.ppt

《《图论第2章 基本概念ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、[有向图]设V是一个非空有限集，A是V上的二元关系。二元组G=(V,A)称为（有向）图，V中元素称为顶点，A中元素称为弧（有向边）。关系A的关系图就是图G的图解。[自环]A中的自反性图解为环形，称为自环。[多重边]在表达实际问题的图解中可能出现重复的关系定义，称为多重边。2.1图的概念[简单图]不出现自环或多重边图解形状的图称为简单图.未加特别声明时，只讨论简单图。[完全图]任何两个顶点之间都有弧相连的图称为完全图。顶点集为V的完全图GV=(V,VV)。[简单完全图]顶点集为V的完全图GV=(V,VV-IV)。[零图]A=或

2、A

3、=0时，称G为零图。[平凡图]

4、V

5、=1时，称G为平

6、凡图。[图的阶]

7、V

8、称为图的阶。2.1图的概念[子图]G=(V,A)是G=(V,A)的一个子图当且仅当:⑴VV⑵A是V上的二元关系⑶AAG是G的一个子图；若G是G的子图，则G的任何子图也是G的子图；平凡图是任何图的子图。（零图无类似结论）2.1图的概念[生成子图]G=(V,A)是G=(V,A)的一个子图且V=V，则称G是G的一个生成子图或支撑子图。[极大子图]G=(V,A)是G=(V,A)的一个子图，若对u,vV,A必有A，则称G是G的一个极大子图。[导出子图]G=(V,A)，SV且S，则G中以S为顶点集的极大

9、子图称为G中由S导出的子图。[补图]设图G=(V,A)，则~G=(V,VVIVA)称为G=(V,A)的补图。2.1图的概念[图的并]设图G1=(V1,A1)，G2=(V2,A2)，令G=(V,A)，其中V=V1V2，A=A1A2。G称为G1和G2的并图，记作G=G1G2。[图的交]设图G1=(V1,A1)，G2=(V2,A2)，令G=(V,A)，其中V=V1V2，A=A1A2。G称为G1和G2的交图，记作G=G1G2。[图的对称差]设图G1=(V1,A1)，G2=(V2,A2)，令G=(V,A)，其中V=V1V2，A=A1A2。G称为G1和G2的对称差，记作G=G1

10、G2。2.1图的概念[无向图]图G=(V,A)，当A为对称关系时，在图解上用线段替换成对出现的弧，在集合上用E={(u,v)

11、u,vV，,A}替换A，得到无向图的形式，记为G=(V,E)。无向图的各种概念类似于有向图的相关定义。n阶无向完全图记作Kn，其边数=n(n1)/2。图解中既有无向边，又有有向边的图，称为混合图。混合图可以化为有向图求解。2.1图的概念[关联集与邻接集]有向图G=(V,A),viV的正关联集、负关联集、正邻接集和负邻接集分别定义为：Inc+(vi)={ak

12、(vj)(vjVak=A)}Inc(vi)={ak

13、(

14、vj)(vjVak=A)}Adj+(vi)={vj

15、vjV(ak)(ak=A)}(外邻接集)Adj(vi)={vj

16、vjV(ak)(ak=A)}(内邻接集)2.2点和边的关联关系无向图G=(V,E),viV的关联集、邻接集分别定义为：Inc(vi)={ek

17、(vj)(vjVek=(vi,vj)E)}Adj(vi)={vj

18、vjV(ek)(ek=(vi,vj)E)}2.2点和边的关联关系[正负度]有向图G=(V,A)，viV的正度、负度、度分别定义为：Deg+(vi)=

19、Inc+(vi)

20、Deg(vi

21、)=

22、Inc(vi)

23、Deg(vi)=Deg+(vi)+Deg(vi)无向图G=(V,E)，viV的度定义为：Deg(vi)=

24、Inc(vi)

25、对有向图G=(V,A)，有2.2点和边的关联关系[定理2-1]对G=(V,E)，有：对G=(V,A)有同样的结论；[推论1]图中度为奇数的顶点必为偶数个。2.2点和边的关联关系[定义]对无向图G=(V,E)，若其任一顶点的度都为r，则称G为一个r度正则图。[例]n阶完全图是n1度正则图。[推论2]3度正则图中有偶数个顶点。2.2点和边的关联关系图解法具有不唯一性。例：一一对应的两个关系，具有相同的代数性质，在一定意义上可视为同一。2.

26、3同构[同构]图G=(V,A)和G=(V,A)，若存在一一对应映射g:VV，使得对v1,v2V，v1,v2A当且仅当g(v1),g(v2)A，则称G和G同构[isomorphic]。记为:GG[例]寻求判定图同构的一般方法是图论的重要课题之一。2.3同构[自补图]图G=(V,A)，~G是G的补图。若G~G，则称图G是自补的（或是自补图）。[例][讨论]若n阶无向图是自补的，则n=0,1(mod4)。