图形的"路径矩阵"和"传递闭合"是什么意思(定向和无向)？

Question

我讨论各种图算法,我看到术语"路径矩阵"和"传递闭包",它们在任何地方都没有明确定义.

在Directed和Undirected图的情况下,"Path Matrix"和"Transitive Closure"是什么意思？

Answer 1

我认为unkulunkulu的答案非常完整,但鉴于JMSA似乎不满意,我会再做一次尝试.

让我们不是从路径矩阵开始,而是使用邻接矩阵.邻接矩阵是图的标准表示.如果adj是某个图G的邻接矩阵,则如果顶点i与顶点j相邻(即,从i到j有一条边),则adj [i] [j] == 1,否则为0.换句话说,adj [i] [j] == 1当且仅当我们可以在一个 "步骤"中从顶点i到达顶点j时.

现在,让我们定义的另一个矩阵,我会打电话给ADJ2:ADJ2 [i] [j] == 1当且仅当我们可以从顶点让我到顶点Ĵ在2个步骤或更少.您可以将其称为"两步邻接"矩阵.重要的是adj2可以用adj来定义:

def adj2(i,j):
    if adj(i,j) == 1:
        return 1
    else:
        for k in range(0,n): # where n is the number of vertices in G
            if adj(i,k) == 1 and adj(k,j) == 1:
                return 1
    return 0

也就是说,如果i与j相邻,则adj2 [i] [j]为1(即adj [i] [j] == 1)或者如果存在某些其他顶点k,则可以从i步进到k然后从k到j(即adj [i] [j] == 1和adj [k] [j] == 1).

你可以想像,你可以使用相同的逻辑来定义一个"三步走"的邻接矩阵ADJ3,ADJ4,adj5,等等.如果你继续运行足够长(例如,对于adjn,其中n是图中顶点的数量),你会得到一个矩阵,告诉你是否存在从顶点i到顶点j的任何长度的路径.当然,这也是图的路径矩阵:对于所有i,j,adjn [i] [j] == path [i] [j].(注意:不要将路径矩阵与距离矩阵混淆.)

数学家会说路径[i] [j]是图G上adj [i] [j]的传递闭包.

传递闭包独立于图论; adj不是唯一具有传递闭包的东西.粗略地说,所有带有两个参数并返回布尔值的函数(在编程意义上)都有一个传递闭包.

等式(==)和不等式(<,>,<=,> =)运算符是此类函数的常见示例.然而,这些与adj不同,因为它们本身是可传递的." f(i,j)是传递的"意味着如果f(i,j)== true,并且f(j,k)== true,则f(i,k)== true.你知道这个属性是正确的,例如,"小于"关系:从<b和b <c,你可以推断a <c.传递函数f的传递闭包只是f.

adj通常不具有传递性.考虑图表:

v1---v2---v3

在此图中,adj可能表示函数busBetween(city1,city2).这里有一个总线,你可以从v1到v2(adj [1] [2] == 1)和一个从v2到v3的总线(adj [2] [3] == 1),但是v1没有总线直接到v3(adj [1] [2] == 0).从v1到v3有一条总线路径,但v1和v3不是总线相邻的.对于该曲线图,ADJ不是传递的,所以路径,这是的传递闭包ADJ,不同于ADJ.

如果我们在v1和v3之间添加边,

v1---v2---v3
 \        /
   \----/

然后adj变为传递:在每种可能的情况下,adj [i] [j] == 1和adj [j] [k] == 1意味着adj [i] [k] == 1.对于此图,path和adj是相同的.该图是无向的对应于" 对称性 "属性.如果我们为每个顶点添加循环以使v1,v2和v3各自与它们相邻,那么结果图将是传递的,对称的和" 反身的 ",并且可以说代表集合上的等式(==){ 1,2,3}.

这开始说明图形如何表示不同的函数,以及函数的属性如何反映在图形的属性中.通常,如果让adj表示某个函数f,那么path就是f的传递闭包.

对于传递闭包的正式定义,我建议您使用维基百科.一旦你理解了所有的数学术语,这不是一个难题.

Answer 2

图论中的路径矩阵是一个矩阵大小n*n,其中n是图的顶点数.i第th行和j第th列的元素是图中1是否有从i顶点到jth的路径,0如果没有.

的弗洛伊德算法通常用于计算的路径矩阵.

该定义不区分有向图和无向图,但很明显,对于无向图,矩阵总是对称的.

Transitive Closure是一个类似的概念,但它来自不同的领域.想象一下你有一组对象,对于其中一些你知道一个对象肯定比另一个好,所以你可以写a > b(">"是"更好"的简写).当然,你应该假设,如果a > b 和 b > c再a > c.这称为传递规则.然后对于你想知道的任何两个物体,它们中的一个是否比另一个好,或者它是未知的.这是关闭:首先你有一个可能不具有传递性的关系,但是在假定传递性之后,你可以将它完成到一个传递性关系.

为了解决这个问题在构造有向图,其中一个顶点对应于每一个所提到的对象(a,b,c等),其中的有向边u -> v存在当且仅当u > v.然后你可以构造第一段中定义的路径矩阵,它会给你答案:显然,两个顶点之间的路径的存在等同于一个关系链的存在,因为u > a > b > ... > z > v,传递规则,u > v.

作为传递闭包的旁注,当您询问有向图和无向图时,给出的示例使用非对称关系(>),然后图表被指示,但情况并非总是如此.例如,任何等价关系总是满足传递性,但也必须满足对称性,因此相应的图是无向的.您可以找到对称关系(或图形)的传递闭包.