元件 (圖論)：修订间差异

删除的内容添加的内容

行内

2022年11月6日 (日) 06:09的版本

在圖論中，元件又稱為連通元件、元件、或分支^[1]，是一個無向子圖，在元件中的任何兩個頂點都可以經由該圖上的邊抵達另一個頂點，且沒有任何一邊可以連到其他子圖的頂點。例如右圖中的無向圖可以分成3個無向子圖，也就是3個元件。沒有與任何其他頂點相連的單一頂點也可以算是一個元件。

如果圖是一個有向圖，而每2個頂點都存在可以來回該頂點的路徑則稱為強連通元件；而若圖上任兩個點之間皆有不止一條路徑連通，則稱為雙連通元件（英语：Biconnected component）。

定义与示例

无向图的连通分量的定义是一个连通子图，且其不是某个更大的连通子图的一部分。例如，第一幅图有三个分量。图的每个顶点 $v$ 属于一个该图的分量，其同时也是 $v$ 可到达（英语：Reachability）的顶点所构成的集合的导出子图。^[2]每个图都是它的分量构成的不相交并（英语：Disjoint union of graphs）。^[3] 更多示例包括如下特殊情况：

在空图中，每个顶点形成一个有一个顶点和零条边的分量。^[4] 更加一般地说，任意图中的每个孤立顶点都会形成这种分量。^[5]
在连通图中，有且仅有一个分量，它就是整个图。^[4]
在森林中，每个分量是一棵树。^[6]
在聚类图（英语：Cluster graph）中，每个分量是一个极大团。这些图可以作为任意无向图的传递闭包产生，对于这些图来说，找到传递闭包是确定连通分量的等价表述。^[7]

分量的另一个定义涉及定义在图的顶点上的等价关系的等价类。在无向图中，如果有一条从 $u$ 到 $v$ 的路径，那么顶点 $u$ 就 "可到达" $v$ 。

可达性是一种等价关系，因为：

它是自反关系。从任何顶点到它本身都有一条长度为零的平凡路径。
它是对称关系。如果有一条从 $u$ 到 $v$ 的路径，同样的边以相反的顺序形成一条从 $v$ 到 $u$ 的路径。
它是传递关系。如果有一条从 $u$ 到 $v$ 的路径和一条从 $v$ 到 $w$ 的路径，这两条路径可以串联起来，形成一条从 $u$ 到 $w$ 的路径。

这种关系的等价类将图的顶点划分为不相交集，即顶点的子集，这些子集相互之间都是可达的，在这些子集之外没有额外的可达对。每个顶点正好属于一个等价类。那么，分量就是这些等价类中的每一个所形成的导出子图。^[8]另外，有些资料将分量定义为顶点的集合，而不是它们所导出的子图。^[9]

參見

強連通元件

參考文獻

^ Diestel. 图论 (PDF). （原始内容存档 (PDF)于2019-05-03）.
^ Clark, John; Holton, Derek Allan, A First Look at Graph Theory, Allied Publishers: 28, 1995, ISBN 9788170234630
^ Joyner, David; Nguyen, Minh Van; Phillips, David, 1.6.1 Union, intersection, and join, Algorithmic Graph Theory and Sage 0.8-r1991, Google: 34–35, May 10, 2013
^ ^4.0 ^4.1 Tutte, W. T., Graph Theory, Encyclopedia of Mathematics and its Applications 21, Reading, Massachusetts: Addison-Wesley: 15, 1984, ISBN 0-201-13520-5, MR 0746795
^ Thulasiraman, K.; Swamy, M. N. S., Graphs: Theory and Algorithms, John Wiley & Sons: 9, 2011, ISBN 978-1-118-03025-7
^ Bollobás, Béla, Modern Graph Theory, Graduate Texts in Mathematics 184, New York: Springer-Verlag: 6, 1998, ISBN 0-387-98488-7, MR 1633290, doi:10.1007/978-1-4612-0619-4
^ McColl, W. F.; Noshita, K., On the number of edges in the transitive closure of a graph, Discrete Applied Mathematics, 1986, 15 (1): 67–73, MR 0856101, doi:10.1016/0166-218X(86)90020-X
^ Foldes, Stephan, Fundamental Structures of Algebra and Discrete Mathematics, John Wiley & Sons: 199, 2011, ISBN 978-1-118-03143-8
^ Siek, Jeremy; Lee, Lie-Quan; Lumsdaine, Andrew, 7.1 Connected components: Definitions, The Boost Graph Library: User Guide and Reference Manual, Addison-Wesley: 97–98, 2001

Hopcroft, J.; Tarjan, R., Algorithm 447: efficient algorithms for graph manipulation, Communications of the ACM, 1973, 16 (6): 372–378, doi:10.1145/362248.362272
Lewis, Harry R.; Papadimitriou, Christos H., Symmetric space-bounded computation, Theoretical Computer Science, 1982, 19 (2): 161–187, doi:10.1016/0304-3975(82)90058-5
Reingold, Omer, Undirected connectivity in log-space, Journal of the ACM, 2008, 55 (4): Article 17, 24 pages, doi:10.1145/1391289.1391291
Shiloach, Yossi; Even, Shimon, An on-line edge-deletion problem, Journal of the ACM, 1981, 28 (1): 1–4, doi:10.1145/322234.322235

[1] Diestel. 图论 (PDF). （原始内容存档 (PDF)于2019-05-03）.

[2] Clark, John; Holton, Derek Allan, A First Look at Graph Theory, Allied Publishers: 28, 1995, ISBN 9788170234630

[3] Joyner, David; Nguyen, Minh Van; Phillips, David, 1.6.1 Union, intersection, and join, Algorithmic Graph Theory and Sage 0.8-r1991, Google: 34–35, May 10, 2013

[:0-4] 4.0 ^4.1 Tutte, W. T., Graph Theory, Encyclopedia of Mathematics and its Applications 21, Reading, Massachusetts: Addison-Wesley: 15, 1984, ISBN 0-201-13520-5, MR 0746795

[5] Thulasiraman, K.; Swamy, M. N. S., Graphs: Theory and Algorithms, John Wiley & Sons: 9, 2011, ISBN 978-1-118-03025-7

[6] Bollobás, Béla, Modern Graph Theory, Graduate Texts in Mathematics 184, New York: Springer-Verlag: 6, 1998, ISBN 0-387-98488-7, MR 1633290, doi:10.1007/978-1-4612-0619-4

[mcnosh-7] McColl, W. F.; Noshita, K., On the number of edges in the transitive closure of a graph, Discrete Applied Mathematics, 1986, 15 (1): 67–73, MR 0856101, doi:10.1016/0166-218X(86)90020-X

[foldes-8] Foldes, Stephan, Fundamental Structures of Algebra and Discrete Mathematics, John Wiley & Sons: 199, 2011, ISBN 978-1-118-03143-8

[boost-9] Siek, Jeremy; Lee, Lie-Quan; Lumsdaine, Andrew, 7.1 Connected components: Definitions, The Boost Graph Library: User Guide and Reference Manual, Addison-Wesley: 97–98, 2001

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

@@ 第6行： / 第6行： @@
 如果圖是一個有向圖，而每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}}</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}}</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}}</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}}</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}}</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}}</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>
 == 參見 ==
@@ 第11行： / 第42行： @@
 == 參考文獻 ==
-{{Refbegin|2}}
+{{Refbegin|1}}
 {{Reflist}}
-#{{citation| first1 = J.| first2 = R.| last1 = Hopcroft | author1-link = John Hopcroft| 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 = 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|author1-link=Harry R. Lewis|first2=Christos H.|last2=Papadimitriou|author2-link=Christos Papadimitriou|title=Symmetric space-bounded computation|journal=[[Theoretical Computer Science (journal)|Theoretical Computer Science]] | pages=161–187|year=1982|doi=10.1016/0304-3975(82)90058-5|volume=19|issue=2}}
+#{{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|authorlink=Omer Reingold|title=Undirected connectivity in log-space|journal=[[Journal of the ACM]]|year=2008|
+#{{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 | author2-link = Shimon Even | 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}}
+#{{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:图论]]