元件 (圖論)

特定頂點及所有與其具有路徑連通之極大連通子圖
(重定向自连通分量 (图论)

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

有3個元件的圖

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

定义与示例编辑

 
有七个分量的聚类图英语Cluster graph

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

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

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

可达性是一种等价关系,因为:

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

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

參見编辑

參考文獻编辑

  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 
  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 
  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 
  8. ^ Foldes, Stephan, Fundamental Structures of Algebra and Discrete Mathematics, John Wiley & Sons: 199, 2011, ISBN 978-1-118-03143-8 
  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. 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 
  2. 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 
  3. Reingold, Omer, Undirected connectivity in log-space, Journal of the ACM, 2008, 55 (4): Article 17, 24 pages, doi:10.1145/1391289.1391291 
  4. Shiloach, Yossi; Even, Shimon, An on-line edge-deletion problem, Journal of the ACM, 1981, 28 (1): 1–4, doi:10.1145/322234.322235