无向图的连通分量的定义是一个连通子图,且其不是某个更大的连通子图的一部分。例如,第一幅图有三个分量。图的每个顶点属于一个该图的分量,其同时也是可到达(英语:Reachability)的顶点所构成的集合的导出子图。[2]每个图都是它的分量构成的不相交并(英语:Disjoint union of graphs)。[3] 更多示例包括如下特殊情况:
^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.04.1Tutte, 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
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
七月 07, 2023
元件, 圖論, 在圖論中, 元件又稱為連通元件, 元件, 或分支, 是一個無向子圖, 在元件中的任何兩個頂點都可以經由該圖上的邊抵達另一個頂點, 且沒有任何一邊可以連到其他子圖的頂點, 例如右圖中的無向圖可以分成3個無向子圖, 也就是3個元件, 沒有與任何其他頂點相連的單一頂點也可以算是一個元件, 有3個元件的圖, 如果圖是一個有向圖, 而每2個頂點都存在可以來回該頂點的路徑則稱為強連通元件, 而若圖上任兩個點之間皆有不止一條路徑連通, 則稱為雙連通元件, 英语, biconnected, component, 定. 在圖論中 元件又稱為連通元件 元件 或分支 1 是一個無向子圖 在元件中的任何兩個頂點都可以經由該圖上的邊抵達另一個頂點 且沒有任何一邊可以連到其他子圖的頂點 例如右圖中的無向圖可以分成3個無向子圖 也就是3個元件 沒有與任何其他頂點相連的單一頂點也可以算是一個元件 有3個元件的圖 如果圖是一個有向圖 而每2個頂點都存在可以來回該頂點的路徑則稱為強連通元件 而若圖上任兩個點之間皆有不止一條路徑連通 則稱為雙連通元件 英语 Biconnected component 定义与示例 编辑 有七个分量的聚类图 英语 Cluster graph 无向图的连通分量的定义是一个连通子图 且其不是某个更大的连通子图的一部分 例如 第一幅图有三个分量 图的每个顶点v displaystyle v 属于一个该图的分量 其同时也是v displaystyle v 可到达 英语 Reachability 的顶点所构成的集合的导出子图 2 每个图都是它的分量构成的不相交并 英语 Disjoint union of graphs 3 更多示例包括如下特殊情况 在空图中 每个顶点形成一个有一个顶点和零条边的分量 4 更加一般地说 任意图中的每个孤立顶点都会形成这种分量 5 在连通图中 有且仅有一个分量 它就是整个图 4 在森林中 每个分量是一棵树 6 在聚类图 英语 Cluster graph 中 每个分量是一个极大团 这些图可以作为任意无向图的传递闭包产生 对于这些图来说 找到传递闭包是确定连通分量的等价表述 7 分量的另一个定义涉及定义在图的顶点上的等价关系的等价类 在无向图中 如果有一条从u displaystyle u 到v displaystyle v 的路径 那么顶点u displaystyle u 就 可到达 v displaystyle v 可达性是一种等价关系 因为 它是自反关系 从任何顶点到它本身都有一条长度为零的平凡路径 它是对称关系 如果有一条从u displaystyle u 到v displaystyle v 的路径 同样的边以相反的顺序形成一条从v displaystyle v 到u displaystyle u 的路径 它是传递关系 如果有一条从u displaystyle u 到v displaystyle v 的路径和一条从v displaystyle v 到w displaystyle w 的路径 这两条路径可以串联起来 形成一条从u displaystyle u 到w displaystyle 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 amp Sons 9 2011 2022 11 06 ISBN 978 1 118 03025 7 原始内容存档于2022 01 07 Bollobas Bela 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 amp 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 取自 https zh wikipedia org w index php title 元件 圖論 amp oldid 76081931, 维基百科,wiki,书籍,书籍,图书馆,