离散数学图概念路与回路.ppt

********************************************************定理7-2.5在有向图G=V,E中，它的每一个结点位于且只位于一个强分图中。?证明思路：1)先证:每一个结点必位于一个强分图中。2)再证:每一个结点只位于一个强分图中。?第59页,共60页，星期六，2024年，5月感谢大家观看第60页,共60页，星期六，2024年，5月************************************************************两图同构的一些必要条件：1.结点数目相同；2.边数相等；3.度数相同的结点数目相等。以上几个条件不是两个图同构的充分条件。见279页图7-1.10同构必须是结点和边分别存在一一对应。第27页,共60页，星期六，2024年，5月*作业279页:(5)（6）第28页,共60页，星期六，2024年，5月7-2路与回路在现实世界中，常常要考虑这样的问题：如何从一个图中的给定结点出发，沿着一些边连续移动而达到另一指定结点，这种依次由点和边组成的序列，就形成了路的概念。第29页,共60页，星期六，2024年，5月学习本节要熟悉如下术语(22个)：路、路的长度、迹、回路、通路、圈、连通、连通分支、点割集、连通图、割点、点连通度、边割集、边连通度、割边、可达、单侧连通、强连通、强分图、弱连通、弱分图、单侧分图掌握5个定理，一个推论。第30页,共60页，星期六，2024年，5月路无向图的连通性有向图的连通性7-2路与回路第31页,共60页，星期六，2024年，5月一、路定义7-2.1给定图G=V,E,设v0,v1,…,vn?V，e1,…,en?E,其中ei是关联于结点vi-1,vi的边，交替序列v0e1v1e2…envn称为结点v0到vn的路（path）。v0和vn分别称为路的起点和终点，边的数目n称作路的长度。当v0=vn时，这条路称作回路。若一条路中所有的边e1,…,en均不相同,称作迹。若一条路中所有的结点v0,v1,…,vn均不相同,称作通路。闭的通路,即除v0=vn之外,其余结点均不相同的路,称作圈。第32页,共60页，星期六，2024年，5月例如路：v1e2v3e3v2e3v3e4v2e6v5e7v3迹：v5e8v4e5v2e6v5e7v3e4v2通路：v4e8v5e6v2e1v1e2v3圈：v2e1v1e2v3e7v5e6v2第33页,共60页，星期六，2024年，5月在简单图中一条路v0e1v1e2…envn，由它的结点序列v0，v1，…，vn确定，所以简单图的路，可由其结点序列表示。在有向图中，结点数大于1的一条路亦可由边序列e1e2…en表示。第34页,共60页，星期六，2024年，5月定理7-2.1在一个具有n个结点的图中，如果从结点vj到结点vk存在一条路，则从结点vj到结点vk必存在一条不多于n-1条边的路。?证明思路：多于n-1条边的路中必有重复出现的结点，反复删去夹在两个重复结点之间的边之后，剩余的边数不会超过n-1条边。?第35页,共60页，星期六，2024年，5月定理7-2.1的证明如果从结点vj到vk存在一条路，该路上的结点序列是vj…vi…vk，如果在这条中有l条边，则序列中必有l+1个结点，若ln-1，则必有结点vs，它在序列中不止出现一次，即必有结点序列vj…vs…vs…vk，在路中去掉从vs到vs的这些边，仍是vj到vk的一条路，但此路比原来的路边数要少，如此重复进行下去，必可得到一条从vj到vk的不多于n-1条边的路。第36页,共60页，星期六，2024年，5月定理7-2.1在一个具有n个结点的图中，如果从结点vj到结点vk存在一条路，则从结点vj到结点vk必存在一条不多于n-1条边的路。推论在一个具有n个结点的图中，如果从结点vj到结点vk存在一条路，则从结点vj到结点vk必存在一条边数小于n的通路。第37页,共60页，星期六，2024年，5月