查看“︁元件 (圖論)”︁的源代码

{{noteTA 
|1=zh-hans:分量;zh-hant:元件
}}
[[Image:Pseudoforest.svg|thumb|240px|有3個元件的圖]]
在[[圖論]]中，'''元件'''（{{lang-en|Component}}）又稱為'''連通元件'''、'''-{zh-hant:分量;zh-hans:元件;}-'''、或'''分支'''<ref>{{Cite web|url=http://diestel-graph-theory.com/Chinese/ChineseSample5.pdf|title=图论|accessdate=|author=Diestel|date=|publisher=|archive-date=2019-05-03|archive-url=https://web.archive.org/web/20190503033303/http://diestel-graph-theory.com/Chinese/ChineseSample5.pdf|dead-url=no}}</ref>，是一個無向子圖，在元件中的任何兩個頂點都可以經由該圖上的邊抵達另一個頂點，且沒有任何一邊可以連到其他子圖的頂點。例如右圖中的無向圖可以分成3個無向子圖，也就是3個元件。沒有與任何其他頂點相連的單一頂點也可以算是一個元件。

如果圖是一個有向圖，而每2個頂點都存在可以來回該頂點的路徑則稱為[[強連通元件]]；而若圖上任兩個點之間皆有不止一條路徑連通，則稱為{{link-en|雙連通元件|Biconnected component}}。

== 定义与示例 ==
[[File:Equivalentie.svg|thumb|有七个分量的{{En-link|聚类图|Cluster graph}}]]
无向图的连通分量的定义是一个连通子图，且其不是某个更大的连通子图的一部分。例如，第一幅图有三个分量。图的每个顶点<math>v</math>属于一个该图的分量，其同时也是<math>v</math>{{En-link|可达性|Reachability|可到达}}的顶点所构成的集合的[[导出子图]]。<ref>{{citation|last1=Clark|first1=John|last2=Holton|first2=Derek Allan|isbn=9788170234630|page=28|publisher=Allied Publishers|title=A First Look at Graph Theory|url=https://books.google.com/books?id=kb-aLlgYZuEC&pg=PA28|year=1995|accessdate=2022-11-06|archive-date=2022-01-08|archive-url=https://web.archive.org/web/20220108225127/https://books.google.com/books?id=kb-aLlgYZuEC&pg=PA28|dead-url=no}}</ref>每个图都是它的分量构成的{{En-link|不相交并(图论)|Disjoint union of graphs|不相交并}}。<ref>{{citation|last1=Joyner|first1=David|last2=Nguyen|first2=Minh Van|last3=Phillips|first3=David|contribution=1.6.1 Union, intersection, and join|contribution-url=https://code.google.com/p/graphbook/|date=May 10, 2013|edition=0.8-r1991|pages=34–35|publisher=Google|title=Algorithmic Graph Theory and Sage|accessdate=2022-11-06|archive-date=2016-01-16|archive-url=https://web.archive.org/web/20160116090036/https://code.google.com/p/graphbook/|dead-url=no}}</ref> 更多示例包括如下特殊情况：
*在[[空圖|空图]]中，每个顶点形成一个有一个顶点和零条边的分量。<ref name=":0">{{citation|last=Tutte|first=W. T.|isbn=0-201-13520-5|mr=746795|page=15|publisher=Addison-Wesley|location=Reading, Massachusetts|series=Encyclopedia of Mathematics and its Applications|title=Graph Theory|url=https://books.google.com/books?id=uTGhooU37h4C&pg=PA15|volume=21|year=1984|accessdate=2022-11-06|archive-date=2022-01-07|archive-url=https://web.archive.org/web/20220107081347/https://books.google.com/books?id=uTGhooU37h4C&pg=PA15|dead-url=no}}</ref> 更加一般地说，任意图中的每个孤立[[顶点 (图论)|顶点]]都会形成这种分量。<ref>{{citation|last1=Thulasiraman|first1=K.|last2=Swamy|first2=M. N. S.|isbn=978-1-118-03025-7|page=9|publisher=John Wiley & Sons|title=Graphs: Theory and Algorithms|url=https://books.google.com/books?id=rFH7eQffQNkC&pg=PA9|year=2011|accessdate=2022-11-06|archive-date=2022-01-07|archive-url=https://web.archive.org/web/20220107215533/https://books.google.com/books?id=rFH7eQffQNkC&pg=PA9|dead-url=no}}</ref>
*在[[连通图]]中，有且仅有一个分量，它就是整个图。<ref name=":0" />
*在[[森林 (图论)|森林]]中，每个分量是一棵[[树 (图论)|树]]。<ref>{{citation|last=Bollobás|first=Béla|doi=10.1007/978-1-4612-0619-4|isbn=0-387-98488-7|mr=1633290|page=6|publisher=Springer-Verlag|location=New York|series=Graduate Texts in Mathematics|title=Modern Graph Theory|url=https://books.google.com/books?id=JeIlBQAAQBAJ&pg=PA6|volume=184|year=1998|accessdate=2022-11-06|archive-date=2022-01-08|archive-url=https://web.archive.org/web/20220108192625/https://books.google.com/books?id=JeIlBQAAQBAJ&pg=PA6|dead-url=no}}</ref>
*在{{En-link|聚类图|Cluster graph}}中，每个分量是一个[[极大团]]。这些图可以作为任意无向图的[[传递闭包]]产生，对于这些图来说，找到传递闭包是确定连通分量的等价表述。<ref name="mcnosh">{{citation|last1=McColl|first1=W. F.|last2=Noshita|first2=K.|doi=10.1016/0166-218X(86)90020-X|issue=1|journal=Discrete Applied Mathematics|mr=856101|pages=67–73|title=On the number of edges in the transitive closure of a graph|volume=15|year=1986}}</ref>

分量的另一个定义涉及定义在图的顶点上的[[等价关系]]的等价类。在无向图中，如果有一条从<math>u</math>到<math>v</math>的[[路径 (图论)|路径]]，那么顶点<math>u</math>就“可到达”<math>v</math>。

可达性是一种等价关系，因为：
*它是[[自反关系]]。从任何顶点到它本身都有一条长度为零的平凡路径。
*它是[[对称关系]]。如果有一条从<math>u</math>到<math>v</math>的路径，同样的边以相反的顺序形成一条从<math>v</math>到<math>u</math>的路径。
*它是[[传递关系]]。如果有一条从<math>u</math>到<math>v</math>的路径和一条从<math>v</math>到<math>w</math>的路径，这两条路径可以串联起来，形成一条从<math>u</math>到<math>w</math>的路径。
这种关系的[[等价类]]将图的顶点划分为[[不相交集]]，即顶点的子集，这些子集相互之间都是可达的，在这些子集之外没有额外的可达对。每个顶点正好属于一个等价类。那么，分量就是这些等价类中的每一个所形成的[[导出子图]]。<ref name="foldes">{{citation
 | last = Foldes
 | first = Stephan
 | isbn = 978-1-118-03143-8
 | page = 199
 | publisher = John Wiley & Sons
 | title = Fundamental Structures of Algebra and Discrete Mathematics
 | url = https://books.google.com/books?id=A59RivXPMzkC&pg=PA199
 | year = 2011
 | accessdate = 2022-11-06
 | archive-date = 2022-01-07
 | archive-url = https://web.archive.org/web/20220107080529/https://books.google.com/books?id=A59RivXPMzkC&pg=PA199
 | dead-url = no
 }}</ref>另外，有些资料将分量定义为顶点的集合，而不是它们所导出的子图。<ref name="boost">{{citation
 | last1 = Siek | first1 = Jeremy
 | last2 = Lee | first2 = Lie-Quan
 | last3 = Lumsdaine | first3 = Andrew
 | contribution = 7.1 Connected components: Definitions
 | pages = 97–98
 | publisher = Addison-Wesley
 | title = The Boost Graph Library: User Guide and Reference Manual
 | year = 2001}}</ref>

== 參見 ==
*[[強連通元件]]

== 參考文獻 ==
{{Refbegin|1}}
{{Reflist}}
#{{citation| first1 = J.| first2 = R.| last1 = Hopcroft | author1-link = 約翰·霍普克洛夫特| last2 =  Tarjan | author2-link = Robert Tarjan | title = Algorithm 447: efficient algorithms for graph manipulation| journal = [[Communications of the ACM]] | volume = 16| issue = 6| pages = 372–378| year = 1973| doi = 10.1145/362248.362272}}
#{{citation|first1=Harry R.|last1=Lewis|first2=Christos H.|last2=Papadimitriou|author2-link=赫里斯托斯·帕帕季米特里乌|title=Symmetric space-bounded computation|journal=Theoretical Computer Science | pages=161–187|year=1982|doi=10.1016/0304-3975(82)90058-5|volume=19|issue=2}}
#{{citation|first=Omer|last=Reingold|title=Undirected connectivity in log-space|journal=[[Journal of the ACM]]|year=2008|
volume=55|issue=4|pages=Article 17, 24 pages|doi=10.1145/1391289.1391291}}
#{{citation | last1 = Shiloach | first1 = Yossi | last2 = Even | first2 = Shimon | doi = 10.1145/322234.322235 | issue = 1 | journal = [[Journal of the ACM]] | pages = 1–4 | title = An on-line edge-deletion problem | volume = 28 | year = 1981}}
{{Refend}}
[[Category:图论]]
[[Category:图的连通性]]