图论 第1章 图的基本概念.pdf

《图论 第1章 图的基本概念.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第一章：图的基本概念杨帆江苏科技大学数理学院第一章：图的基本概念图的定义与基本术语同构途径(way)和道路(path)图的连通性图的运算图的概念图论中的图是由若干给定的顶点及连接两顶点的边所构成的图形。这种图形通常用来描述某些事物之间的某种特定关系，用顶点代表事物，用边表示相应两个事物间的某种关系。哥尼斯堡七桥问题图论起源于著名的哥尼斯堡七桥问题:哥尼斯堡市跨越河的两岸，河中心有两个小岛。小岛与河的两岸有七条桥连接。在所有桥都只走一遍的前提下，如何才能把这个地方所有的桥都走遍？哥尼斯堡七桥问题在任何顶点出发，必须从一条边进，从另一条边出一进一出，每个

2、顶点相关联的边必须为偶数。莱昂哈德·欧拉在1735年圆满地解决了这个问题，证明七桥问题无解，同时，欧拉还给出了任意一种河-桥图能否全部走一次的判定法则，以及怎样快速找到所要求的路线。这些解析，最后发展成为了数学中的图论。图的定义二元组定义：G=(V,E)V是顶点集，E是边集E的元素是一个二元组数对，用(x,y表示，)x,y∈VG=(V,E)1V={v,v,v,v,v}12345E={e,e,e,e,e,e,e}1234567e=(v,v),e=(v,v),112223e=(v,v),e=(v,v),334424e=(v,v),e=(v,v),514645e=(v,

3、v)715图的基本术语(1)阶：图G的顶点集合V的大小称为图G的阶没有任何边的图称为空图，记作Φ。只有一个顶点的图称为平凡图(trivialgraph)。关联与邻接：点与点的邻接(adjacent)点与边的关联(incident)两个顶点之间有边相连，则两个顶点邻接，并且通过这条边关联。重边：连接同一对顶点的边数大于1环：顶点通过同一条边与自己关联图的基本术语(2)多重图：允许重边，又允许有环的图简单图：没有环及多重边的图有向图/无向图：每条边都规定了方向的图称为有向图，而边没有方向的图为无向图。有限图/无限图：顶点集合和边集合都是有限集合称

4、为有限图，否则称为无限图。例题证明：在任意六人中必存在三人，要么都相识，要么都不相识。证明构造图。六个人={a,b,c,d,e,f}边集：两人认识，则代表两人的顶点之间连一条红边，否则连一条绿边。考虑某点，不妨设为f，至少有3条边同色（不妨设为红色）。设这三条同色边为fa，fb，fc。考虑三角形abc。1.abc中含红边（设为bc），则fbc为一同色三角形；2.abc不含红边，则abc为一同色三角形（绿色）。同构G1和G2的顶点和边都一一对应，且连接关系完全相同，只是顶点和边的标号不同，则G1和G2是同构的。同构关系实际是一种等价关系。完全图完全图：每对不同的顶

5、点都有边相连n阶完全图记作Kn共有C2=1n(n−1条边)n2补图：设G为简单图，而H是一个以V(G)为顶点集，且顶点在H中邻接当且仅当它们在G中不邻接，则称H为G的补图，记作H=GGH竞赛图定义：完全图的定向图称为竞赛图。举例：n=1，n=2，n=3二部图(bipartitegraph)定义：设V1和V2是G的顶点子集，其中VV=V(G),VV=Φ，且G中每一条边1212的一个端点在V中，另一个端点在V中，则12称G为二部图，记作G=(V,V;E)12分划(V,V)称为图G的二分划。12完全二部图对于二部图G，如果V中的顶点与V中的每12个顶点都邻接

6、，则称为完全二部图。若V=m,V=n，则完全二部图记作K。12m,nPetersen图图习题1.2.3pp.13证明：下列三个无向图都与Pertersen图同构。图的基本术语(3)顶点的度：与该顶点相关联的边的数目记作deg(v)，或简记作d(v)；度为零的顶点称为孤点；度为1的顶点称为悬挂点；对于有向图，有出度和入度之分；奇顶点和偶顶点；计算有环的顶点，环边计两次.图G的最大度:∆(G)=max{d(v)

7、v∈V(G)}图G的最小度：δ(G)=min{d(v)

8、v∈V(G)}图的基本术语(4)正则图：图的每个顶点的度都相同每个点的度均为k的正

9、则图，称为k-正则图0-正则图1-正则图2-正则图3-正则图握手定理顶点的度与边的关系：∑deg(v)=2Ev∈Vd(v)=2,d(v)=4,d(v)=3,123d(v)=3,d(v)=445∑d(vi)=(2+4+3+3+4)=16vE=8在任意图G中，度为奇数的顶点个数是偶数∑d(v)+∑d(v)=2Ev∈V1v∈V2子图若V(H)⊆V(G),E(H)⊆E(G)，且H中边的重数不超过G，则H称为G的子图，记作H⊆G若以下条件有一项成立，则H称为G的真子图。(1)V(H)⊂V(G);(2)E(H)⊂E(G);(