图论 PPT G1基本概念.ppt

《图论 PPT G1基本概念.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、图的基本概念1LuChaojun,SJTU图论的研究对象世界由事物组成,事物之间有联系.图可以直观地描述事物及其间联系.用结点表示事物用边表示事物间联系可见,图模型几乎可用于任何领域.图论(graphtheory)就是以这种结点和边构成的图为研究对象.2LuChaojun,SJTU图的例子七桥问题红楼家谱乙烷LuChaojun,SJTU3图的定义定义:图G是二元组(V,E),其中V是非空顶点集合E是边集合,每条边与V中两个顶点(可相同)相关联.若边e与顶点u,v关联,称u和v相邻,亦称e连接u,v.对任意图G,约定用V(G)和E(G)表示该图的顶点集和边集.LuChaoj

2、un,SJTU4graphvertexedgeadjacent图的画法图可以画出来:顶点画成点,边画成连接顶点的曲线.例如下图G可画成右边两种样子:V(G){A,B,C}E(G){eAB,eBC,eAC}有限图vs无限图有限图:V和E是有限集合无限图:V或E是无限集合我们只讨论有限图:V{v1,v2,…,vn}E{e1,e2,…,em}以后不加说明时,都假定图有n个结点,m条边.若

3、V(G)

4、n,称G是n阶图.LuChaojun,SJTU6无向图vs有向图无向边:边无方向,可视为顶点的无序对.记作e{u,v}uvvu,u和v称为e的端点.有向边:边有

5、方向,可视为顶点的有序对.记作e(u,v),u称始点,v称终点.无向图:E中都是无向边.以后不加说明的都是无向图.有向图:E中都是有向边.LuChaojun,SJTU7undirectededgedirectededgeendpointinitialvertexterminalvertexundirectedgraphdirectedgraph简单图vs多重图环:所关联的两个顶点重合的边.重边:关联两个顶点的多条边.多重图:有重边的图.简单图:无重边无环的无向图.完全图:任意两个不同顶点都相邻的简单图.n个结点的完全图记作Kn.空图/零图:无边的简单图,记作Nn.LuC

6、haojun,SJTU8loopmultipleedgemultigraphsimplegraphnull/emptygraphcompletegraph顶点的度顶点的度(degree):与顶点v关联的边数.记作dG(v)或d(v).环对d(v)的贡献为2.对有向图:d(v)d+(v)+d(v)出度(out-degree)d+(v)以v为始点的边数入度(in-degree)d(v)以v为终点的边数环对出度,入度各贡献1.例如:Kn中各顶点的度都为n1.LuChaojun,SJTU9有关度的若干术语孤立点:度为0的顶点悬点:度为1的顶点悬边:与悬点关联的边奇点:

7、度为奇数的顶点偶点:度为偶数的顶点正则图:各顶点度相同若度为k,称为k-正则图.例如:Kn是(n1)-正则图握手定理及其推论定理[握手定理]:图G(V,E),若

8、E

9、m.则推论:G中奇点数目必为偶数.推论:Kn的边数为n(n1)2.LuChaojun,SJTU11二部图定义:设G(V,E)是简单图.若V可划分为不相交的非空集合V1和V2,且E中所有边都连接V1中的一个顶点和V2中的一个顶点,则称G为二部图(bipartitegraph)或偶图.若V1中任一顶点都与V2中每个顶点相邻,则称为完全二部图.若

10、V1

11、m,

12、V2

13、n,则完全二部图记为Km,n子图定

14、义:给定G(V,E),如果G(V,E)满足VV,EE,则称G是G的子图(subgraph),记作GG.如果GG,则称G是G的真子图,记作GG;平凡子图:G和Nn如果VV,则称G是G的支撑(spanning)子图或生成子图;如果E包含了G在V中的所有边,则称G是G的导出(induced)子图.13LuChaojun,SJTU例:子图下图中G和G都是G的子图G是G的导出子图,而G不是G是G的支撑子图,而G不是LuChaojun,SJTU14图的运算定义G1(V1,E1)和G2(V2,E2)的并:G1G2(V1

15、V2,E1E2)交:G1G2(V1V2,E1E2)对称差:G1G2(V1V2,E1E2)(V1V2,(E1E2)(E2E1))15LuChaojun,SJTU图的运算(续)若G2是G1的子图,则定义差:G1G2(V1,E1E2)n阶简单图G的补图G:KnG从G中删去顶点v及其关联的边:Gv显然:Gv是G的导出子图从G中删去边e:Ge显然:Ge是G的支撑子图向G中增加边eijvivj:GeijLuChaojun,SJTU16图的同构定义:给定两个图G1(V1,E1)和G2(V2