分量 (图论)

在图论中，分量（英语：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]