热门问题
时间线
聊天
视角
分量 (图论)
特定頂點及所有與其具有路徑連通之極大連通子圖 来自维基百科,自由的百科全书
Remove ads
在图论中,分量(英语:Component)又称为连通分量、元件、或分支[1],是一个无向子图,在分量中的任何两个顶点都可以经由该图上的边抵达另一个顶点,且没有任何一边可以连到其他子图的顶点。例如右图中的无向图可以分成3个无向子图,也就是3个分量。没有与任何其他顶点相连的单一顶点也可以算是一个分量。

如果图是一个有向图,而每2个顶点都存在可以来回该顶点的路径则称为强连通分量;而若图上任两个点之间皆有不止一条路径连通,则称为双连通分量。
定义与示例

无向图的连通分量的定义是一个连通子图,且其不是某个更大的连通子图的一部分。例如,第一幅图有三个分量。图的每个顶点属于一个该图的分量,其同时也是可到达的顶点所构成的集合的导出子图。[2]每个图都是它的分量构成的不相交并。[3] 更多示例包括如下特殊情况:
- 在空图中,每个顶点形成一个有一个顶点和零条边的分量。[4] 更加一般地说,任意图中的每个孤立顶点都会形成这种分量。[5]
- 在连通图中,有且仅有一个分量,它就是整个图。[4]
- 在森林中,每个分量是一棵树。[6]
- 在聚类图中,每个分量是一个极大团。这些图可以作为任意无向图的传递闭包产生,对于这些图来说,找到传递闭包是确定连通分量的等价表述。[7]
分量的另一个定义涉及定义在图的顶点上的等价关系的等价类。在无向图中,如果有一条从到的路径,那么顶点就“可到达”。
可达性是一种等价关系,因为:
- 它是自反关系。从任何顶点到它本身都有一条长度为零的平凡路径。
- 它是对称关系。如果有一条从到的路径,同样的边以相反的顺序形成一条从到的路径。
- 它是传递关系。如果有一条从到的路径和一条从到的路径,这两条路径可以串联起来,形成一条从到的路径。
这种关系的等价类将图的顶点划分为不相交集,即顶点的子集,这些子集相互之间都是可达的,在这些子集之外没有额外的可达对。每个顶点正好属于一个等价类。那么,分量就是这些等价类中的每一个所形成的导出子图。[8]另外,有些资料将分量定义为顶点的集合,而不是它们所导出的子图。[9]
Remove ads
参见
参考文献
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads