连通图和连通分量

桃扇骨 2021-11-02 02:24 363阅读 0赞

**连通图和连通分量    
  
1．顶点间的连通性**  
  　  在无向图G中，若从顶点vi到顶点vj有路径(当然从vj到vi也一定有路径)，[快看小说网][Link 1]则称vi和vj是连通的。  
  
**2．连通图**  
    　若V(G)中任意两个不同的顶点vi和vj都连通(即有路径)，则称G为连通图(Con-nected Graph)。  
【例】图G2，和G3是连通图。  
     
     ![20170505161107755][]![点击并拖拽以移动][Image 1]  
**3．连通分量**  
    　无向图G的极大连通子图称为G的最强连通分量(Connected Component)。  
  注意：  
　　① 任何连通图的连通分量只有一个，即是其自身  
    　② 非连通的无向图有多个连通分量。  
  【例】下图中的G4是非连通图，它有两个连通分量H1和H2。  
          ![20170505161156256][]![点击并拖拽以移动][Image 1]  
  
**强连通图和强连通分量**  
  
**1．强连通图**  
　    有向图G中，若对于V(G)中任意两个不同的顶点vi和vj，[情定三生：首席医少赖上门][Link 2]都存在从vi到vj以及从vj到vi的路径，则称G是强连通图。  
  
**2．强连通分量**  
    　有向图的极大强连通子图称为G的强连通分量。  
注意：  
    　① 强连通图只有一个强连通分量，即是其自身。  
    　② 非强连通的有向图有多个强连分量。  
【例】下图中的G1不是强连通图，因为v3到v2没有路径，但它有两个强连通分量，如右图所示。  
  
                
![20170505161222896][]![点击并拖拽以移动][Image 1]  
**网络(Network)**  
  
　    若将图的每条边都赋上一个权，则称这种带权图为网络([超级人生][Link 3])。  
注意：  
　    权是表示两个顶点之间的距离、耗费等具有某种意义的数。

【例】下图就是一个网络的例子。

![20170505161246733][]![点击并拖拽以移动][Image 1]

转载于:https://www.cnblogs.com/Katerina/p/11336043.html

[Link 1]: http://www.kuaikanxs.cc
[20170505161107755]: https://img-blog.csdn.net/20170505161107755
[Image 1]: 
[20170505161156256]: https://img-blog.csdn.net/20170505161156256
[Link 2]: http://www.kuaikanxs.cc/book/5647/
[20170505161222896]: https://img-blog.csdn.net/20170505161222896
[Link 3]: http://www.kuaikanxs.cc/book/8454/
[20170505161246733]: https://img-blog.csdn.net/20170505161246733