资源描述：
《图论图的基本概念 .doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第一章：图的基本概念杨帆江苏科技大学数理学院第一章：图的基本概念*图的定义与基本术语*同构*途径(way)和道路(path)・图的连通性*图的运算图的概念*图论中的图是由若干给定的顶点及连接两顶点的边所构成的图形。*这种图形通常用来描述某些事物之间的某种特定关系，用顶点代表事物，用边表示相应两个事物间的某种关系。哥尼斯堡七桥问题•图论起源于著名的哥尼斯堡七桥问题：*哥尼斯堡市跨越河的两岸，河中心有两个小岛。小岛与河的两岸有七条桥连接。在所有桥都只走一遍的前提下，如何才能把这个地方所有的桥都走遍？哥尼斯堡七桥问题•在
2、任何顶点出发，必须从一条边进，从另一条边出•一进一出，每个顶点相关联的边必须为偶数。*莱昂哈德■欧拉在1735年圆满地解决了这个问题，证明七桥问题无解，同时，欧拉还给出了任意一种河-桥图能否全部走一次的判定法则，以及怎样快速找到所要求的路线。这些解析，最后发展成为了数学中岛图论。图的定义*二元组定义：g=（v.e）是顶点集，E是边集的元素是一个二元组数对，用0，｝，表示，x，yeVGX=(V,E)V=KV2,v3,v4,V5}E=ei，〜A,e5,e6>e7)ei=(V1,=(V2,v3),A=(V3,V4)，q=
3、(v2,v4)，^5=(VP%)，％=(V4,V5)，ei=(VPV5)图的基本术语(1)*阶：图G的顶点集合V的大小称为图G的阶*没有任何边的图称为空图，记作0。•只有一个顶点的图称为平凡图(trivialgraph)。・关联与邻接：•点与点的邻接(adjacent)*点与边的关联(incident)*两个顶点之间有边相连，则两个顶点邻接，并且通过这条边关联。*重边：连接同一对顶点的边数大于1*环：顶点通过同一条边与自己关联图的基本术语(2)*多重图：允许重边，又允许有环的图*简单图：没有环及多重边的图*有向图/
4、无向图：*每条边都规定了方向的图称为有向图，而边没有方向的图为无向图。*有限图/无限图：*顶点集合和边集合都是有限集合称为有限图，否则称为无限图。例题*证明：在任意六人中必存在三人，要么都相识，要么都不相识。*证明构造图。六个人={a,b,c,d7e,f}边集：两人认识，则代表两人的顶点之间连一条红边，否则连一条绿边。考虑某点，不妨设为f，至少有3条边同色（不妨设为红色）。设这三条同色边为fa，fb,fc。考虑三角形abc。l.abc中含红边（设为be），则fbc为一同色三角形；2.abc不含红边，则abc为一同色
5、三角形（绿色）。同构*G1和G2的顶点和边都一一对应，且连接关系完全相同，只是顶点和边的标号不同，则G1和G2是同构的。u3*同构关系实际是一种等价关系。完全图*完全图：每对不同的顶点都有边相连*行阶完全图记作尺,；•共有C,卜丄+-1牽i*补图：设G为简单图，而H是一个以V(G)为顶点集，且顶点在H中邻接当且仅当它们在中不邻接，则称H为G的补图，记作h=GGH竞赛图*定义：完全图的定向图称为竞赛图。參举｛列：n=l，n=2,n=3完全二部图*对于二部图G，如果V；中的顶点与V2中的每个顶点都邻接，则称为完全二部图
6、。•若=，则完全二部图记作么,，,7。Petersen图•图*习题1.2-3pp-13证明：下列三个无向图都与Pertersen图同构。图的基本术语(3)・顶点的度：与该顶点相关联的边的数目•记作deg(v),或简记作d(v)；*度为零的顶点称为孤点；*度为1的顶点称为悬挂点；*对于有向图，有出度和入度之分；*奇顶点和偶顶点；*计算有环的顶点，环边计两次.•图G的最大度：A(G)=max{t/(v)
7、vGV(G)}・图G的最小度:3(G)=min{a(v)
8、vgV(G)}图的基本术语(4)*正则图：图的每个顶点的度
9、都相同*每个点的度均为k的正则图，称为k-正则图0-正则图1-正则图2-正则图3-正则图握手定理•顶点的度与边的关系：zde§(v)=2
10、£
11、veV=2，d(v2)=4，a(v3)=3，J(v4)=3,t/(v5)=4[a(vJ=(2+4+3+3+4)=16'
12、e
13、=8*在任意图G中，度为奇数的顶点个数是偶数2>(v)+J>(v)=2
14、£
15、veVivgV2子图•若V(H)cV(G),E(H)cE(G),且H中边的重数不超过G，则H称为G的子图，记作H^G*若以下条件有一项成立，则H称为G的真子图。•(l)V(H)(
16、zV(G);•(2)£(H)(zE(G);•(3)H中至少有一条边的重数小于G中对应边重数子图•生成子图(Spanninggraph),又称支撑子图。*满足V(H)=V(G)，E(H)(=E(G)的真子图点导出子图*点导出子图(inducedgraph):*设V'qV(G)，以V'为顶点集，且两端点都在V'中的边的全体为边集所组成的子图，称为由V'导出的G的
