元件 (圖論)

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

有3個元件的圖。

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

參見

參考文獻
  1. Diestel. (PDF). （原始内容存档 (PDF)于2019-05-03）.
  1. Hopcroft, J.; Tarjan, R., , Communications of the ACM, 1973, 16 (6): 372–378, doi:10.1145/362248.362272
  2. Lewis, Harry R.; Papadimitriou, Christos H., , Theoretical Computer Science, 1982, 19 (2): 161–187, doi:10.1016/0304-3975(82)90058-5
  3. Reingold, Omer, , Journal of the ACM, 2008, 55 (4): Article 17, 24 pages, doi:10.1145/1391289.1391291
  4. Shiloach, Yossi; Even, Shimon, , Journal of the ACM, 1981, 28 (1): 1–4, doi:10.1145/322234.322235
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.