查看“︁连通图”︁的源代码

'''连通图'''（{{lang-en|Connected graph}}）是[[图论]]中最基本概念之一，其定义基于连通的概念。在一个[[无向图]]''G''中，若从[[顶点 (图论)|顶点]]<math>v_i</math>到顶点<math>v_j</math>有路径相连（从<math>v_j</math>到<math>v_i</math>也一定有路径），则称<math>v_i</math>和<math>v_j</math>是连通的。如果''G''是[[有向图]]，那么连接<math>v_i</math>和<math>v_j</math>的路径中所有的边都必须同向。如果图中任意两点都是连通的，那么图被称作连通图。图的连通性是图的基本性质。连通度是指为了让图分解成孤立的子图所要删除的顶点数的最小值。连通度是刻画网络的一个重要指标。

== 严格定义 ==

对一个图''G''= (''V'',''E'')中的两点<math>x</math>和<math>y</math>，若存在交替的[[顶点 (图论)|顶点]]和边的序列<math>\Gamma = (x=v_0 - e_1 - v_1 - e_2 - \cdots - e_{k} - v_{k} = y)</math>（在有向图中要求[[有向边]]<math>v_i - v_{i+1}</math>属于''E''），则两点<math>x</math>和<math>y</math>是连通的。<math>\Gamma</math>是一条<math>x</math>到<math>y</math>的连通路径，<math>x</math>和<math>y</math>分别是起点和终点。当<math>x=y</math>时，<math>\Gamma</math>被称为'''回路'''。如果通路<math>\Gamma</math>中的边两两不同，则<math>\Gamma</math>是一条'''简单通路'''，否则为一条'''复杂通路'''。如果图''G''中每两点间皆连通，则''G''是'''连通图'''。

一个有向图被称作'''弱连通'''('''weakly connected''')的，如果将所有有向边替换为无向边之后的无向图是连通的，如果对于任意一对顶点<math>u</math>，<math>v</math>，或者存在一条从<math>u</math>到<math>v</math>的有向路径，或者存在一条从<math>v</math>到<math>u</math>的有向路径，则该图是'''单连通'''('''unilaterally conncected''')的<ref>{{Cite web |url=http://compalg.inf.elte.hu/~tony/Oktatas/TDK/FINAL/Chap%2011.pdf#page=6 |title=Chapter 11: Digraphs: Principle of duality for digraphs: Definition |access-date=2020-10-04 |archive-date=2020-01-10 |archive-url=https://web.archive.org/web/20200110130724/http://compalg.inf.elte.hu/~tony/Oktatas/TDK/FINAL/Chap%2011.pdf#page=6 |dead-url=no }}</ref>，如果对于如果对于任意一对顶点<math>u</math>，<math>v</math>，同时存在一条从<math>u</math>到<math>v</math>的有向路径和一条从<math>v</math>到<math>u</math>的有向路径，则该图是'''强连通'''('''strongly connected''')的。

== 分量和割 ==
无向图''G''的一个极大连通子图称为''G''的一个[[元件 (圖論)|连通分量]]（或'''连通分支'''）。每一个顶点和每一条边都属于唯一的一个连通分量，连通图只有一个连通分量，即其自身；非连通的无向图有多个连通分量。

有向图中的[[强连通分量]]是其极大的强连通子图。强连通图只有一个强连通分量，即是其自身；非强连通的有向图有多个强连通分量。

连通图<math>G</math>的'''割点'''是指一个由顶点组成的集合，在<math>G</math>删除了这些点之后，会变得不连通。点连通度<math>\kappa(G)</math>是割点集阶数的最小值。如果图<math>G</math>不是完全图，且<math>\kappa(G)=k</math>,则图<math>G</math>是<math>k</math>-点连通的。更确切地来说，如果图<math>G</math>（不论是否完全）可以在删除了<math>k+1</math>个点之后变得不连通，却不能在删除<math>k-1</math>个点之后变得不连通，则图<math>G</math>是<math>k</math>-点连通的，特别地，阶数为<math>n</math>的完全图是<math>n-1</math>-点连通的。

一对端点<math>u</math>,<math>v</math>的'''割点'''是是指一个由顶点组成的集合，在<math>G</math>删除了这些点之后，<math>u</math>,<math>v</math>会变得不连通。局部连通度<math>\kappa(u,v)</math>是<math>u</math>,<math>v</math>的最小割点集的阶数。在无向图上，局部连通度是对称的，也就是说，<math>\kappa(u,v)=\kappa(v,u)</math>，另外，除了完全图之外，<math>\kappa(G)</math>为所有不相邻的点对<math>u</math>,<math>v</math>的局部联通度中的最小值。

类似的概念可以用来定义'''边连通度'''。如果在<math>G</math>上删除一条边可以导致不连通性，则这条边被称作[[桥 (图论)|桥]]。更一般地，'''割边'''是指一个由边组成的集合，在
在<math>G</math>删除了这些边之后，会变得不连通。边连通度在<math>\lambda(G)</math>是最小的割边集的大小，局部边连通度<math>\lambda(u,v)</math>是

如果图<math>G</math>的边连通度大于等于<math>k</math>，则它被称作<math>k</math>-边连通的。

在一个图上，以下的不等式成立:<math>\kappa(G)\leqslant\lambda(G)\leqslant\delta(G)</math>，其中<math>\delta(G)</math>是<math>G</math>的最小度(minimum degree)<ref name="diestel">{{cite web|last=Diestel|first=R.|url=http://diestel-graph-theory.com/GrTh.html|title=Graph Theory, Electronic Edition|date=2005|pages=12|access-date=2020-10-04|archive-date=2019-12-16|archive-url=https://web.archive.org/web/20191216100521/http://diestel-graph-theory.com/GrTh.html|dead-url=no}}</ref>。
如果图<math>G</math>的点连通度等于其最小度,则被称作'''极大连通'''的，如果它的边连通度等于其最小度，则它被称作'''极大边连通的<ref>{{Cite book
 | title = Handbook of graph theory
 | first1 = Jonathan L.
 | last1 = Gross
 | first2 = Jay
 | last2 = Yellen
 | publisher = [[CRC Press]]
 | year = 2004
 | page = [https://books.google.com/books?id=mKkIGIea_BkC&lpg=PA335&pg=PA335 335]
 | isbn = 978-1-58488-090-5
 | url = https://books.google.com/?id=mKkIGIea_BkC
 }}</ref>。
===Super- and hyper-连通===
如果图<math>G</math>上，每一个最小的割点集都能孤立一个顶点，则图<math>G</math>被称作'''super-connected'''或者 '''super-κ'''。如果<math>G</math>删除了每一个最小的割点集之后图都会分成两个连通分量，并且其中一个是单点，那么图<math>G</math>被称作'''hyper-connected'''或'''hyper-κ'''。 如果图上删除了每一个最小的割点集之后都分成了两个连通分量，则图<math>G</math>被称作'''semi-hyper-connected'''或'''semi-hyper-κ'''。<ref>{{Cite journal|last=Liu|first=Qinghai|last2=Zhang|first2=Zhao|date=2010-03-01|title=The existence and upper bound for two types of restricted connectivity|url=https://www.researchgate.net/publication/235246832|journal=Discrete Applied Mathematics|volume=158|issue=5|pages=516–521|doi=10.1016/j.dam.2009.10.017}}</ref>

一个割点集<math>X</math>被称作non-trivial的，如果对于任意不属于<math>X</math>的顶点<math>v</math>，其邻域<math>N(u)</math>都不包含在<math>X</math>中。<math>G</math>的'''superconnectivity'''可以被表示成：
<math>\kappa(G)=</math>= min{|X| : X is a non-trivial cutset}.

一个non-trivial 割边和'''edge-superconnectivity''' λ1(G)可以被类似地定义。<ref>{{Cite journal|last=Balbuena|first=Camino|last2=Carmona|first2=Angeles|date=2001-10-01|title=On the connectivity and superconnectivity of bipartite digraphs and graphs|journal=Ars Combinatorica|volume=61|pages=3–22}}</ref>


== 门格尔定理 ==
图论中关于连通性最重要的定理之一[[门格尔定理]]，它用顶点之间独立路径的个数刻画了图点连通和边连通度。令
<math>u</math>，<math>v</math>为图<math>G</math>的两个顶点，一系列连接<math>u</math>和<math>v</math>的路径被称作点独立的，如果它们之间除了<math>u</math>，<math>v</math>之外，不会有相同的顶点。类似地，它们被称作边独立的，如果它们不会有相同的边。<math>u</math>
和<math>u</math>点独立的路径的个数被记作<math>\kappa'(u,v)</math>，边独立的路径的个数被记作<math>\lambda'(u,v)</math>。
门格尔定理告诉我们，若<math>u</math>
，<math>v</math>不相同，则<math>\lambda'(u,v)=\lambda(u,v)</math>，若<math>u</math>，<math>v</math>不相同且不相邻，则
<math>\kappa'(u,v)=\kappa(u,v)</math><ref>{{cite book|title=Algorithmic Graph Theory|url=https://archive.org/details/algorithmicgraph0000gibb| author=Gibbons, A.|year=1985|publisher=[[Cambridge University Press]]}}</ref><ref>{{cite book|title=Algorithmic Aspects of Graph Connectivity|author1=Nagamochi, H. |author2=Ibaraki, T. | year=2008 |publisher=Cambridge University Press}}</ref> 。
事实上，这其实是[[最大流最小割定理]]的特殊情况。

== 连通度的计算方面 ==
判断两个顶点是否连通这一问题可以被[[搜索算法]]迅速的解决，例如[[广度优先算法]]。更一般地，判断一个图是否连通，以及一个图连通分量的计数问题可以被较快地解决（例如使用[[并查集]]，一个简单算法的伪代码可以写成：

# 从<math>G</math>的任意一个顶点开始
# 使用深度优先或广度优先搜索所有与该顶点连通的顶点，并计数
# 搜索完成，如果计数等于<math>G</math>的阶数，则<math>G</math>是连通的，否则<math>G</math>不连通。

根据门格尔定理，在连通图<math>G</math>上，对于任意一对顶点<math>u</math>，<math>v</math>，<math>\kappa(u,v)</math>，<math>\lambda(u,v)</math>可以通过最大流最小割算法迅速的计算，因此，<math>G</math>的边连通度和点联通度分别作为<math>\kappa(u,v)</math>，<math>\lambda(u,v)</math>的最小值，可以被迅速地计算。

=== 连通图的个数 ===
<math>n</math>阶（小于等于16）的不同的连通图的个数在 [[On-Line Encyclopedia of Integer Sequences]]中被记录在 {{OEIS link|A001187}}中，前几个份量是
<center>
{| class="wikitable"
|-
! ''n''
! 个数
|-
! 2
| 1
|-
! 3
| 4
|-
! 4
| 38
|-
! 5
| 728
|-
! 6
| 26704
|-
! 7
| 1866256
|-
! 8
| 251548592
|}
</center>

== 一些例子 ==
* 不连通图的边连通度和点连通度均为<math>0</math>
* 1-点连通等价于阶数大于等于<math>2</math>的图的连通性。
* <math>n</math>阶完全图的边连通度是<math>n-1</math>,其他类型的<math>n</math>阶图的边连通度严格小于<math>n-1</math>
* 在[[树 (图论)|树]]中，任意两个顶点之间的局部边连通度都是<math>1</math>

== 其他性质 ==
* 连通性被图[[同态]]保持
* 如果<math>G</math>是连通的，则它的[[线图]]<math>L(G)</math>也是连通的
* 图<math>G</math>是2-边连通的，当且仅当它有一个定向，且是强连通的。
* 根据[[Gabriel Andrew Dirac|G. A. Dirac]]的结论，如果图<math>G</math>是<math>k</math>-点连通的，且<math>k\geqslant2</math>，则对于每k个顶点组成的集合，存在一个环经过这个集合上所有的顶点。<ref>{{Cite journal | last = Dirac | first = Gabriel Andrew | authorlink = Gabriel Andrew Dirac | journal = [[Mathematische Nachrichten]] | pages = 61–85 | title = In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen | volume = 22 | issue = 1–2 | year = 1960 | mr = 0121311 | doi = 10.1002/mana.19600220107}}.</ref><ref>{{Cite journal | last1 = Flandrin | first1 = Evelyne | last2 = Li | first2 = Hao
 | last3 = Marczyk | first3 = Antoni | last4 = Woźniak | first4 = Mariusz | doi = 10.1016/j.disc.2005.11.052 | issue = 7–8
 | journal = Discrete Mathematics | pages = 878–884 | title = A generalization of Dirac's theorem on cycles through {{mvar|k}} vertices in {{mvar|k}}-connected graphs | volume = 307 | year = 2007 | mr = 2297171}}.</ref> 在<math>k=2</math>时，反过来亦成立。

* 一个无向图''G''= (''V'',''E'')是连通的，那么边的数目大于等于[[顶点 (图论)|顶点]]的数目减一：<math> |E| \ge |V|-1</math>，而反之不成立。

* 如果''G''= (''V'',''E'')是有向图，那么它是强连通图的必要条件是边的数目大于等于顶点的数目：<math> |E| \ge |V|</math>，而反之不成立。

* 没有回路的无向图是连通的当且仅当它是[[树 (图论)|树]]，即等价于：<math>\displaystyle |E| = |V|-1</math>。

== 参见 ==
* [[代数连通度]]
* [[Cheeger constant (graph theory)]]
* [[Dynamic connectivity]], [[并查集]]
* [[扩展图]]
* [[Strength of a graph]]
== 參考文獻 ==
{{reflist}}
{{图论}}
[[Category:图]]