版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
图 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=〈V,E,Ψ〉,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=〈V,E,Ψ〉为连通无向图,v1,v2∈V且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 路 dG+(v1)=dG-(v1)+1,dG+(v2)=dG-(v2)G的其它结点vdG+(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
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 农产品初加工机相关项目投资计划书范本
- 麻醉科安全管理与服务优化措施计划
- 加强社区内商业活动的合理规划计划
- 2024-2025学年福建省漳州市漳浦县人教版三年级上册期中测试数学试卷-A4
- 《讲数列的应用》课件
- 《设备管理工作规划》课件
- 《信息的加密》课件
- 《教材股票估值》课件
- 质量分析报告范文
- 《电工技术》课件-第11章
- 国家基本药物目录2022版
- 知道智慧网课《古代汉语》章节测试答案
- 食品营养学习题库(含参考答案)
- 机械产品数字化设计智慧树知到期末考试答案章节答案2024年九江职业大学
- 项目经理承包责任制
- 《HSK标准教程2》06你怎么不吃了
- 酱油投资项目可行性报告
- 行政复议法-形考作业2-国开(ZJ)-参考资料
- 随机森林完整版本
- 云南省文山州文山市第二学区2023-2024学年八年级上学期期末语文试题
- 留学生个人承诺书
评论
0/150
提交评论