《离散数学课件》1-2图基本概念

1/81离散数学集合论数理逻辑图论代数2/81一个人要把他带的一条狗，一只羊和一袋菜用一条小船摆渡到河的对岸。每次摆渡这个人只能将狗、羊和菜之一带过去。但是，不能把狗和羊，也不能把羊和菜单独的留在河的同一岸。V={被允许出现的局面}E={顶点之间的关系|一次摆渡能够从一局面变为另一局面}3/819.1图的基本概念(一)有向图(二)无向图(三)图的同构(四)完全图(五)握手定理顶点集、边集多重边、自环、孤立点简单图/多重图图的同构映射子图、生成子图、补图有向完全图顶点的度数入度、出度有向图G=(V,E)定义1设V是一个非空有限集合，E是V上的二元关系。则称有序二元组G=(V,E)是一个有向图，并称V为顶点集，E为边集。

其中，边集E为有序二元组所构成的集合。

5/81例设V={2，3，4，5，6}，E={(x,y)|x整除y},即

E={(2,2),(2,4),(2,6),(3,3),(3,6),(4,4),(5,5),(6,6)}

画出有向图G=(V,E)246356/81有向图G=(V,E):边、孤立点、自环若(a,b)∊E，称(a,b)为图G中一条边。设(a,b)∊E，称边(a,b)关联于顶点a和b，顶点a称为该边的始点，顶点b称为该边的终点，并称a和b相邻。若一个顶点没有任何边关联于它，称该顶点为孤立点。若一条边的始点和终点是同一顶点，称该边为自环。246357/81多重集约定一个多重集是一些对象的总体，但这些对象不必不同。如:

{a,a,a,b,b,c}{a,a,a}

{a,b,c}一个元素的重数是它在该多重集里出现的次数集合仅是多重集中重数仅为0和1的特殊情况8/81无向图G=(V,E)定义2设V是一个非空有限集合，E是一个多重集合，E的元素是仅含V中两个元素的多重子集。则称二元组G=(V,E)是一个无向图，例1(p136)

图G=(V,E)，

V={v1,v2,v3,v4,v5}，

E={{v1,v2},{v2,v3},

{v3,v3},{v3,v4},{v2,v4},{v4,v5},{v2,v5},{v2,v5}}9/81无向图G=(V,E)

:边、自环、孤立点{v,u}∈E,称{v,u}是G中一条边。称V为顶点集，称E为边集。设e={v,u}是G中的一条边，v和u称为边e的二个端点，称边e关联

v和u，也称v邻接到u，或u邻接于v。若u=v，称{v,u}为G中的自环。对于任意的u∈

V，若不存在任何边关联u，说顶点u是孤立点。边和点：关联点和点：相邻边和边：相邻10/81多重图、简单图一个图，有向图或无向图，其边集若是多重集，称这样的图为多重图，也简称图。若一个图，也就是多重图，其重数大于1的边称为多重边，又称有这样边的图为有多重边的图。称一个没有多重边，没有自环，也没有孤立点的图为简单图。若不声明是简单图，就泛指图或多重图。11/81图的画法不同、实质相同12/81图的画法不同、实质相同13/81图的同构

G1≅G2定义3设G1=(V1,E1)和G2=(V2,E2)是两个图，若存在函数f:V1→V2，f是双射，且若定义函数g:E1→E2，对于任意的{v1,v1’}∈E1，g({v1,v1’})={f(v1),f(v1’)}，g也是一个双射。则称图G1和图G2是同构的两个图，记为

G1≅G2，并称f为图的同构映射，。14/81完全图Kn一个简单图，若每一对不同的顶点之间都有一条边相连，这样的图称为完全图。一个有n(∈N)个顶点的完全图在同构的意义下是唯一的，记为Kn。15/81子图、真子图、生成子图定义4设G=(V,E),H=(V’,E’)是两个图。若V’⊆V且E’⊆E，则说H是G的子图。若V’V或E’E，则说H是G的真子图。若H是G的子图且V’=V，说H是G的生成子图。⊂≠⊂≠K4的真子图K4的生成子图例:K416/81例

K4的所有的生成子图有多少？64个！17/81例K4所有互不同构的生成子图有多少？11个！18/81补图设G=(V,E)是一个图，它没有自环和多重边。令=(V,E’)，其中E’={{u,v}│u≠v，u,v∊V，{u,v}∉E}称为G的补图。GG例下面两图互为补图：19/81自互补图一个无向简单图如果同构于它的补图，则称这个图为自互补图。例4个顶点的自互补图：20/81例

试画出五个顶点的自互补图21/81顶点的度数设G=(V,E)是一个图，对于每一个v∊V，称关联顶点v的边数为顶点v的度数，记为d(v)。23322/81定理1(握手定理)设G=(V,E)是一个图，对于每一个v∊V，d(v)为顶点v的度数。则:∑d(v)=2|E|v∊V23323/81推论任何一个无向图，度数为奇数的顶点有偶数个。证明：设G=(V,E)是一个无向图。令

V1={v∊V│d(v)是奇数}，

V2={v∊V│d(v)是偶数}，显然{V1，V2}是V的一个划分。

∑d(v)v∊V1∑d(v)=v∊V∑d(v)v∊V2+∑d(v)v∊V∑d(v)=v∊V1∑d(v)v∊V2－∵∴容易说明，等式右端是偶数，而等式左端是|V1|个奇数相加，故|V1|为偶数。24/81例2有9个人在一起打乒乓球，已知他们每人至少和其中另外3个人各打过一场球，则一定有一个人不止和3个人打过球。用图论语言解释这件事。解：设v1，v2，…，v9代表这9个人，建立顶点集

V={v1，v2，…，v9}，对于其中的任意两个人vi和vj（i≠j），若vi和vj打过一场球，则{vi,vj}∊E，得到边集E，则我们有了一个无向图G=（V，E）。若每一个人仅和其余3个人各打过一场球，则d(vi)=3，而此时图G的奇数度的顶点是9个，即是奇数个，与推论矛盾。矛盾说明，至少有一个人vi，d(vi)≥4。25/81例(3,3,2,3)与(5,2,3,1,4)能成为图的度数序列吗?为什么?解:不能，因为度数为奇数的顶点数目不是偶数。26/81例已知图G中有10条边,4个3度顶点,其余顶点的度数均小于等于2,问G中至少有多少个顶点?为什么?解:图G中顶点度数之和为2×10=20，而已有4个顶点的度数之和为4×3=12，还剩下8度，按题意，还需至少4个顶点，所以图G至少有8个顶点。27/81例3(p138)两无向图是否同构？abcdegf1234567答：图（a）中两个3度顶点之间没有边，而图（b）中两个3度顶点之间有边，故不存在两图之间的同构映射。（a）（b）28/81同构图的顶点度设G1=(V1,E1)和G2=(V2,E2)同构，即存在同构映射f:V1→V2，则对于任意的vi∊V1，一定有

d(vi)=d(f(vi))

任意两个同构的无向图，一定有一个同样的顶点度序列。顶点度序列是一组按大小排列的正整数，每一个数对应某一个顶点的度数。29/81例考察两个不同构的简单无向图。

每一个图都仅有6个顶点，且每个顶点都均是3度，并指出这两个图为什么不同构。反证法：假使两图同构。不妨假设红点对应红点,则3个绿点对应3个绿点,剩下的2个蓝点对应2个蓝点，而在左图中2个蓝点间无边，而在右图中2个蓝点间有边。矛盾！30/81有向完全图如果一个有向图去掉边的方向以后所得无向图是完全图，则称为有向完全图。31/81出度、入度定义5设G=(V,E)是一个有向图，v∊V，称以v为始点的边的条数为v的出度，记为

d出(v)或d+(v)；称以v为终点的边的条数为v的入度，记为d入(v)或d—(v)。32/81定理2∑

d出(v)=∑d入(v)=|E|v∊Vv∊V设G=(V,E)是一个有向图，则33/81小结

图的基本概念(一)有向图(二)无向图(三)图的同构(四)完全图(五)握手定理顶点集、边集多重边、自环、孤立点简单图/多重图图的同构映射子图、生成子图、补图有向完全图顶点的度数入度、出度34/819.2图中的通路、图的连通性和图的矩阵表示(一)通路(二)简单通路、初等通路(三)简单回路、初等回路(四)连通图(五)单侧连通、强连通(六)关联矩阵、邻接矩阵、可达矩阵35/81通路:顶点序列称顶点序列(vi1，vi2，…，vis)为图G中的一条通路，若vij∊V，1≤j≤s，且(vij,vi(j+1))∊E，其中1≤j≤s-1。例

(v1,v2,v3)为通路(v1,v3,v4,v6,v7)为通路36/81通路:边序列称边序列(ei1，ei2，…，eit)为图G中的一条通路，若eij∊E，1≤j≤t，且适当的规定边eij(1≤j≤t)中的两个端点，让其中一个为起点，一个为终点，可以使eij的终点与ei(j+1)的起点是同一顶点，其中1≤j≤t-1。例

(e2,e3)为通路(e1,e5,e8,e12)为通路37/81通路的长度、顶点间的距离称一条通路经过的边的多少为这条通路的长度。称两个顶点间的最短通路的长度为该两个顶点间的距离。例

(v1,v2,v3)为通路，长度为2。

(v1,v3,v4,v6,v7)为通路,长度为4。38/81简单通路、初等通路称一条通路为简单通路,如果它的每一条边都不重复出现。称一条通路为初等通路,如果它的每一个顶点都不重复出现.例

(v1,v2,v5,v6,v4,v6,v8,v7)为简单通路,但非初等通路.39/81回路、简单回路、初等回路（圈）设(vi1，vi2，…，vis)是图G=(V,E)中的一条通路，若vi1=vis，则这条通路为G中的一条回路。若一个回路中边不重复出现，则称之为简单回路。若一个回路中顶点不重复出现，则称之为初等回路，又称之为圈。40/81例回路、简单回路、初等回路（圈）

(v2,v4,v5,v6,v4,v3,v2)为一个简单回路，但不是圈41/81定理1G=(V,E)是一个无向图。v1，v2∊V，若G中存在一条v1

到v2的通路，则一定存在一条从v1到v2的初等通路。42/81定理1的证明设S={n∊N│G中存在一条长为n的从v1

到v2的通路}由题知S≠Ø，又S⊆N，由自然数集的非空子集有最小数，可设m∊S，对于任意n∊S，有m≤

n。设(v1=vi0，vi1，…，vi(m-1)，v2=vim)是G中一条从v1到v2长度为m的通路，则这条通路即是初等通路。否则，若它不是初等通路，一定存在两个相同的顶点vij和vik(0≤j<k≤m)，使得vij=vik。于是(vi0，…，vij

，vi(k+1)，…，vim)也是中一条从v1到v2的通路，且长度为m-k+j(<m)，这与m最小矛盾。43/81推论G=(V,E)是一个无向图，|V|=n。如果G中存在一条从v1到v2的通路，那么一定存在一条从v1到v2的长度小于等于n-1的通路。恰有n个顶点的图G中的初等通路最长为n-1。44/81连通图定义G=(V,E)是一个无向图，若G中任意两个不同的顶点之间在G中都有通路存在，则称G是一个连通图，否则称G为不连通图。45/81有向连通图定义称一个有向图是连通的，如果去掉边的方向后所得无向图是连通的。46/81单侧连通一个有向图任意二点之间都有单向通路，则称为单侧连通图。例连通、非单侧连通单侧连通47/81强连通如果一个有向图任意二点之间都有双向的通路，则称为强连通图。例单侧连通非强连通强连通连通性判别定理(强连通判别法)

D强连通当且仅当D中存在经过每个顶点至少一次的回路定理(单向连通判别法)

D单向连通当且仅当D中存在经过每个顶点至少一次的通路

48(1)(2)(3)例下图(1)强连通,(2)单连通,(3)弱连通49/81连通分支设G为一个无向图,R是G中顶点之间的连通关系,按着R可将V(G)划分成k(k≥1)个等价类,记成V1,V2,···,Vk,称由它们导出的子图G[V1],G[V2],…,G[Vk]为G的连通分支。其个数记作p(G)=k.50/81例连通分支连通分支数为1连通分支数为451点割集

记Gv:从G中删除v及关联的边

GV:从G中删除V中所有的顶点及关联的边

Ge:从G中删除e

GE:从G中删除E中所有边定义设无向图G=<V,E>,VV,若p(GV)>p(G)且VV,p(GV)=p(G),则称V为G的点割集.若{v}为点割集,则称v为割点.52点割集(续)例{v1,v4},{v6}是点割集,v6是割点.{v2,v5}是点割集吗？53边割集定义设无向图G=<V,E>,EE,若p(GE)>p(G)且EE,p(GE)=p(G),则称E为G的边割集.若{e}为边割集,则称e为割边或桥.图中，{e1,e2}，{e1,e3,e5,e6}，{e8}等是边割集，e8是桥，{e7,e9,e5,e6}是边割集吗？54/81例G=(V,E)是一个简单图，试证明若G不连通，则G的补图G一定连通。证明：因为G不连通，则G可以分为若干连通子图：（V1，E1），---，（Vn，En）根据补图构造过程知，在G的补图中，

V1中每个顶点与其它顶点集V2，---，Vn中顶点有边相连。这样，在G的补图中，有分别属于两个顶点子集Vi与Vj中的任意两个顶点之间有边直接相连，属于同一个顶点子集Vi的任意两个顶点借助顶点子集Vj的任意一个顶点连通。所以，根据连通的定义知：G的补图一定连通。图的矩阵表示关联矩阵（无向图、有向图）邻接矩阵（无向图、有向图）有向图的可达矩阵5556/81无向图的关联矩阵设G=(V,E)是一个无向图，|V|=n，|E|=m，V={v1,v2,⋯,vn}，E={e1,e2,⋯,em}，则有n×m阶矩阵，

M(G)=(mij)n×m其中:

称M(G)=(mij)n×m为图G的关联矩阵。mij=1如顶点vi与边ei关联0如顶点vi与边ei关联57/81例

e1e2e3e4e5e6e7e8

v1

11101000

v2

10010000

v3

00110011v4

00001101v5

01000110

M(G)=特点：1、行和为度数2、列和为23、所有元素的和为总

度数4、平行边列相同有向图的关联矩阵58定义设无环有向图D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},令

则称(mij)nm为D的关联矩阵，记为M(D).59例：写出下图的关联矩阵60有向图的关联矩阵性质

(4)平行边对应的列相同61/81邻接矩阵(adjacencymatrix)

设G=(V,E)是一个无向图，|V|=n，

V={v1,v2,⋯,vn}，则有n×n阶矩阵，

A(G)=(aij)n×n其中:

称A(G)=(aij)n×n为图G的邻接矩阵。aij=1{vi,vj}∊E0{vi,vj}∉E62/81例邻接矩阵

v1v2v3v4v5v1

01111v2

10101v3

11011v4

10101v5

10110

A(G)=63定义设有向图D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},令为顶点vi邻接到顶点vj边的条数，称()mn为D的邻接矩阵,记作A(D),简记为A.有向图的邻接矩阵（补）

64例邻接矩阵性质65/81定理2设图G=(V,E)，其中V={v1,v2,⋯,vn}。A是G的邻接矩阵。对于任意的自然数k，设矩阵Ak的第i行第j列的元素为aij(k)，即

Ak=(aij(k))n×n则aij(k)

给出了所有的从vi到vj的长度为k的通路的条数。若aij(k)=0，说明没有vi到vj的长度为k的通路。66/81例有向图D如图所示,求A,A2,A3,A4,

并回答诸问题：D中长度为1,2,3,4的通路各有多少条？

其中回路分别为多少条？(2)D中长度小于或等于4的通路为多少条？

其中有多少条回路？

长度通路回路

67合计50818121133141417368/81有向图的可达矩阵定义设D=<V,E>为有向图,V={v1,v2,…,vn},令

称(pij)nn为D的可达矩阵,记作P(D),简记为P.性质:

P(D)主对角线上的元素全为1.D强连通当且仅当P(D)的元素全为1.69例右图所示的有向图D的可达矩阵为70/819.3带权图与带权图中的最短通路(一)带权图(二)最短通路问题(三)狄克斯瑞(Dijkstra)算法71/81例假设有分布在不同建筑物中的5台计算机C1,C2,C3,C4,C5。计算机连接的可能方案以及每种连接方式的成本（单位：元）如右图所示。C1100C2C3C4C5120370200成本最低的安装方案C1100C2900C3C4C512040020045037072/81带权图一个带权图规定为◆一个有序三元组(V，E，f)，或◆一个有序三元组(V，E，g)，或◆一个有序四元组(V，E，f，g)，其中，V是顶点集，E是边集，f是定义在V上的函数，g是定义在E上的函数，f和g我们可以称为权函数。对于每一个顶点或边x，f(x)和g(x)可以是一个数字、符号或是某种量。73/81带权图中的最短通路设G=(V,E,W)是一个带权图，其W是边集E到R+={x∊R│x>0}的一个函数。通常称W(e)为边e的长度，图G中一个通路的长度定义为通路中所经过的边的长度之和。设v0,z∊V，要求从v0到z的最短通路的长。74/81Dijkstra算法的基本思想先把V分成两个子集，一个设为T,T={v∊V│v0到v的最短通路的长已经求出}，另一个是P=V－T。显然T≠Ø，因为至少v0∊T。要不断地扩大T，直到z∊T。TP＝V－Tv0z75/81定理对于任意的x∊P，设LT(x)表示从v0仅经过T中的顶点到x的最短通路的长。若不存在这样的通路，置LT(x)=∞。称LT(x)为x关于T的指标。令

LT(t1)=min{LT(x)│x∊P}则LT(t1)是从v0到t1的最短通路的长。TP＝V－Tv0t1注：LT(x)即为教材上的l(t)x76/81定理的证明若存在从v0到t1的通路其长小于LT(t1)，这条路一定包含了P中的顶点（否则，与LT(t1)最小性矛盾）。设t2∊P，且t2是从v0到t1的其长度小于LT(t1)的通路中遇到的第一个P中的点。于是有一条从v0到t2仅经过T中的点的通路，其长度小于LT(t1)，而由LT(t2)的定义知，LT(t2)<LT(t1),这与假设LT(t1)=min{LT(x)│x∊P}矛盾。TP＝V－Tv0t1t277/81命题设T和P已知，已找出t1,使LT(t1)=min{LT(x)│x∊P}。令T’=T∪

{t1}P’=P－

{t1}，并设LT’(x)表示仅经过T’中的点从v0到x的最短通路的长。则有

LT’(x)=min{LT(x),LT(t1)+W({t1,x})}这里，若图中{t1,x}∉E,取W({t1,x})=∞。v0t1xt’v0t1xv0t1x79/81命题的证明从v0到x且不含P’中顶点的任何一条最短通路，只有两种可能的情况：一条既不包含P’中的顶点也不包含t1的通路.此时，最短通路长仍然为LT(x)v0t1x80/81命题的证明(2)一条由v0到t1不包含P中的其它顶点，然后由t1经过{t1,x}到x的通路。此时，最短通路长为LT(t1)+W({t1,x})

.v0t1x81/81命题证明的说明：还有一种？实际上，从v0到t1再到t’的这条通路一定不短于从v0到t’的最短通路，而由作法可知从v0到t’的最短路经过的点全在T中，所以即使有可能产生一条最短路，我们也可以用一条从v0到t’的仅经过T中点的最短通路取代，也就是说这种情况可以归化为第一种情况考虑。从v0到t1，再到T’中某一顶点t’，由t’到x中间不经P’中点。v0t1xt’82/81Dijkstra算法设起点是v0，终点是z。具体程序如下：开始，设T={v0}，P=V－T，对P中的每一个顶点x,令LT(x)=W({v0,x})。设t1是P中关于T有最小指标的顶点,即

LT(t1)=min{LT(x)│x∊P}。若t1=z，则终止。否则，设T’=T∪

{t1}，P’=P－

{t1}。对于P’中的每一个顶点，计算它关于T’的指标：

LT’(x)=min{LT(x),LT(t1)+W({t1,x})}。把T’代为T,把P’代为P,把LT’(x)代为LT(x)，重复步骤(2)。83/81例求图9.9中从a到z的最短通路的长acebdz147123265T={a,b}386∞T={a,b,c}

84∞abcdezT={a}