“路径矩阵”是什么意思？和“传递闭合”图（直接和无向）？ [英] What does it mean by "Path Matrix" and "Transitive Closure" of a graph (Directed and Undirected)?
问题描述
我讨论了各种图算法，我看到了术语路径矩阵和传递闭包，这些术语在任何地方都没有很好定义。
它是什么意思是路径矩阵和传递闭包的情况下，直接和无向图吗？ 解决方案
我认为unkulunkulu的答案是相当完整，但给予JMSA似乎不满意 ，我会再次尝试。
让我们从路径矩阵开始，但是使用 adjacency matrix 。邻接矩阵是图的标准表示。如果 adj 是某个图 G 的邻接矩阵，则 adj [i] [j] == 1 如果顶点 i 与顶点 j 相邻（即存在从 i 到 j 的边），并且<否则强> 0 。换句话说，当且仅当我们可以从顶点 i 返回顶点 j 时， adj [i] [j] == 1 em> one step。
现在，让我们定义另一个我称之为 adj2 的矩阵： adj2当且仅当我们可以在两个步骤中从顶点 i 到顶点 j 时才得到[i] [j] == 1 或更少。你可以称它为两步邻接矩阵。重要的是 adj2 可以用 adj 来定义：
def adj2（i，j）：
如果adj（i，j）== 1：
返回1
else：
对于范围内的k（0，n） ：＃其中n是G
中的顶点数，如果adj（i，k）== 1且adj（k，j）== 1：
返回1
返回0
也就是说， adj2 [i] [j] 是 1 如果 i 与 j 相邻（即 adj [i] [j] == 1 ）或者是否存在其他顶点 k ，以便您可以从 i 更改为 k ，然后从 k j （即 adj [i] [j] == 1和adj [k] [j] == 1 ）。
可以想象，可以使用相同的逻辑来定义三步邻接矩阵 adj3 ， adj4 ， adj5 < STRONG>， 等等。如果持续时间足够长（例如 adjn ，其中 n 是图中顶点的数目），则会得到一个矩阵，告诉您是否存在任何长度从顶点我到顶点 j 。当然，这也将是图的路径矩阵： adjn [i] [j] ==路径[i] [j]适用于所有i，j 。 （注意：不要将路径矩阵与距离矩阵混淆。）
一位数学家会说， path [i] [j] 是图上 adj [i] [j] 的传递闭包 G 。
传递闭包独立于图论存在; adj 不是唯一具有传递闭包的东西。粗略地说，所有函数（在编程意义上）带有两个参数并返回布尔值有一个传递闭包。
等号（==）和不等号（<，>，< =，> =）运算符是这些函数的熟悉示例。这些不同于 adj ，然而，它们本身就是 传递 的。 f（i，j）是传递性的表示如果 f（i，j）== true ，并且 f（j，k）== true ，然后 f（i，k）== true 。你知道，这个属性对于小于关系是成立的：从 a< b 和 b < c ，您可以推断 a 。 ç即可。传递函数 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 不是可传递的，所以 path 是 adj 的传递闭包，与 adj strong>。
如果我们在v1和v3之间添加一条边，
v1 --- v2 --- v3
\ /
\ ---- /
然后 adj 变成可传递的：在任何情况下， adj [i] [j] == 1 和 adj [j] [k] == 1 意味着 adj [i] [k] == 1 。对于此图，路径和 adj 是相同的。该图是无向的对应于 symmetry 属性。如果我们为每个顶点添加循环，以使v1，v2和v3与它们各自相邻，则生成的图将是传递的，对称的和 reflexive ，可以说是代表集合{1,2,3}上的等号（==）。
<这开始说明图可以如何表示不同的函数，以及函数的属性如何反映在图的属性中。一般来说，如果让 adj 表示某个函数 f ，那么 path 是 f 的传递闭包。 / p>
对于传递闭包的一个正式定义，我把你引用到维基百科。一旦你理解了所有的数学术语，这并不是一个难题。
I the discussion of various graph algorithms, I see the terms "Path Matrix" and "Transitive Closure" which are not well-defined anywhere.
What does it mean by "Path Matrix" and "Transitive Closure" in case of both Directed and Undirected graphs?
I think unkulunkulu's answer is pretty complete, but given JMSA seems unsatisfied, I'll make another attempt.
Let's start not with the path matrix, but with the adjacency matrix. The adjacency matrix is the standard representation of a graph. If adj is the adjacency matrix for some graph G, then adj[i][j] == 1 if vertex i is adjacent to vertex j (i.e. there is an edge from i to j), and 0 otherwise. In other words, adj[i][j] == 1 if and only if we can get from vertex i to vertex j in one "step".
Now, let's define another matrix which I'll call adj2: adj2[i][j] == 1 if and only if we can get from vertex i to vertex j in two steps or less. You might call it a "two-step adjacency" matrix. The important thing is that adj2 can be defined in terms of 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
That is, adj2[i][j] is 1 if i is adjacent to j (i.e. adj[i][j] == 1) or if there exists some other vertex k such that you can step from i to k and then from k to j (i.e. adj[i][j] == 1 and adj[k][j] == 1).
As you can imagine, you can use the same logic to define a "three-step" adjacency matrix adj3, adj4, adj5, and so on. If you go on long enough (e.g. to adjn, where n is the number of vertices in the graph), you get a matrix that tells you whether there's a path of any length from vertex i to vertex j. This, of course, would also be the graph's path matrix: adjn[i][j] == path[i][j] for all i, j. (Note: Don't confuse path matrix with distance matrix.)
A mathematician would say that path[i][j] is the transitive closure of adj[i][j] on the graph G.
Transitive closures exist independently from graph theory; adj is not the only thing with a transitive closure. Roughly speaking, all functions (in the programming sense) that take two arguments and return a Boolean value have a transitive closure.
The equality (==) and inequality (<, >, <=, >=) operators are familiar examples of such functions. These differ from adj, however, in that they are themselves transitive. "f(i,j) is transitive" means that if f(i,j) == true, and f(j,k) == true, then f(i, k) == true. You know that this property is true of, say, the "less than" relation: from a < b and b < c, you can infer that a < c. The transitive closure of a transitive function f is just f.
adj is not generally transitive. Consider the graph:
v1---v2---v3
In this graph, adj might represent the function busBetween(city1, city2). Here, there's a bus you can take from v1 to v2 (adj[1][2] == 1) and a bus from v2 to v3 (adj[2][3] == 1), but there's no bus from v1 directly to v3 (adj[1][2] == 0). There is a bus-path from v1 to v3, but v1 and v3 are not bus-adjacent. For this graph, adj is not transitive, so path, which is the transitive closure of adj, is different from adj.
If we add an edge between v1 and v3,
v1---v2---v3
\ /
\----/
then adj becomes transitive: In every possible case, adj[i][j] == 1 and adj[j][k] == 1 implies adj[i][k] == 1. For this graph, path and adj are the same. That the graph is undirected corresponds to the "symmetry" property. If we added loops to each vertex so that v1, v2, and v3 were each adjacent to themselves, the resulting graph would be transitive, symmetric, and "reflexive", and could be said to represent equality (==) over the set {1,2,3}.
This begins to illustrate how graphs can represent different functions, and how properties of the function are reflected in properties of the graph. In general, if you let adj represent some function f, then path is the transitive closure of f.
For a formal definition of transitive closures, I refer you to Wikipedia. It isn't a hard concept once you understand all the math jargon.
这篇关于“路径矩阵”是什么意思？和“传递闭合”图（直接和无向）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
