元件 (圖論)

在圖論中，元件（英語：Component）又稱為連通元件、分量、或分支^[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 [2022-11-06], ISBN 9788170234630, （原始內容存檔於2022-01-08）
^ 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 [2022-11-06], （原始內容存檔於2016-01-16）
^ ^4.0 ^4.1 Tutte, W. T., Graph Theory, Encyclopedia of Mathematics and its Applications 21, Reading, Massachusetts: Addison-Wesley: 15, 1984 [2022-11-06], ISBN 0-201-13520-5, MR 0746795, （原始內容存檔於2022-01-07）
^ Thulasiraman, K.; Swamy, M. N. S., Graphs: Theory and Algorithms, John Wiley & Sons: 9, 2011 [2022-11-06], ISBN 978-1-118-03025-7, （原始內容存檔於2022-01-07）
^ Bollobás, Béla, Modern Graph Theory, Graduate Texts in Mathematics 184, New York: Springer-Verlag: 6, 1998 [2022-11-06], ISBN 0-387-98488-7, MR 1633290, doi:10.1007/978-1-4612-0619-4, （原始內容存檔於2022-01-08）
^ 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 [2022-11-06], ISBN 978-1-118-03143-8, （原始內容存檔於2022-01-07）
^ 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 [2022-11-06], ISBN 9788170234630, （原始內容存檔於2022-01-08）

[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 [2022-11-06], （原始內容存檔於2016-01-16）

[:0-4] 4.0 ^4.1 Tutte, W. T., Graph Theory, Encyclopedia of Mathematics and its Applications 21, Reading, Massachusetts: Addison-Wesley: 15, 1984 [2022-11-06], ISBN 0-201-13520-5, MR 0746795, （原始內容存檔於2022-01-07）

[5] Thulasiraman, K.; Swamy, M. N. S., Graphs: Theory and Algorithms, John Wiley & Sons: 9, 2011 [2022-11-06], ISBN 978-1-118-03025-7, （原始內容存檔於2022-01-07）

[6] Bollobás, Béla, Modern Graph Theory, Graduate Texts in Mathematics 184, New York: Springer-Verlag: 6, 1998 [2022-11-06], ISBN 0-387-98488-7, MR 1633290, doi:10.1007/978-1-4612-0619-4, （原始內容存檔於2022-01-08）

[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 [2022-11-06], ISBN 978-1-118-03143-8, （原始內容存檔於2022-01-07）

[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]