大一各科课件-离散图论

图 1图 重点： (Königsbergbridgesdadab从四块陆地的任何一块出发，怎样通过每座桥恰巧一次，哥尼斯堡七桥1736年 “哥尼斯堡的七座桥.LuChaojun, 路径 闭图G中包含其所有边的简单开路径称为G的路径。图G中包含其所有边的简单闭路径称为G的闭(回)路。Definition:AnEulercircuit(cycle)isacyclethattraverseseveryedgeofagraphexactlyonce.Ifthereisanopenpaththattraverseeachedgeonlyonce,itiscalledanEulerpath. c Eulercircuit:

Eulerpath:图 有向 图每个结点的出度和入度都相等的有向图称 有向图找到了连通无向图 定理6图论8引8G的每个顶点的度数的d(v)2,则G（Ifd(G)>=2thenGcontainsaLetPbealongestpath(actually, alpathsuffices)inGletubeanendpointofP.SincePcannotbeextended,everyofuisavertexinSinced(u)>=2,uhasaneighborvinPviaanedgethatisnotinTheedge{u,v}completesthecyclewiththeportionofPfromvto图论设G是连通无向图，G 图(每个结点都是偶结点 闭路。(WecallagraphEulerianifithasan(1)):对任一 回路沿ei进入v必然有ej从v出来，同时 闭路每条边是不相同的，因此，必然结点的度是偶 （2）)对G的n用第二归纳法n0G令n∈I＋，设任意边数少于n的连通 闭路。若G有n条边，连通、偶结G是连 图 引 G定理

设G有长度为m的回路C Cv0e1v1…vm-1emv0v0,v1,…,vm-1各不相同，并且{v0,v1,…,vm-1}{e1,e2,…,em}分别是C的结点集合和边集合。定理G＝〈Ｖ，Ｅ，Ψ〉，vG是回路或有向回路当且仅当G的阶与边数相等，并且在G中存在这样一条从v到v的闭路径，使得除了v在该闭路径中图论G{e1em}，设有k个分支G1GkG是连通

的每个分支GiC都有公共结点设vni为的分支Gi（1ik）与C的一个公共结点，0n1…nkm–1。显然，Gi为边数小于n的连 点仍为偶结点）。由归纳假设：GiPi

vni到vni 闭路v0e1v1…en1P1en1+1…enkPkenk+1…vm- CCAnEuleriancomponentofAnAnEuleriancomponentof图论Euler’sTheoremsareexamplesofexistencelswhetherornotsomethingbut lushowtocreatewewantaconstructivemethodforfindingEulerpathsand 图论图论pickanyvertextofromthatvertexpickanedgetotraverse(seebelowforimportantdarkenthatedge,asareminderthatyoucan'ttraverseittravelthatedge,comingtothenextrepeat2-4untilalledgeshavebeentraversed,andyouarebackattheAteachstageofthetheoriginalgraphminusthedarkened(alreadyused)edges=reducedimportantrule:nevercrossabridgeofthereducedgraphunlessthereisotherbridge:bridge(alsoknownasacut-edgeorcutarcoranisthmus)isanedgewhosedeletionincreasesthenumberofconnectedcomponents.Equivalently,anedgeisabridgeifandonlyifitisnotcontainedinanycycle.Thinkaboutit:whymustweobservethatEuleriangraphcontainsnoReduced Therestofthetripisobvious,andcompleteEulercircuit(F,C,D,A,C,E,A,B,D,图论定理设G＝〈Ｖ，Ｅ，Ψ〉为连通无向图，v1，v2∈Ｖ且v1v2。 G有一条从v1至v2的 G恰有两个v1和v2证明：任取eE，并令Ψ′＝｛〈e，｛v1，v2｝〉｝，则G有一条从v1至v2的 G′中每个结点都是G中恰有两个奇结点v1和

图论定理设G为弱连通的有向图。G是

G 图论定理G为弱连通的有向图。v1和v2GG有一条从v1至v2 路 dＧ＋(v1)＝dＧ－(v1)＋1，dＧ＋(v2)＝dＧ－(v2)G的其它结点vdＧ＋(v)＝ 图论根据哥尼斯堡桥问题画出的图不 因此不存 图论周游世界的数学 ) 二十个顶点 问：找一条从某城市出发，经过每个城市恰好一次，并且最后：在图中找出一条，并且，除始点和终点重合外，这条闭路所含结点是互不相同的。根据定理7.3.6，这 图）：无向图G中穿过每个顶点 圈,具有

定义13.4无向图G中穿过每个顶点一次且仅一次的非闭合链，称为链.有向图D中穿过每个顶点一次且仅一次的非闭合通路，称为通路.定理(Ore,1960(SufficientIfGisasimplegraphwithn≥3verticessuchforeachpairofnon-adjacentverticesu,v,thenGis证明首先证明G是连通图。假设G非连通，则G至少有两个连所有的v1inV（G1），v2in(V（G2），因为d（v1）≤n1-1d（v2）≤n2-1，故d（v1）+d（v2）≤n1+n2-2＜n-1，这与 ，因此，G必连通定理(NecessaryIfagraphGcontainsabridge,thatis,anedgewhoseremovaldisconnectsthegraph,thenGdoenothaveaHamiltoniancycle.定理(NecessaryForeachvert