13.4 Teildreiecke suchen

In diesem Abschnitt untersuchen wir die Frage, wie wir in einem Graphen \(G\) »Dreiecke«, das heißt Teilgraphen der Form \(K_3\), finden können. Dazu arbeiten wir wieder mit der Adjazenzmatrix des Graphen.

Sei also \(A\) die Adjazenzmatrix (für eine fixierte Eckennummerierung) und sei \(B=(b_{ij})_{i,j} = A^2\).

Dann können wir die Frage nach einem Dreieck in \(G\) auch so umformulieren: Wir suchen Paare \((i, j)\) von Ecken in \(G\) mit \(a_{ij}\ne 0\), \(b_{ij}\ne 0\) (denn das bedeutet erstens, dass \(i\) und \(j\) benachbart sind, und zweitens, dass zwischen \(i\) und \(j\) ein Weg der Länge \(2\) existiert; bezeichnet \(k\) den Zwischenschritt auf diesem Weg, dann sind \(i\), \(j\) und \(k\) paarweise miteinander verbunden und bilden daher ein Dreieck).

Abgesehen davon, dass das ursprüngliche Problem damit (vielleicht) eleganter ausgedrückt ist, kann man auch (für sehr große Graphen) einen Vorteil daraus ziehen, was die konkrete Berechnung angeht. Wenn man naiv in dem Graphen \(G\) nach einem Dreieck sucht, müsste man alle drei-elementigen Teilmengen der Eckenmenge \(\mathbb E\) untersuchen; das wären größenordnungsmäßig \((\# \mathbb E)^3\) Rechenoperationen. Für die Berechnung des Quadrats \(A^2\) der Adjazenzmatix braucht man mit dem naiven Verfahren zur Berechnung des Matrizenprodukts zwar auch größenordnungsmäßig \((\# \mathbb E)^3\) Rechenoperationen. Es gibt aber bessere Algorithmen (vgl. Ergänzung 5.33).

Quelle: [ Ma ] Kap. 10.