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

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

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

通路

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

周长、围长

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

通路、回路的定理

离散数学通路,算法,图论,数据结构
通路最大为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日
浏览(39)
离散数学：图的基本概念

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

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

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

2024年02月12日
浏览(24)
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日
浏览(33)
离散数学第十章图的基本概念

目录 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日
浏览(37)
【数据结构】图-图的连通性（图解）

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

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

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

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

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

2024年02月03日
浏览(33)
【离散数学】4. 图论

1.数理逻辑 2. 集合论 3. 代数系统 4. 图论图：点+边+边与点的映射函数连通性与判别欧拉图与哈密尔顿图二分图和平面图与欧拉公式树及生成树单源点最短路径：Dijkstra算法对偶图 4.1.1 图一个图G是一个三重组 V ( G ) , E ( G ) , Φ G V(G),E(G),Phi_G V ( G ) , E ( G ) , Φ G V(G)是一

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

点相同边相同 $$ 必要条件节点数相同边相同度数相同节点数目相同 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日
浏览(192)