Was bedeutet es "Pfad " Matrix" und "Transitive Closure" eines Graphen (Gerichtete und Ungerichtete)?

Ich denke, unkulunkulu, die Antwort ist ziemlich komplett, aber angesichts der JMSA scheint unzufrieden, werde ich einen weiteren Versuch.

Beginnen wir nicht mit dem Pfad-matrix, aber mit der Nachbarschaft-matrix. Die Nähe matrix ist die standard-Darstellung eines Graphen. Wenn adj ist die Nähe matrix für einige Graphen G, dann adj[i][j] == 1 wenn vertex ich ist neben vertex j (d.h. es gibt eine Kante von ich zu j), und 0 sonst. In anderen Worten, adj[i][j] == 1, wenn, und nur wenn wir von vertex ich Eckpunkt j in eine "Schritt".

Nun definieren wir eine weitere matrix, die ich nenne, adj2: adj2[i][j] == 1, wenn, und nur wenn wir von vertex ich Eckpunkt j in zwei Schritte oder weniger. Sie nennen könnte es eine "zwei-Schritt Nachbarschaft" der matrix. Das wichtigste ist, dass adj2 definiert werden können, in Bezug auf 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

Ist, adj2[i][j] ist 1 wenn ich ist neben j (d.h. adj[i][j] == 1) oder wenn es gibt einige andere vertex k, so dass Sie Schritt aus ich zu k und dann von k zu j (d.h. adj[i][j] == 1 und die adj[k][j] == 1).

Als Sie sich vorstellen können, können Sie mit der gleichen Logik zu definieren eine "drei-Schritt" Nachbarschaft matrix adj3, adj4, adj5, und so weiter. Wenn Sie lange genug (z.B. zu adjn, wo n ist die Anzahl der Eckpunkte in der Grafik), erhalten Sie eine matrix, die Ihnen sagt, ob es einen Pfad von beliebiger Länge von vertex ich Eckpunkt j. Diese, natürlich, wäre auch die Grafik der Pfad matrix: adjn[i][j] == Pfad[i][j] für alle i, j. (Hinweis: nicht zu verwechseln Pfad-matrix mit Distanz-matrix.)

Mathematiker würde sagen, dass Pfad[ich][j] ist der transitive Abschluss von adj[i][j] auf die Grafik G.

Transitive closures existieren unabhängig vom graph-Theorie; adj ist nicht die einzige Sache, die mit einem transitiven hĂ ulle. Grob gesagt, alle Funktionen (in der Programmierung Sinn), die zwei Argumente und geben einen booleschen Wert zurück haben eine transitive closure.

Des Gleichheitsoperators (==) und Ungleichheit (<, >, <=, >=) - Operatoren vertraut sind Beispiele solcher Funktionen. Diese unterscheiden sich von adj jedoch, dass Sie sich transitive. "f(i,j) ist transitiv" bedeutet, dass, wenn f(i,j) == true, und f(j,k) == true, dann f(i, k) == true. Sie wissen, dass diese Eigenschaft wahr ist, sagen wir, "weniger als" - relation: von a < b und b < c, kann man folgern, dass a < c. Die transitiven hĂ ulle einer transitiven Funktion f ist nur f.

adj ist nicht in der Regel transitiv. Betrachten Sie die Graphen:

v1---v2---v3

In diesem Diagramm adj darstellen könnten, die Funktion busBetween(city1, city2). Hier gibt es einen bus, den Sie nehmen können von v1 zu v2 (adj[1][2] == 1) und ein bus von v2 zu v3 (adj[2][3] == 1), aber es gibt keinen bus von v1 direkt zu v3 (adj[1][2] == 0). Es gibt einen bus-Pfad von v1 nach v3, aber v1 und v3 sind nicht bus-benachbart sind. Für dieses Diagramm, adj ist nicht transitiv, so Pfad, das ist der transitive Abschluss von adj, unterscheidet sich von adj.

Wenn wir fügen eine Kante zwischen v1 und v3,

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

dann adj wird transitiv: In jedem möglichen Fall, adj[i][j] == 1 und adj[j][k] == 1 impliziert adj[i][k] == 1. Für dieses Diagramm, Pfad und adj sind die gleichen. Der graph wird ungerichteter entspricht der " Symmetrie " - Eigenschaft. Wenn wir hinzufügen, Schleifen an jedem Knoten, so dass v1, v2 und v3 wurden jeweils neben sich, der resultierende graph wäre transitiv, symmetrisch und "reflexive", und es könnte sein, zu repräsentieren Gleichheit (==) über der Menge {1,2,3}.

Diese beginnt um zu zeigen, wie Graphen darstellen kann verschiedene Funktionen, und wie Sie Eigenschaften der Funktion spiegeln sich in den Eigenschaften des Graphen. Im Allgemeinen, wenn Sie lassen Sie adj repräsentieren einige Funktion f, dann Pfad ist der transitive Abschluss von f.

Für eine formale definition der transitiven Verschlüsse, Verweise ich Sie auf Wikipedia. Es ist nicht eine harte Konzept, wenn Sie verstehen, all die Mathematik-jargon.