离散数学·通路与回路、图的连通性、连通度

10月前作者：call me by ur name 分类：Toy博客阅读(74) 违法举报

这篇具有很好参考价值的文章主要介绍了离散数学·通路与回路、图的连通性、连通度。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

通路

离散数学通路,算法,图论,数据结构
通路 —— 点边点边……点（点边可以重复）
注意长度的概念——边数
回路 —— 最后又回到自己，如其字面意思
简单 —— 边互异（边不可重复）
初级 —— 点互异（点不可重复，除了起点终点）
注意路径和圈所指代的
复杂通路 应该不是很重要，先不看
注意是在无向图 的条件下

周长、围长

离散数学通路,算法,图论,数据结构
最长圈的长度是周长，最短圈的长度是围长

通路、回路的定理

离散数学通路,算法,图论,数据结构
通路最大为n-1，而回路最大为n（因为比通路多了一条从次终点回到起点【终点】）
关于注：

例

离散数学通路,算法,图论,数据结构
比较简单，浅看一下即可

扩大路径法

离散数学通路,算法,图论,数据结构
这个定义看看就行了，暂时想不到简单的解释，但是对于扩大路径法、极大路径目前是会的

例

离散数学通路,算法,图论,数据结构

连通性

无向图

离散数学通路,算法,图论,数据结构
注意是在无向图中
有通路就是连通的，图是连通的即——任意两个结点都是连通的
这个不用细看了

有向图

离散数学通路,算法,图论,数据结构

强连通、弱连通、单侧连通

离散数学通路,算法,图论,数据结构
在有向图中
基图 —— 有向图去掉方向后的无向图
强连通是对于任何

强分图、弱分图、单侧分图

离散数学通路,算法,图论,数据结构

连通度

离散数学通路,算法,图论,数据结构
注意一下p的含义——更加不连通的程度

割集

点割集

离散数学通路,算法,图论,数据结构
简而言之——去掉一些点（在相应的情况下是最少的，但不代表是所有集合最少的，具体看例子）使图不连通，那么点组成的集合为点割集

割点

离散数学通路,算法,图论,数据结构
割点——点割集只有一个元素（去掉这一个割点后，图就变得不连通了）

边割集

离散数学通路,算法,图论,数据结构
同点割集，只不过割集元素为边

割边（桥）

离散数学通路,算法,图论,数据结构
割边也叫桥（熟悉这个说法）

连通度

连通度

离散数学通路,算法,图论,数据结构
所有点割集中最小的那个

边连通度

离散数学通路,算法,图论,数据结构
同理

k-连通图、k-边连通图

离散数学通路,算法,图论,数据结构
看看例

Whitney定理

离散数学通路,算法,图论,数据结构

块

离散数学通路,算法,图论,数据结构

二部图

离散数学通路,算法,图论,数据结构

完全二部图

离散数学通路,算法,图论,数据结构
K₂₃文章来源地址https://www.toymoban.com/news/detail-779366.html

到了这里，关于离散数学·通路与回路、图的连通性、连通度的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：

领支付宝红包赞助服务器费用

C++ 图论之求图的连通块数量（邻接矩阵版）

1. 连通块的定义块内每个点之间都有一条路径。 2. 思路我们可以用dfs深度优先搜索：从一个点出发遍历图将遍历过的点全部标记，标记过的点则不会再遍历到。再写一个循环枚举所有的点（枚举起点），如果没标记就代表可以作为起点，数量加一，进行dfs标记点。 3. 代码

2024年02月13日
浏览(52)
离散数学：图的基本概念

本帖子讨论图的基本概念，这一章，我们将利用有序对和二元关系的概念定义图。图分为了无向图和有向图，他们有共性也有区别，请大家注意体会，用联系和辩证的观点去认识。注意无向图和有向图的表示，最大区别在于边的集合的表示，无向图中边集为无序集VV的子集，

2024年02月09日
浏览(53)
离散数学·图的着色

k -着色 —— 用k个颜色上色的色数 —— 最少需要的颜色数 k -色图 —— 最少需要的色的图 χ(……) —— 相应色数 χ(G) 点色数 =1 —— 为零图全是孤立点 χ(K n )=n χ(G)=2 —— G为非零图二部图二部图：一个图的点集可以分为2个互不相交的点集A,B的并，并且在G中的每一条边

2024年02月12日
浏览(35)
408【数据结构】图、生成树、图的出度和入度、路径and路径长度和回路、简单路径和简单回路概念整理和错题整理

图由顶点集V和边集E组成，记为G=（V，E），使用 V（G）表示所有顶点的集合（不能为空）；使用 E（G）表示各个顶点之间的关系（可以为空）。若用V={v1,v2,v3,....,vn}来表示图，则使用 |V|表示图中顶点的个数，使用E={（vi，vj）|vi∈V，vj∈V}，用 |E| 表示图中边的条

2024年02月03日
浏览(44)
离散数学第十章图的基本概念

目录 10.1 图的基本概念 10.2 道路与回路 10.3 图的连通性 10.4 图的矩阵表示 ①什么是图：一个序偶(V,E)，记作G=(V,E) V(G)={v1,v2,...,vn} 结点集，n为G的阶 E(G)={e1,e2,...,em} 边集，m为G的边数 ②图的分类： 1.无向图

2024年02月07日
浏览(47)
【数据结构】图-图的连通性（图解）

GitHub同步更新（已分类）：Data_Structure_And_Algorithm-Review 公众号： URLeisure 的复习仓库公众号二维码见文末以下是本篇文章正文内容，下面案例可供参考。无向图中，如果从节点 V i 到节点 V j 有路径，则称节点 V i 和节点 V j 是连通的。如果图中任意两个节点都是连通的，则

2024年02月02日
浏览(50)
[离散数学]图论

点相同边相同 $$ 必要条件节点数相同边相同度数相同节点数目相同 m = C n 2 = 5 ∗ 4 / 2 = 10 m=C_n^2=5*4/2=10 m = C n 2 = 5 ∗ 4/2 = 10 n = 5 n=5 n = 5 由推论 m ≤ 3 n − 6 le3n-6 ≤ 3 n − 6 得 m ≤ 9 le9 ≤ 9 相互矛盾 ∑ d e g ( v i ) = 2 e = 2 V − 2 sum deg(v_i)=2e =2V -2 ∑ d e g ( v i ) = 2 e =

2024年02月05日
浏览(205)
【离散数学】测试五图论

目录图论系列文章 1. n层正则m叉树一共有（）片树叶。 A. nm B. mn C. mn 正确答案： B 2. 下图是一棵最优二叉树 A. 对 B. 错正确答案： B 3. 要构造权为1，4，9，16，25，36，49，64，81，100一棵最优二叉树，则必须先构造权为5，9，16，25，36，49，64，81，100一棵最优二叉树

2024年02月09日
浏览(40)
离散数学-图论-树（13）

定义1：连通无回路的无向图称为无向树,简称树.每个连通分支都是树的无向图称为森林.平凡图称为平凡树.在无向树中,悬挂顶点称为树叶,度数大于或等于2的顶点称为分支点. 定义2 设G=V,E是n阶m条边的无向图，则下面各命题是等价的: (1)G是树 (2)G中任意两个顶点之间存在惟一的

2024年02月03日
浏览(45)
离散数学——图论部分

目录概述考点：邻接矩阵，矩阵的计算及含义，完全图，补图，平面图的相关概念，欧拉图，最小生成树，最优二叉树一.图编辑二.路和回路 2.1 2.2连通与可达 1.可达 2.连通三.图的矩阵表示 3.1邻接矩阵 3.2可达性矩阵 3.3无向图的完全关联矩阵 3.4有向图的完全关联矩阵

2024年02月04日
浏览(40)