Relationen und Matrizen

Sei R eine Relation auf der endlichen Menge M = { 1, …, n }. Visualisieren wir die Beziehungen a R b für alle a, b  ∈  M durch einen Pfeil von a nach b, so ist folgende Frage natürlich:

Gibt es für einen Startpunkt s  ∈  M und ein Ziel z  ∈  M einen R-Zug von s nach z?

Dabei ist ein R-Zug der Länge k ≥ 1 von s nach z eine Folge a₀, …, a_k in M mit a₀ = a, a_k = z und a_i R a_i + 1 für alle i < k.

Zur Untersuchung der Frage definieren wir für zwei Relationen S₁ und S₂ auf M ihre Verknüpfung S₁ ∘ S₂ durch:

S₁ ∘ S₂

= { (a, c) | es gibt ein b  ∈  M mit a S₁ b und b S₂ c }.

Nun definieren wir rekursiv für alle k ≥ 1:

R¹ = R, R^k + 1 = R^k ∘ R für alle k.

Eine Induktion nach k ≥ 1 zeigt, dass für alle a, b  ∈  M und alle k ≥ 1 gilt:

a R^k b gdw „es gibt einen R-Zug der Länge k von a nach b“.

Gibt es einen R-Zug von a nach b, so gibt es auch einen R-Zug von a nach b, dessen Länge kleinergleich der Anzahl n der Elemente von M ist (Herausschneiden von Schleifen). Damit lautet unsere Frage:

Gibt es ein k ≤ n mit s R^k z?

Ist R reflexiv, so gilt, wie man leicht einsieht, R = R¹ ⊆ … ⊆ Rⁿ, und dann vereinfacht sich unsere Frage zu:

Gilt s Rⁿ z?

Die transitive Hülle R* von R ist definiert als die kleinste transitive Relation, die R als Teilmenge enthält. Nach unseren Überlegungen gilt also R* = Rⁿ, falls R reflexiv ist, und R* = ⋃_{1 ≤ k ≤ n} R^k in jedem Fall (siehe Übungen).

Für eine effektive Berechnung der transitiven Hülle von R sind 0-1-Matrizen nützlich.

Definition (darstellende Matrix von R)

Die darstellende Matrix A_R = (a_i j)_i j von R ist definiert durch

$a_{ij} = { \begin{matrix} 1 & falls i R j, \\ 0 & sonst. \end{matrix}$

So stellt zum Beispiel die Matrix auf der linken Seite die auf der rechten Seite visualisierte Relation R auf { 1, …, 5 } dar:

Wir führen nun eine neue „logische“ Multiplikation für 0-1-Matrizen ein, die die Verknüpfung S₁ ∘ S₂ von Relationen beschreibt. Hierzu definieren wir eine Addition auf { 0, 1 } durch:

0 + 0 = 0, 0 + 1 = 1 + 0 = 1 + 1 = 1. (logische 0-1-Addition)

Diese Addition entspricht der Wahrheitswertfunktion des Junktors „oder“. Die übliche Multiplikation auf { 0, 1 } entspricht bereits der Wahrheitswertfunktion des Junktors „und“. Im folgenden bedeutet + immer die logische Addition. So ist z. B. (0, 1, 1, 0) + (1, 1, 0, 0) = (1, 1, 1, 0), usw.

Mit diesen Operationen definieren wir nun:

Definition (logische Matrizenmultiplikation)

Seien A, B (n × n)-Matrizen mit 0-1-Einträgen. Dann ist das logische Produkt A ∗ B von A und B die (n × n)-Matrix C = (c_{i j})_{i j} mit

c_{i j} = ∑_{1 ≤ k ≤ n} a_{i k} b_{k j} = a_{i 1} · b_{1 j} + … + a_{i n} · b_{n j} für alle 1 ≤ i, j ≤ n.

Diese Matrizenmultiplikation folgt also wieder der Regel „Zeile mal Spalte“, lediglich die Arithmetik der Addition ist modifiziert.

Es gilt wieder A · (B · C) = (A · B) · C für alle 0-1-Matrizen A, B, C, wie man leicht nachrechnet. Die Assoziativität folgt aber auch aus dem folgenden Satz, der den Zusammenhang mit der Verknüpfung von Relationen herstellt.

Satz (Verknüpfung von Relationen und logische Matrizenmultiplikation)

Seien S₁, S₂ Relationen auf M = { 1, …, n }. Dann gilt

A_{S₁ ∘ S₂} = A_S₁ ∗ A_S₂.

Beweis

Seien A_S₁ = (a_{i j})_i j, A_S₂ = (b_{i j})_i j, A_S₁ ∗ A_S₂ = (c_{i j})_i j.

Dann gilt für alle i, j:

c_{i j} = 1	gdw
∑_{1 ≤ k ≤ n} a_{i k} b_{k j} = 1	gdw
es gibt ein 1 ≤ k ≤ n mit a_{i k} b_{k j} = 1	gdw
es gibt ein 1 ≤ k ≤ n mit a_{i k} = 1 und b_{k j} = 1	gdw
es gibt ein 1 ≤ k ≤ n mit (i, k)  ∈  S₁ und (k, j)  ∈  S₂	gdw

(i, j)  ∈  S₁ ∘ S₂.

Korollar

Es gilt A_R^k = (A_R)^k für alle k ≥ 1.

Wir können also die transitive Hülle R* von R berechnen, indem wir für A = A_R der Reihe nach die Produkte

A ∗ A = A², A² ∗ A = A³, …, Aⁿ

berechnen. Ist R reflexiv, so ist Aⁿ die darstellende Matrix A_R* von R*. Allgemein ist A_R* die punktweise logische Addition der Matrizen A¹, …, Aⁿ. Diese Berechnung von R* benötigt aber unnötig viele Rechenschritte, und wir wollen deswegen noch einen effizienteren Algorithmus vorstellen.

Der Warshall-Algorithmus

Sei wieder R eine Relation auf M = { 1, …, n }. Wir definieren für alle k ≤ n eine Relation R^(k) auf M durch:

i R^(k) j falls „es gibt einen R-Zug i = a₀, …, a_m = j mit 1 ≤ a₁, …, a_m − 1 ≤ k“

für alle i, j  ∈  M. Offenbar gilt:

R = R⁽⁰⁾ ⊆ R⁽¹⁾ ⊆ … ⊆ R⁽ⁿ⁾ = „die transitive Hülle von R“.

Bei diesen Relationen steht der obere Index also nicht für die Länge eines R-Zuges, sondern für die Menge { 1, …, k } der Elemente von M, die für einen R-Zug verwendet werden dürfen.

Der sog. Algorithmus von Warshall berechnet nun in effektiver Weise die darstellenden Matrizen der Relationen R^(k). Wir formulieren das Verfahren vorab und beweisen dann, was es leistet.

Algorithmus von Warshall

Sei A eine (n × n)-Matrix mit 0-1-Einträgen. Wir definieren rekursiv (n × n)-Matrizen A^(k) mit 0-1-Einträgen für alle k ≤ n. Das Ergebnis der Berechnung ist die Matrix A⁽ⁿ⁾.

Zunächst setzen wir A⁽⁰⁾ = A. Sei nun A^(k) definiert für ein k < n. Für alle 1 ≤ i ≤ n mit A^(k)(i, k + 1) = 1 sei die i-te Zeile von A^(k + 1) die punktweise logische Summe der i-ten und (k + 1)-ten Zeile von A^(k). Die anderen Zeilen von A^(k + 1) übernehmen wir unverändert aus der Matrix A^(k).

Ist die Matrix A^(k) berechnet, so ist die (k + 1)-te Spalte die „aktive“ Spalte und die (k + 1)-te Zeile die „aktive“ Zeile. Die Einsen der aktiven Spalte markieren genau diejenigen Zeilen, auf die wir die aktive Zeile logisch addieren. Die aktive Spalte und Zeile bleiben dabei, wie man leicht sieht, unverändert.

Wir zeigen nun:

Satz (Korrektheit des Warshall-Algorithmus)

Sei A = A_R die darstellende Matrix von R, und seien A⁽⁰⁾, …, A⁽ⁿ⁾ die durch den Warshall-Algorithmus berechneten Matrizen. Dann gilt für alle k ≤ n:

A^(k) ist die darstellende Matrix A_R^(k) der Relation R^(k).

Beweis

Wir zeigen die Behauptung durch Induktion nach k ≤ n.

Induktionsanfang k = 0:

Es gilt A⁽⁰⁾ = A = A_R = A_R⁽⁰⁾.

Induktionsschritt von k nach k + 1 für k < n:

Für alle 1 ≤ i, j ≤ n gilt:

A^(k + 1)(i, j) = 1			gdw
A^(k)(i, j) = 1	oder	A^(k)(i, k + 1) = 1 und A^(k)(k + 1, j) = 1	gdw_I. V.
(i, j)  ∈  R^(k)	oder	(i, k + 1)  ∈  R^(k) und (k + 1, j)  ∈  R^(k)	gdw
(i, j)  ∈  R^(k)	oder	es gibt 1 ≤ a₁, …, a_m, b₁, …, b_m′ ≤ k mit i, a₁, …, a_m, k + 1, b₁, …, b_m′, j ist ein R-Zug	gdw

(i, j)  ∈  R^(k + 1),

wobei wir für die letzte Rückrichtung die Existenz von R-Zügen verwenden, die kein Element von M mehrfach durchlaufen.

Damit ist also das Ergebnis A⁽ⁿ⁾ des Warshall-Algorithmus die darstellende Matrix der transitiven Hülle von R.

Wir beobachten noch, dass wir uns die Matrizen A⁽ⁱ⁾ während der Berechnung nicht merken müssen. Es genügt somit ein „Speicherplatz“ für eine 0-1-Matrix.