文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 图的连通性
侵权投诉

图的连通性

图的连通性

即w(T u) w(T) 1。由于T u是图G u的生成树,故

w(G u) w(T u) w(T) 1 w(G),

因此u不是G的割点。同理v也不是G的割点。证毕。

二、顶点割集:

定义2.1.2 对图G,若V(G)的子集V 使得w(G V ) w(G),则称V 为图G的一个顶点割集。含有k个顶点的顶点割集称为k-顶点割集。 注:(1)割点是1-顶点割集。 (2)完全图没有顶点割集。

三、连通度: (G) min{|V ||V 是G的顶点割集}。完全图的连通度定义为 (K ) 1,空图的连通度定义为0。

注:(1) 使得|V | (G)的顶点割集V 称为G的最小顶点割集。 (2)若 (G) k,则称G为k连通的。 (3)若G不连通,则 (G) 0。 (4)若G是平凡图,则 (G) 0。 (4)所有非平凡连通图都是1连通的。 例:

四、割边

定义2.1.3 设e E(G),如果w(G e) w(G),则称e为G的一条割边。 定理2.1.3 边e是G的割边当且仅当e不在G的任何圈中。 证明:证其逆否命题:e不是割边当且仅当e含在G的某个圈中。

必要性:设e = xy不是割边。假定e位于G的某个连通分支G1中,则G1 e仍连通。故在

G1 e中有(x,y)路P,P + e便构成G1中一个含有e的圈。

充分性:设e含在G的某个圈C中,而C含于某连通分支G1中,则G1 e仍连通。故

w(G e) w(G),这说明e不是割边。证毕。

定理2.1.4 一个连通图是树当且仅当它的每条边都是割边。

证明:连通图G是树 G无圈 任何边e不含在圈中 任何边e是G的割边。证毕。

图的连通性

图的连通性

图的连通性

图的连通性

上一页第2页

你可能喜欢

热门文档

相关文档

  • 图的连通性

    图的连通性离散数学 第22讲 上一讲内容的回顾通路与回路 连通与连通图 扩大路径证明法 最短通路问题与Dijstra算法 图的连通性割点 割边(桥) (点)连通度 ( ...

  • 图论课件第三章 图的连通性

    图论课件第三章 图的连通性_数学_自然科学_专业资料。图论课件1 0 .5 n 0 ? 0 .5 ?1 2 1 .5 t 1 0 .5 0 0 0 .4 0 .2 x 0 .8 0 .6...

  • 图的连通性总结

    图的连通性总结_IT/计算机_专业资料。强连通分量图的连通性总结 boboo 目录 1. 图的遍历及应用 1.1. DFS 遍历 1.2. DFS 树的边分类 1.3. DFS 树的...

  • 图的连通性问题

    图的连通性问题 £7.4 图的连通性问题£7.4.1 无向图的连通分量和生成树(1)连通图 在对无向图进行遍历时,对于连通图,仅需从图中任一顶点出发, 进行深度...

  • 图的连通性

    图的连通性 //割点 割点 vector<int>map[Max]; //邻接表 int n, root, times; int dfn[Max], low[Max]; int flag[Max]; int Min( int a,int b...

  • 图的连通性判断

    图的连通性判断_工学_高等教育_教育专区。可以明确找出图中各个分支,并确定各节点的归属。基于MATLAB 的实现,此方法可以知道有几个连通域,并且知道各个顶点的...

  • 7.4 图的连通性问题

    7.4 图的连通性问题 7.4.1 无向图的连通分量和生成树 ?连通:顶点v至v’之间有路径存在 ?连通图:无向图图 G 的任意两点之间都是连通的,则称 G 是 连通...

  • 求图的连通性,8

    求图的连通性,8_数学_自然科学_专业资料。“离散数学”实验报告(求图的连通性) 专业班级学号姓名 网络工程 1202 班 12407442 张敏慧 2013.12.14 目录一.实验...

  • 3-图的连通性

    《通信网理论基础》 实 验 指 导 书适用专业—信息工程 实验三:图的连通性判断一、实验目的 本次实验要求用计算机语言编写图的连通性判断算法,可输入图的邻接矩...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email