元件 (圖論)

有3個元件的圖

在圖論中，元件（Template:Lang-en）又稱為連通元件、-{zh-hant:分量;zh-hans:元件;}-、或分支，是一個無向子圖，在元件中的任何兩個頂點都可以經由該圖上的邊抵達另一個頂點，且沒有任何一邊可以連到其他子圖的頂點。例如右圖中的無向圖可以分成3個無向子圖，也就是3個元件。沒有與任何其他頂點相連的單一頂點也可以算是一個元件。

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

定义与示例

有七个分量的Template:En-link

无向图的连通分量的定义是一个连通子图，且其不是某个更大的连通子图的一部分。例如，第一幅图有三个分量。图的每个顶点$v$属于一个该图的分量，其同时也是$v$Template:En-link的顶点所构成的集合的导出子图。每个图都是它的分量构成的Template:En-link。 更多示例包括如下特殊情况：

• 在空图中，每个顶点形成一个有一个顶点和零条边的分量。 更加一般地说，任意图中的每个孤立顶点都会形成这种分量。
• 在连通图中，有且仅有一个分量，它就是整个图。
• 在森林中，每个分量是一棵树。
• 在Template:En-link中，每个分量是一个极大团。这些图可以作为任意无向图的传递闭包产生，对于这些图来说，找到传递闭包是确定连通分量的等价表述。

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

可达性是一种等价关系，因为：

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

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

參見

• 強連通元件

參考文獻

1. Template:Citation
2. Template:Citation
3. Template:Citation
4. Template:Citation