Question

连通图的定义是什么？

Answer 1

连通性是图论的基本概念之一：它要求最小数量的元素（节点或边）需要被移除，以将剩余的节点分成两个或多个孤立的子图。它与网络流问题的理论密切相关。图的连通性是衡量其作为网络的弹性的重要指标。

在无向图 G中，如果G包含从u到v的路径，则称两个顶点 u和v是连通的。

否则，它们被称为断开连接。如果两个顶点通过长度为1的路径额外连接，即通过一条边，则这些顶点称为相邻。

如果图中的每一对顶点都是连通的，则称该图是连通的。这意味着每对顶点之间都有一条路径。未连接的无向图称为断开连接。

因此，如果G中存在两个顶点，使得G中没有路径以这些顶点为端点，则无向图G是不连通的。只有一个顶点的图是连接的。具有两个或多个顶点 的无边图是不连通的。

如果用无向边替换其所有有向边产生一个连通（无向）图，则称为弱连通图。如果每对顶点u, v包含从u到v的有向路径或从v到u的有向路径，则它是单边连通的或单边的（也称为半连通的）。

如果它包含从u到v的有向路径和从v到u的有向路径，则它是强连接的，或者只是强连接的对于每对顶点u, v。

门格尔定理

关于图中连通性的最重要事实之一是门格尔定理，它根据顶点之间独立路径的数量来表征图的连通性和边连通性。

如果u和v是图G的顶点，那么如果u 和 v 之间的路径集合中没有两个共享一个顶点（除了 u和 v本身），则称为独立路径集合。

类似地，如果集合中没有两条路径共享一条边，则该集合是与边无关的。

u和v之间相互独立的路径数记为κ′ ( u , v )，u和v之间相互独立的路径数记为λ′ ( u, v )。

对于不同的顶点u , v , λ ( u , v )等于λ′ ( u , v )，如果u也不与v相邻，则κ ( u , v )等于κ′ ( u , v ) 。