证明:若一个有向图(强连通分量已被视为新的顶点)中不存在入度为0的顶点和出度为0的顶点,则其必是强连通图

时间:2024-05-22 21:37:45

要证明的问题:

       若一个有向图(强连通分量已被视为新的顶点,即图中没有强连通分量)中不存在入度为0的顶点和出度为0的顶点,则该有向图必是强连通图。

(强连通图:任取两个不同的顶点a和b,a都可以到达b)

要证:是强连通图,

即证:任取顶点 i 、j (i和j是不同顶点),i可到达j,

即证:假设i不可到达j,必产生矛盾。

 

那么就用假设法,假设i不可到达j:

看到达j的路径:看j的上1个点,上2个点,……,上n个点;

证明:若一个有向图(强连通分量已被视为新的顶点)中不存在入度为0的顶点和出度为0的顶点,则其必是强连通图

再看i走出去的路径:看i的下1个点,下2个点,......,下m个点;

证明:若一个有向图(强连通分量已被视为新的顶点)中不存在入度为0的顶点和出度为0的顶点,则其必是强连通图

 

因为不存在入度为0的顶点,所以j(-n)顶点必有其来路。由于根据假设i不可到j,所以其来路只能在链(1)中。但是如果这样,则链(1)中有环,环是强连通分量,与条件相矛盾。所以j(-n)顶点的上一顶点只能来自链(2);同理,i(m)顶点的下一顶点只能来自链(1)。

 

所以,i可到达j;

<=>假设失败;

<=>该有向图是强连通图。