《离散数学》图的基本概念.pptxVIP

7.2通路、回路与图的连通性简单通(回)路,初级通(回)路,复杂通(回)路无向连通图,连通分支弱连通图,单向连通图,强连通图点割集与割点边割集与割边(桥)

定义给定图G=V,E（无向或有向的），设G中顶点与边的交替序列?=v0e1v1e2…elvl：若?i(1?i?l),vi?1和vi是ei的端点(对于有向图,要求vi?1是始点,vi是终点),则称?为通路,v0是通路的起点,vl是通路的终点,l为通路的长度.又若v0=vl，则称?为回路.理解：通路或回路是点与边的交替序列，边的端点恰好是前后的两个点长度＝边数通路与回路

若通路(回路)中所有顶点(对于回路,除v0=vl)各异，则称为初级通路(初级回路).初级通路又称作路径,初级回路又称作圈.路上各点不重复若通路(回路)中所有边各异,则称为简单通路(简单回路),否则称为复杂通路(复杂回路).路上各边不重复

说明:在无向图中，环是长度为1的圈,两条平行边构成长度为2的圈.无向简单图中,所有圈的长度?3在有向图中，环是长度为1的圈,两条方向相反边构成长度为2的圈.在有向简单图中,所有圈的长度?2.通路与回路(续)

通路与回路(续)01在n阶图G中，若从顶点vi到vj（vi?vj）存在通路，则从vi到vj存在长度小于等于n?1的通路.定理02在n阶图G中，若从顶点vi到vj（vi?vj）存在通路，则从vi到vj存在长度小于等于n?1的初级通路.推论03在一个n阶图G中，若存在vi到自身的回路，则一定存在vi到自身长度小于等于n的回路.定理04在一个n阶图G中，若存在vi到自身的简单回路，则一定存在长度小于等于n的初级回路.推论

无向图的连通性u与v连通:u与v之间有通路.设无向图G=V,E,连通关系：R={u,v|u,v?V且u?v}是V上的等价关系连通图:平凡图,或者任意两点都连通的图连通分支:V关于R的等价类的导出子图设V/R={V1,V2,…,Vk},G[V1],G[V2],…,G[Vk]是G的连通分支,规定u与自身总连通.单击此处添加正文，文字是您思想的提炼，为了演示发布的良好效果，请言简意赅地阐述您的观点。您的内容已经简明扼要，字字珠玑，但信息却千丝万缕、错综复杂，需要用更多的文字来表述；但请您尽可能提炼思想的精髓，否则容易造成观者的阅读压力，适得其反。正如我们都希望改变世界，希望给别人带去光明，但更多时候我们只需要播下一颗种子，自然有微风吹拂，雨露滋养。恰如其分地表达观点，往往事半功倍。当您的内容到达这个限度时，或许已经不纯粹作用于演示，极大可能运用于阅读领域；无论是传播观点、知识分享还是汇报工作，内容的详尽固然重要，但请一定注意信息框架的清晰，这样才能使内容层次分明，页面简洁易读。如果您的内容确实非常重要又难以精简，也请使用分段处理，对内容进行简单的梳理和提炼，这样会使逻辑框架相对清晰。连通分支个数记作p(G)=k.单击此处添加正文，文字是您思想的提炼，为了演示发布的良好效果，请言简意赅地阐述您的观点。您的内容已经简明扼要，字字珠玑，但信息却千丝万缕、错综复杂，需要用更多的文字来表述；但请您尽可能提炼思想的精髓，否则容易造成观者的阅读压力，适得其反。正如我们都希望改变世界，希望给别人带去光明，但更多时候我们只需要播下一颗种子，自然有微风吹拂，雨露滋养。恰如其分地表达观点，往往事半功倍。当您的内容到达这个限度时，或许已经不纯粹作用于演示，极大可能运用于阅读领域；无论是传播观点、知识分享还是汇报工作，内容的详尽固然重要，但请一定注意信息框架的清晰，这样才能使内容层次分明，页面简洁易读。如果您的内容确实非常重要又难以精简，也请使用分段处理，对内容进行简单的梳理和提炼，这样会使逻辑框架相对清晰。G是连通图?p(G)=1

短程线与距离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)（三角不等式)

点割集（v－点；V’－点集；e－边；E’－变集）G?V?:从G中删除V?中所有的顶点及关联的边G?e:从G中删除eG?E?:从G中删除E?中所有边记G?v:从G中删除v及关联的边设无向图G=V,E,如果存在顶点子集V??V,使p(G?V?)p(G)，而且删除V?的任何真子集V??后（?V???V?），p(G?V??)=p(G),则称V?为G的点割集.若{v}为点割集,则称v为割点.理解：删除点后连通分支数可能增加，会减少吗？定义

点割集(