图论部分第七章、图的基本概念7.1 无向图及有向图无向图与有向图多重集合: 元素可以重复出现的集合无序积: A&B={(x,y) | x∈A∧y∈B}定义无向图G=<V,E>, 其中(1) 顶点集V≠∅，元素称为顶点(2) 边集E为V&V的多重子集，其元素称为无向边，简称边.例如, G=<V,E>如图所示, 其中V={v1, v2, …,v5}, E={(v1,v1), (v1,v2),(v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5)} ,定义有向图D=<V,E>, 其中(1) V同无向图的顶点集, 元素也称为顶点(2) 边集E为V⨯V的多重子集，其元素称为有向边，简称边.用无向边代替D的所有有向边所得到的无向图称作D的基图，右图是有向图，试写出它的V和E注意：图的数学定义与图形表示,在同构(待叙)的意义下是一一对应的通常用G表示无向图, D表示有向图, 也常用G泛指无向图和有向图, 用e k表示无向边或有向边.V(G), E(G), V(D), E(D): G和D的顶点集, 边集.n 阶图: n个顶点的图有限图: V, E都是有穷集合的图零图: E=∅平凡图: 1 阶零图空图: V=∅顶点和边的关联与相邻：定义设e k=(v i,v j)是无向图G=<V,E>的一条边, 称v i ,vj为e k的端点, e k与v i (v j)关联. 若v i ≠v j, 则称e k与v i (v j)的关联次数为1;若v i = v j, 则称e k为环, 此时称e k与v i 的关联次数为2; 若v i不是e k端点,则称e k与v i 的关联次数为0. 无边关联的顶点称作孤立点.定义设无向图G=<V,E>, v i,v j∈V, e k,e l∈E,若(v i,v j) ∈E, 则称v i,v j相邻; 若e k,e l至少有一个公共端点, 则称e k,e l相邻.对有向图有类似定义. 设e k=〈v i,v j〉是有向图的一条边,又称v i是e k的始点, v j 是e k的终点, v i邻接到v j, v j邻接于v i.邻域和关联集顶点的度数设G=<V,E>为无向图, v∈V,v的度数(度) d(v): v作为边的端点次数之和悬挂顶点: 度数为1的顶点悬挂边: 与悬挂顶点关联的边G的最大度∆(G)=max{d(v)| v∈V}G的最小度δ(G)=min{d(v)| v∈V}例如d(v5)=3, d(v2)=4, d(v1)=4,∆(G)=4, δ(G)=1,v4是悬挂顶点, e7是悬挂边, e是环1设D=<V,E>为有向图, v∈V,v的出度d+(v): v作为边的始点次数之和v的入度d-(v): v作为边的终点次数之和v的度数(度) d(v): v作为边的端点次数之和d(v)= d+(v)+ d-(v)D的最大出度∆+(D), 最小出度δ+(D)最大入度∆-(D), 最小入度δ-(D)最大度∆(D), 最小度δ(D)例如d+(a)=4, d-(a)=1, d(a)=5,d+(b)=0, d-(b)=3, d(b)=3,∆+(D)=4, δ+(D)=0, ∆-(D)=3,δ-(D)=1,∆(D)=5, δ(D)=3.握手定理定理任意无向图和有向图的所有顶点度数之和都等于边数的2倍, 并且有向图的所有顶点入度之和等于出度之和等于边数.证G中每条边（包括环）均有两个端点，所以在计算G中各顶点度数之和时，每条边均提供2度，m条边共提供2m度. 有向图的每条边提供一个入度和一个出度, 故所有顶点入度之和等于出度之和等于边数.图的度数列设无向图G的顶点集V={v1, v2, …, v n}G的度数列: d(v), d(v2), …, d(v n)1如右图度数列:4,4,2,1,3设有向图D的顶点集V={v1, v2, …, v n}D的度数列: d(v), d(v2), …, d(v n)1D的出度列: d+(v), d+(v2), …, d+(v n)1D的入度列: d-(v), d-(v2), …, d-(v n)1如右图度数列:5,3,3,3出度列:4,0,2,1入度列:1,3,1,2例1 (3,3,3,4), (2,3,4,6,8)能成为图的度数列吗?解不可能. 它们都有奇数个奇数.例2 已知图G有10条边, 4个3度顶点, 其余顶点的度数均小于等于2, 问G 至少有多少个顶点?解设G有n个顶点. 由握手定理,4⨯3+2⨯(n-4)≥2⨯10解得n≥8例3 证明不存在具有奇数个面且每个面都具有奇数条棱的多面体.证用反证法. 假设存在这样的多面体,作无向图G=<V,E>, 其中V={v | v为多面体的面},E={(u,v) | u,v∈V∧u与v有公共的棱∧u≠v}.根据假设, |V|为奇数且∀v∈V, d(v)为奇数. 这与握手定理的推论矛盾. 多重图与简单图定义 (1) 在无向图中,如果有2条或2条以上的边关联同一对顶点, 则称这些边为平行边, 平行边的条数称为重数.(2)在有向图中,如果有2条或2条以上的边具有相同的始点和终点, 则称这些边为有向平行边, 简称平行边, 平行边的条数称为重数.(3) 含平行边的图称为多重图.(4) 既无平行边也无环的图称为简单图.注意:简单图是极其重要的概念图的同构定义设G1=<V1,E1>, G2=<V2,E2>为两个无向图(有向图), 若存在双射函数f: V1→V2, 使得对于任意的v,v j∈V1,i(v i,v j)∈E1（<v i,v j>∈E1）当且仅当(f(v i),f(v j))∈E2（<f(v i),f(v j)>∈E2），并且, (v i,v j)（<v i,v j>）与 (f(v i),f(v j))（<f(v i),f(v j)>）的重数相同，则称G1与G2是同构的，记作G1≅G2.几点说明：图之间的同构关系具有自反性、对称性和传递性.能找到多条同构的必要条件, 但它们都不是充分条件:① 边数相同，顶点数相同② 度数列相同(不计度数的顺序)③ 对应顶点的关联集及邻域的元素个数相同，等等若破坏必要条件，则两图不同构至今没有找到判断两个图同构的多项式时间算法完全图：n阶无向完全图K n: 每个顶点都与其余顶点相邻的n阶无向简单图.简单性质: 边数m=n(n-1)/2, ∆=δ=n-1n阶有向完全图: 每对顶点之间均有两条方向相反的有向边的n阶有向简单图.简单性质: 边数m=n(n-1), ∆=δ=2(n-1),∆+=δ+=∆-=δ-=n-1子图：定义设G=<V,E>, G '=<V ',E '>是两个图(1) 若V '⊆V且E '⊆E,则称G '为G的子图, G为G '的母图, 记作G '⊆G(2) 若G '⊆G 且V '=V，则称G '为G的生成子图(3) 若V '⊂V 或E '⊂E，称G '为G的真子图(4) 设V '⊆V 且V '≠∅, 以V '为顶点集, 以两端点都在V '中的所有边为边集的G的子图称作V '的导出子图，记作G[V '](5) 设E '⊆E且E '≠∅, 以E '为边集, 以E '中边关联的所有顶点为顶点集的G的子图称作E '的导出子图, 记作G[E ']补图：定义设G=<V,E>为n阶无向简单图，以V为顶点集,所有使G成为完全图K n的添加边组成的集合为边集的图，称为G的补图，记作 .若G≅ , 则称G是自补图.例对上一页K4的所有非同构子图, 指出互为补图的每一对子图, 并指出哪些是自补图.7.2 通路、回路、图的连通性简单通(回)路, 初级通(回)路, 复杂通(回)路定义给定图G=<V,E>（无向或有向的），G中顶点与边的交替序列Γ=v0e1v1e2…e l v l，(1) 若∀i(1≤i≤l), v i-1, v i是e i的端点(对于有向图, 要求v i-1是始点, v i是终点), 则称Γ为通路, v0是通路的起点, v l是通路的终点, l为通路的长度. 又若v=v l，则称Γ为回路.(2) 若通路(回路)中所有顶点(对于回路, 除v0=v l)各异，则称为初级通路(初级回路).初级通路又称作路径, 初级回路又称作圈.(3) 若通路(回路)中所有边各异, 则称为简单通路(简单回路), 否则称为复杂通路(复杂回路).说明:表示方法① 用顶点和边的交替序列(定义), 如Γ=v0e1v1e2…e l v l② 用边的序列, 如Γ=e1e2…e l③ 简单图中, 用顶点的序列, 如Γ=v0v1…v l④ 非简单图中,可用混合表示法,如Γ=v0v1e2v2e5v3v4v5环是长度为1的圈, 两条平行边构成长度为2的圈.在无向简单图中, 所有圈的长度≥3; 在有向简单图中, 所有圈的长度≥2.在两种意义下计算的圈个数① 定义意义下在无向图中, 一个长度为l(l≥3)的圈看作2l个不同的圈. 如v0v1v2v0 ,v 1v2vv1, v2v0v1v2, v0v2v1v0 , v1v0v2v1 , v2v1v0v2看作6个不同的圈. 在有向图中, 一个长度为l(l≥3)的圈看作l个不同的圈.② 同构意义下所有长度相同的圈都是同构的, 因而是1个圈.定理在n阶图G中，若从顶点v i到v j（v i≠v j）存在通路，则从v i到v j存在长度小于等于n-1的通路.推论在n阶图G中，若从顶点v i到v j（v i≠v j）存在通路，则从v i到v j存在长度小于等于n-1的初级通路.定理在一个n阶图G中，若存在v i到自身的回路，则一定存在v i到自身长度小于等于n的回路.推论在一个n阶图G中，若存在v i到自身的简单回路，则一定存在长度小于等于n的初级回路.无向图的连通性设无向图G=<V,E>,u与v连通: 若u与v之间有通路. 规定u与自身总连通.连通关系R={<u,v>| u,v∈V且u~v}是V上的等价关系连通图:任意两点都连通的图. 平凡图是连通图.连通分支: V关于连通关系R的等价类的导出子图设V/R={V1,V2,…,V k}, G[V1], G[V2], …,G[V k]是G的连通分支, 其个数记作p(G)=k.G是连通图⇔p(G)=1短程线与距离u与v之间的短程线: u与v之间长度最短的通路(u与v连通)u与v之间的距离d(u,v): u与v之间短程线的长度若u与v不连通, 规定d(u,v)=∞.性质：d(u,v)≥0, 且d(u,v)=0 ⇔u=vd(u,v)=d(v,u)d(u,v)+d(v,w)≥d(u,w)点割集与割点记G-v: 从G中删除v及关联的边G-V ': 从G中删除V '中所有的顶点及关联的边G-e : 从G中删除eG-E': 从G中删除E'中所有边定义设无向图G=<V,E>, V '⊂V, 若p(G-V ')>p(G)且∀V ''⊂V ', p(G-V '')=p(G), 则称V '为G的点割集. 若{v}为点割集, 则称v为割点.边割集与割边(桥)定义设无向图G=<V,E>, E '⊆E, 若p(G-E ')>p(G)且∀E ''⊂E ',p(G-E '')=p(G), 则称E '为G的边割集. 若{e}为边割集, 则称e为割边或桥.在上一页的图中，{e1,e2}，{e1,e3,e5,e6}，{e8}等是边割集，e是桥，{e7,e9,e5,e6}是边割集吗？8几点说明：K无点割集nn阶零图既无点割集，也无边割集.若G连通，E '为边割集，则p(G-E ')=2若G连通，V '为点割集，则p(G-V ')≥2有向图的连通性设有向图D=<V,E>u可达v: u到v有通路. 规定u到自身总是可达的.可达具有自反性和传递性D弱连通(连通): 基图为无向连通图D单向连通: ∀u,v∈V，u可达v或v可达uD强连通: ∀u,v∈V，u与v相互可达强连通⇒单向连通⇒弱连通定理(强连通判别法) D强连通当且仅当D中存在经过每个顶点至少一次的回路定理(单向连通判别法) D单向连通当且仅当D中存在经过每个顶点至少一次的通路有向图的短程线与距离u到v的短程线: u到v长度最短的通路 (u可达v)u与v之间的距离d<u,v>: u到v的短程线的长度若u不可达v, 规定d<u,v>=∞.性质：d<u,v>≥0, 且d<u,v>=0 ⇔u=vd<u,v>+d<v,w> ≥d<u,w>注意: 没有对称性7.3 图的矩阵表示无向图的关联矩阵定义设无向图G=<V,E>, V={v1, v2, …, v n}, E={e1, e2, …, e m},令m ij为v i 与e j的关联次数，称(m ij)n⨯m为G的关联矩阵，记为M(G).性质(1) 每一列恰好有两个1或一个2有向图的关联矩阵定义设无环有向图D=<V,E>, V={v1, v2, …, v n},E={e, e2, …, e m}, 令1性质(1) 每一列恰好有一个1和一个-1(2) 第i行1 的个数等于d+(v i), -1 的个数等于d-(v i)(3) 1的总个数等于-1的总个数, 且都等于m(4) 平行边对应的列相同有向图的邻接矩阵有向图的可达矩阵7.4 最短路径及关键路径带权图G=<V,E,w>, 其中w:E→R.∀e∈E, w(e)称作e的权. e=(v i,v j), 记w(e)=w ij . 若v i,v j不相邻, 记w ij =∞.设L是G中的一条路径, L的所有边的权之和称作L的权, 记作w(L).u和v之间的最短路径: u和v之间权最小的通路.标号法(E.W.Dijkstra, 1959)PERT图与关键路径PERT图(计划评审技术图)设有向图G=<V,E>, v∈Vv的后继元集Γ+(v)={x|x∈V∧<v,x>∈E}v的先驱元集Γ-(v)={x|x∈V∧<x,v>∈E}PERT图:满足下述条件的n阶有向带权图D=<V,E,w>,(1) D是简单图,(2) D中无回路,(3) 有一个入度为0的顶点, 称作始点; 有一个出度为0的顶点, 称作终点.通常边的权表示时间, 始点记作v1, 终点记作v n关键路径关键路径: PETR图中从始点到终点的最长路径v的最早完成时间TE(v i): 从始点v1沿最长路径到v ii所需的时间TE(v)=01TE(v)=max{TE(v j)+w ji|v j∈Γ-(v i)}, i=2,3,⋯,niv的最晚完成时间TL(v i): 在保证终点v n的最早完成i时间不增加的条件下, 从始点v1最迟到达v i的时间TL(v)=TE(v n)nTL(v)=min{TL(v j)-w ij|v j∈Γ+(v i)}, i=n-1,n-2,⋯,1iv的缓冲时间TS(v i)=TL(v i)-TE(v i), i=1,2,⋯,niv在关键路径上⇔TS(v i)=0i最晚完成时间TL(v)=128TL(v)=min{12-6}=67TL(v)=min{12-1}=116TL(v)=min{11-1}=105TL(v)=min{10-4}=64TL(v)=min{6-2,11-4,6-4}=23TL(v)=min{2-0,10-3,6-4}=22TL(v)=min{2-1,2-2,6-3}=01缓冲时间TS(v)=0-0=01TS(v)=2-1=12TS(v)=2-2=03TS(v)=6-4=24TS(v=10-8=25TS(v)=11-9=26TS(v)=6-6=07TS(v)=12-12=08关键路径: v1v3v7v8。
