离散数学CH04图论基本概念

离散数学CH04图论基本概念第1页/共68页内容提要图的基本概念4.1连通图4.34.4图的矩阵表示路和回路4.2第2页/共68页内容提要欧拉图和哈密顿图4.5二部图及匹配4.74.8平面图树4.6第3页/共68页有趣的图论问题能否从河岸或小岛出发，通过每一座桥，且仅通过一次回到原地？问题第4页/共68页

图论是一个重要的数学分支。数学家欧拉1736年发表了关于图论的第一篇论文，解决了著名的哥尼斯堡七桥问题。克希霍夫对电路网络的研究、凯来在有机化学的计算中都应用了树和生成树的概念。以及在民间广为流传的一些游戏问题：例如迷宫问题、棋盘上马的行走路线问题等等。这些古老的问题当时吸引了许多学者的注意，从而在这些问题研究的基础上，又提出了著名的四色猜想和环游世界各国的问题。有趣的图论问题第5页/共68页第6页/共68页第7页/共68页（0，0）（0，3）（3，0）（5，1）（0，1）（1，0）（1，3）（3，3）（5，0）（2，3）（2，0）（0，2）（5，2）（4，3）（4，0）（5，3）图

有趣的图论问题第8页/共68页一个人带着一只狼、一只羊和一捆草要渡河，由于船太小，人做摆渡者一次只能运送一个“乘客”，很显然，如果人不在，狼要吃羊，羊要吃草，问人怎样才能把它们平安地渡过河去？有趣的图论问题第9页/共68页解这是通路问题的一个典型实例。用f表示人，w表示狼，s表示羊，h表示草。集合{f，w，s，h}中能平安在一起的子集有：{f，w，s，h}，{f，w，s}，{f，s，h}，{f，w，h}，{f，w}，{f，s}，{f，h}，{w，h}，{f}，{w}，{s}，{h}。用顶点表示渡河过程中的状态，状态是二元组：第一元素是集合{f，w，s，h}在渡河过程中留在原岸的子集，第二元素是在彼岸的子集，将一次渡河后代表状态变化的顶点间连边，得图。容易看出，一条路径就是一种渡河方案。有趣的图论问题第10页/共68页有趣的图论问题第11页/共68页图可直观地表示离散对象之间的相互关系，研究它们的共性和特性，以便解决具体问题。一个图是由一些结点和连接两结点间的连线组成,至于连线的长短、曲直及结点的位置是无关紧要的.4.1图的基本概念第12页/共68页4.1图的基本概念下面表示的是同一个图第13页/共68页什么是图?可用一句话概括图是用点和线来刻划离散事物集合中的每对事物间以某种方式相联系的数学模型。因为它显得太抽象，不便于理解，所以有必要给出另外的回答。下面便是把图作为代数结构的一个定义。4.1图的基本概念第14页/共68页定义1一个图G定义为一个三元组<V，E，φ>，记作G=<V，E，φ>。其中V是个非空有限集合，它的元素称为结点；E也是个有限集合，其元素称为边，而φ是从E到V中的有序对或无序对的映射。4.1图的基本概念第15页/共68页由定义可知，图G中的每条边都与图中的无序或有序结点对相联系的。若边e∈E与无序结点对（vi，vj）相联系，则φ(e)=（vi，vj），这时边e称为无向边，有时简称为边；若边e∈E与有序结点对<vi，vj>相联系，则φ(e)=<vi，vj>，此时边e称为有向边或弧，vi称为弧e的始结点，vj称为弧e的终结点。4.1图的基本概念第16页/共68页【例4.1】G=V(G),E(G),G

其中：V(G)={a,b,c,d}E(G)={e1,e2,e3,e4}G：G(e1)=(a,b)

G(e2)=(b,c)

G(e3)=(a,c)

G(e4)=(a,a)

试画出G的图形。4.1图的基本概念第17页/共68页【例4.1】

解：G的图形如图所示。4.1图的基本概念第18页/共68页定义2在图G=<V，E>中，如果每条边都是弧，该图称为有向图；若每条边都是无向边，该图G称为无向图；如果有些边是有向边，另一些边是无向边，图G称为混合图。4.1图的基本概念第19页/共68页4.1图的基本概念有向图无向图混合图第20页/共68页定义3在有向图G=<V，E>中，对任意结点v∈V，以v为始结点的弧的条数，称为结点v的出度，记为d+(v)；以v为终结点的弧的条数，称为v的入度，记作d-(v)；结点v的出度与入度之和，称为结点的度数(degree)，记为d(v)，显然d(v)=d+(v)+d-(v)。一个度数为0的结点称为孤立结点（isolatedvertex）。4.1图的基本概念第21页/共68页对于无向图G=<V，E>，结点v∈V的度数等于联结它的边数，也记为d(v)。注意：若v点有环，规定该点度因环而增加2。4.1图的基本概念第22页/共68页对于无向图G=<V，E>，记Δ(G)或Δ=max{d(v)|v∈V}δ(G)或δ=min{d(v)|v∈V}

它们分别称为图G的最大度和最小度。4.1图的基本概念第23页/共68页例4.1图的基本概念第24页/共68页关于无向图中的结点的度，欧拉给出一个定理，这是图论中的第一个定理。定理4.1.1握手定理：图中结点度数的总和等于边数的两倍.一个图中有10个结点，每个结点的度数为6,图中有多少条边？？结点度数总和：610=60因为2e=60，所以e=30.解：4.1图的基本概念第25页/共68页推论：在任何图中,度数为奇数的结点必定是偶数个.下面哪些可以作为一个图的度数列

（或称为可图化的）？V={v1,v2,…,vn}为无向图G的顶点集，称d(v1),d(v2),…,d(vn)为G的度数列4.1图的基本概念第26页/共68页在任何有向图中,所有结点入度之和等于出度之和.定理14.1.24.1图的基本概念证明：在有向图中每一条边对应一个入度和一个出度，为图的入度和出度各增加1。所以，所有结点入度的和等于边数，所有结点出度的和也等于边数。

第27页/共68页【例】求解下列各题:（1）图G的度数列为2，2，3，5，6，则边数m为多少?

（2）图G有12条边，度数为3的顶点有6个，余者度数均小于3，问G至少由几个顶点？

(3)(3,3,3,4),(2,3,4,6,8)能成为图的度数列吗?4.1图的基本概念第28页/共68页【例】证明不存在具有奇数个面且每个面都具有奇数条棱的多面体.4.1图的基本概念第29页/共68页证:用反证法.假设存在这样的多面体,

作无向图G=<V,E>,其中V={v|v为多面体的面},E={(u,v)|u,vVu与v有公共的棱uv}.

根据假设,|V|为奇数且vV,d(v)为奇数.

这与握手定理的推论矛盾.4.1图的基本概念第30页/共68页定义4:若结点vi与vj由一条边(或弧)e所联结，则称结点vi和vj是边(或弧)e的端结点；同时也称结点vi与vj是邻接结点（adjacentvertices），记作viadjvj；否则为非邻接结点，记作vinadjvj；也说边(或弧)e关联vi与vj或说结点vi与vj关联边(或弧)e。关联同一个结点的两条边或弧称为邻接边或弧。而联结一结点与它自身的一条边，称为环。环的方向是无意义的。4.1图的基本概念第31页/共68页定义5在图G=<V，E>中，如果任何两结点间不多于一条边(对于有向图中，任何两结点间不多于一条同向弧)，并且任何结点无环，则图G称为简单图；若两结点间多于一条边(对于有向图中，两结点间多于一条同向弧)图G称为多重图，并把联结两结点之间的多条边或弧，称为平行边或弧，平行边或弧的条数称为重数。4.1图的基本概念第32页/共68页例如，在图(a)中结点a和b之间有两条平行边，结点b和c之间有三条平行边，结点b上有两条平行边，这两条平行边都是环。图(a)不是简单图。在图(b)中结点v1和v2之间有两条平行边。v2和v3之间的两条边，因为方向不同，所以不是平行边。图(b)不是简单图。4.1图的基本概念第33页/共68页定义6设G为n阶（结点的个数）简单无向图，若G中的每个结点都与其余的n–1个结点相邻接，则称G为n阶无向完全图（Completegraph）。记为Kn。在n阶无向完全图中，给每一条边任意确定一个方向，所得到的图称为n阶有向完全图。也记为Kn。今后，将n阶无向完全图和n阶有向完全图统称为n阶完全图。[思考]n阶完全图Kn的边数是多少？4.1图的基本概念第34页/共68页4.1图的基本概念第35页/共68页n阶无向完全图Kn的边数为因为Kn中任意两点间都有边相连，而n

个结点中任取两点的组合数(即总边数)为:

n阶有向完全图的边数为？4.1图的基本概念第36页/共68页定义7在无向图G=<V，E>中，如果每个结点的度是k，即(v)(v∈V→d(v)=k)，则图G称为k度（次）正则图(regular)。对于k度（次）正则图G，Δ(G)=δ(G)=k。4.1图的基本概念正则图边数（由握手定理得）第37页/共68页定义8离散图（Discretegraph）:一个具有n个结点但没有边的图称为离散图(零图)，记为Un。仅由一个孤立点构成的图称为平凡图.4.1图的基本概念第38页/共68页定义9给每条边或弧都赋予权的图G=<V，E>，称为加权图，记为G=<V，E，W>，其中W表示各边之权的集合。加权图在实际中有许多应用，如在输油管系统图中权表示单位时间流经管中的石油数量；在城市街道中，权表示表示通行车辆密度；在航空交通图中，权表示两城市的距离等等。4.1图的基本概念第39页/共68页定义10

给定无向图(或有向图)G1=<V1，E1>和G2=<V2，E2>。若存在双射f：V1V2，使得对任意v，u∈V1，有(u,v)∈E1(f(u),f(v))∈E2，则称G1同构于G2，记为G1≌

G2。显然，两图的同构是相互的，即G1同构于G2，G2同构于G1。4.1图的基本概念G1≌G2第40页/共68页由同构的定义可知，不仅结点之间要具有一一对应关系，而且要求这种对应关系保持结点间的邻接关系。对于有向图的同构还要求保持边的方向。4.1图的基本概念充要条件第41页/共68页一般说来，证明两个图是同构的并非是轻而易举的事情。请证明下面的两个图是同构的。4.1图的基本概念第42页/共68页根据图的同构定义，图同构的必要条件如下：

(1)结点数目相等；

(2)边数相等；

(3)度数相同的结点数目相等。4.1图的基本概念必要条件第43页/共68页但这仅仅是必要条件而不是充分条件。例如，下面的两个图满足上述三个条件，然而并不同构。因为在(a)中度数为3的结点x与两个度数为1的结点邻接，而(b)中度数为3的结点y仅与一个度数为1的结点邻接。寻找一种简单有效的方法来判定图的同构，至今仍是图论中悬而未决的重要课题。4.1图的基本概念第44页/共68页例4.1图的基本概念第45页/共68页例4.1图的基本概念第46页/共68页v1v2v3v4v5v6v1v2v3v4v5v6例4.1图的基本概念第47页/共68页例4.1图的基本概念第48页/共68页例4.1图的基本概念第49页/共68页例4.1图的基本概念第50页/共68页例4.1图的基本概念第51页/共68页例(续)4.1图的基本概念第52页/共68页例(续)4.1图的基本概念第53页/共68页例(续)4.1图的基本概念第54页/共68页例(续)4.1图的基本概念第55页/共68页例(续)4.1图的基本概念第56页/共68页补图、子图和生成子图定义4.11设G=V,E是n阶简单无向图，G中的所有结点和所有能使G成为完全图的添加边组成的图称为图G的相对于完全图的补图，简称为G的补图。记为。若G≌，则称G为自补图。4.1图的基本概念第57页/共68页4.1图的基本概念在图中，(b)是(a)的补图，(a)与(b)同构，所以(a)是自补图。第58页/共68页？解G是一个有15条边的简单图，有13条边，请问G

中有多少个结点?共有15+13=28条边，是一个完全图，它的结点数与G相同，设为n，则n(n-1)/2=28n=8问题4.1图的基本概念第59页/共68页定义4.12设G=V,E