Hallo,
ich habe ein Problem einen Algorithmus zu finden der einen K4 für einen beliebigen Graphen ermittelt. Bei einem K3 hat man die Möglichkeit die Adjazenzmatrix mit sich selbst zu multiplizieren(wenn vorher die Diagonalen auf 0 gesetzt wurden). Dann vergleicht man die Produktmatrix mit der Ausgangsmatrix wo beide Einträge a(ij) != 0 sind. Als Beispiel habe für einen K3 habe ich hier die Multiplikation
mal aufgezeigt. Dieses Beispiel enthält jedoch keinen K4 und soll nur noch einmal der Visualisierung meiner Ausgangssituation dienen.
Adjazenzmatrix mit Dreiecken
- Matrix :
0 1 1 0 0 1 1 1
1 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1
0 0 0 0 1 1 0 0
0 0 0 1 0 1 1 1
1 0 0 1 1 0 0 0
1 0 0 0 1 0 0 0
1 1 1 0 1 0 0 0
- Matrix :
0 1 1 0 0 1 1 1
1 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1
0 0 0 0 1 1 0 0
0 0 0 1 0 1 1 1
1 0 0 1 1 0 0 0
1 0 0 0 1 0 0 0
1 1 1 0 1 0 0 0
Produktmatrix:
5 1 1 1 3 0 0 2
1 2 2 0 1 1 1 1
1 2 2 0 1 1 1 1
1 0 0 2 1 1 1 1
3 1 1 1 4 1 0 0
0 1 1 1 1 3 2 2
0 1 1 1 0 2 2 2
2 1 1 1 0 2 2 4
So war meine Überlegung, für einen K4, die entstandene Produktmatrix mit der bestehenden Adjazenzmatrix zu multiplizieren und aus dieser Matrix(A^3) die gleiche Bedingung ableiten zu können. Nur leider erkenne ich dabei keinen K4. Ist der Ansatz falsch? Ich wäre froh über jeglichen Hinweis und bedanke mich schon einmal im Voraus für Vorschläge.
Grüße Thomas