面些毛子种枚大票 第二讲：基本概念 XIDIAN UNIVERSITY 1. 网络的图表示 图的连通性。在一个有向图G中，如果存在从节点y,到节点y,的路径，则称y 和y是连通的。如果图中任意两点都是连通的，那么这个图是连通图。如果G 是无向图，如果存在从节点v,到节点y的路径，那么也必然存在从y,到y,的路径。 强连通图：对于有向图G,若对于任意两个不同的节点y,和y,都存在从v到y 以及从v,到y,的路径，则称G是强连通图。 弱连通图：对于有向图G,将所有的有向边替换为无向边，所得到的图称为 原有向图的基图。如果一个有向图的基图是连通图，则该有向图是弱连通图。 (c) 问题：左图是强连通图还是弱连通图？ 6 1. 网络的图表示 第二讲：基本概念 6 图的连通性。在一个有向图 G 中，如果存在从节点vi到节点vj的路径，则称vi 和vj是连通的。如果图中任意两点都是连通的，那么这个图是连通图。如果G 是无向图，如果存在从节点vi到节点vj的路径，那么也必然存在从vj到vi的路径。 强连通图：对于有向图 G，若对于任意两个不同的节点vi和vj，都存在从vi到vj 以及从vj到vi的路径，则称 G是强连通图。 弱连通图：对于有向图 G，将所有的有向边替换为无向边，所得到的图称为 原有向图的基图。如果一个有向图的基图是连通图，则该有向图是弱连通图。 3 1 2 4 5 (c) 问题：左图是强连通图还是弱连通图？