Loading AI tools
特定頂點及所有與其具有路徑連通之極大連通子圖 来自维基百科,自由的百科全书
在圖論中,元件(英語:Component)又稱為連通元件、分量、或分支[1],是一個無向子圖,在元件中的任何兩個頂點都可以經由該圖上的邊抵達另一個頂點,且沒有任何一邊可以連到其他子圖的頂點。例如右圖中的無向圖可以分成3個無向子圖,也就是3個元件。沒有與任何其他頂點相連的單一頂點也可以算是一個元件。
如果圖是一個有向圖,而每2個頂點都存在可以來回該頂點的路徑則稱為強連通元件;而若圖上任兩個點之間皆有不止一條路徑連通,則稱為雙連通元件。
無向圖的連通分量的定義是一個連通子圖,且其不是某個更大的連通子圖的一部分。例如,第一幅圖有三個分量。圖的每個頂點屬於一個該圖的分量,其同時也是可到達的頂點所構成的集合的導出子圖。[2]每個圖都是它的分量構成的不相交並。[3] 更多示例包括如下特殊情況:
分量的另一個定義涉及定義在圖的頂點上的等價關係的等價類。在無向圖中,如果有一條從到的路徑,那麼頂點就「可到達」。
可達性是一種等價關係,因為:
這種關係的等價類將圖的頂點劃分為不相交集,即頂點的子集,這些子集相互之間都是可達的,在這些子集之外沒有額外的可達對。每個頂點正好屬於一個等價類。那麼,分量就是這些等價類中的每一個所形成的導出子圖。[8]另外,有些資料將分量定義為頂點的集合,而不是它們所導出的子圖。[9]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.