请输入您要查询的字词:

 

单词 ConnectedGraph
释义

connected graph


A connected graphMathworldPlanetmath is a graph such that there exists a path between all pairs of vertices. If the graph is a directed graphMathworldPlanetmath, and there exists a path from each vertex to every other vertex, then it is a strongly connected graph.

A connected componentMathworldPlanetmathPlanetmathPlanetmath is a maximal (under inclusion) subset of vertices of any graph and any edges between them that forms a connected graph. Similarly, a strongly connected component is a maximal (under inclusion) subset of vertices of any digraph and any edges between them that forms a strongly connected graph. Any graph or digraph is a union of connected or strongly connected components, plus some edges to join the components together. Thus any graph can be decomposed into its connected or strongly connected components. For instance, Tarjan’s algorithmMathworldPlanetmath can decompose any digraph into its strongly connected components.

For example, the following graph and digraph are connected and strongly connected, respectively.

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 23:14:46