图论(简化).pptVIP

1 图的基本概念与基本定理 例2 有六支球队进行足球比赛，我们分别用点v1…v6表示这六支球队，它们之间的比赛情况，也可以用图反映出来，已知v1队战胜v2队，v2队战胜v3队，v3队战胜v5队，如此等等。这个胜负情况，可以用图8.3所示的有向图反映出来。 例2 分子式CnH2n+2 流程图 从以上的几个例子可以看出，我们用点和点之间的线所构成的图，反映实际生产和生活中的某些特定对象之间的特定关系。一般来说，通常用点表示研究对象用点与点之间的线表示研究对象之间的特定关系。 由于在一般情况下，图中的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系，显的并不重要，因此，图论中的图与几何图，工程图等本质上是不同的。 综上所述，图论中的图是由点和点与点之间的线所组成的。通常，我们把点与点之间不带箭头的线叫做边，带箭头的线叫做弧。 如果一个图是由点和边所构成的，那么，称为为无向图，记作G =(V，E)，其中V表示图G的点集合，E表示图G的边集合。连接点vi,vj?V的边记作[vi,vj]，或者[vj,vi]。 如果一个图是由点和弧所构成的，那么称为它为有向图，记作D =(V,A)，其中V 表示有向图D的点集合，A表示有向图D的弧集合。一条方向从vi指向vj的弧，记作(vi,vj)。 图4是一个无向图G =（V，E） 其中 V={v1,v2,v3,v4} E={[v1,v2],[v2,v1],[v2,v3], [v3,v4],[v1,v4],[v2,v4], [v3,v3]} 图5是一个有向图D =（V，A） 其中V={v1,v2,v3,v4,v5,v6,v7} A={(v1,v2),(v,v3),(v3,v2), (v3,v4),(v2,v4),(v4,v5), (v4,v6),(v,v3),(v5,v4), (v5,v6),(v6,v7)} 常用的名词 一个图G或有向图D中的点数,记作P(G)或P(D),简记作P,边数或者弧数,记作q(G)或者q(D),简记作q。 如果边[vi,vj]?E,那么称vi,vj是边的端点，或者vi,vj是相邻的。 如果一个图G中，一条边的两个端点是相同的,那么称为这条边是环，如图8.4中的边[v,v3]是环。 如果两个端点之间有两个端点之间有两条以上的边，那么称为它们为多重边，如图8.4中的边[v1,v2] ,[v2,v1]。 一个无环，无多重边的图标为简单图，一个无环，有多重边的图标图称为多重图。 以点v为端点的边的个数称为点v的度，记作d(v),如图4中d(v1)=3， d(v2)=4,d(v3)=4,d(v4)=3。 度为零的点称为弧立点，度为1的点称为悬挂点。悬挂点的边称为悬挂边。度为奇数的点称为奇点，度为偶数的点称为偶点。 图的连通性（无向图） 链： 由两两相邻的点及其相关联的边构成的点 边序列；如： v0 ,e1 ,v1 ,e2 ,v2 ，e3 ,v3 ,…,vn-1, en , vn ; v0 ，vn分别为链的起点和终点； 简单链：链中所含的边均不相同； 初等链：链中所含的点均不相同,也称通路； 回路： 若 v0 ≠ vn 分称该链为开链，否则称 为闭链或回路； 圈： 除起点和终点外链中所含的点均不相同 的闭链； 连通图：图中任意两点之间均至少有一条通路， 否则称作不连通图。 设 G1=[ V1 , E1 ],G2=[ V2 ,E2 ] 子图：如果V2 ?V1 ,E2 ?E1 称G2 是G1 的子图； 真子图：如果V2 ?V1 ,E2 ?E1 称G2 是G1 的真子图； 部分图（支撑子图）：如果 V2 = V1 , E2 ? E1 称 G2 是 G1 的部分图； 有向图：关联边有方向 弧：有向图的边a=(u ,v),起点u,终点v； 路：若有从 u 到 v 不考虑方向的链,且各方向一 致,则称之为从u到v的路； 初等路: 各顶点都不相同的路； 欧拉图与哈密尔顿图 设G为连通的无向图，经过图G每边一次且仅一次的路称为欧拉路 设G为连通的无向图，经过图G每边一次且仅一次的路称为欧拉回路 含有欧拉回路的图称为欧拉图 一笔画问题 一笔画问题，也称为遍历问题，是很有实际意义的。 很明显，一个图G如果能够一笔画出，那么这个图一定是欧拉图或者含有欧拉链。 定理10 一个连通多重图G是欧拉图的充分必要条件是G中无奇点。 推论 一个多重连通图G有欧拉链的充分必要条件是G有且仅有两个奇点。 比如前面提到的哥尼斯