000
18.01.2004, 12:18 Uhr
talis
|
ich muss ein programm schreiben, welches berechnen soll, ob zwei eingegebene graphen isomorph sind oder nicht.
am papier habe ich kein problem das herauszufinden, jedoch mit der programmierlogik schon.
beschreibung zur prüfung (am papier), ob zwei graphen isomorph sind:
1) beide graphen müssen die gleiche anzahl von knoten haben
2) knotengrade müssen ebenso in beiden graphen gleich vertreten sein (also es muss gleich viele knoten grades 1, 2, 3, usw. geben)
3) nachbarschaftsbeziehungen prüfen - abbildungen von graph a(x) und a(y) feststellen (das sieht man auch relativ einfach bis knotenanzahl 10 am papier)
so zu 3) ich:
ich habe mir den algorithmus, laut der beschreibung des lehrers, aufgeschrieben - nur da diese mitschrift schon ein paar wochen alt ist, tue ich mir schwer die zu deuten bzw. zu verstehen:
algorithmus 1:
zwei isomporhe graphen unterscheiden sich nur über die numerierung der matrizen, deswegen muss man diese umnummerieren - gleichzeitiges vertauschen von spalten und zeilen. das würd' ich ja noch irgendwie verstehen.
so, aber dann fand ich, dass dies zu lange dauern würde und die berechnung ewig dauern würde.
algorithmus 2:
die knoten nach grade sortieren, entweder ab- oder ansteigend nach knotengraden nummerieren.
und jetzt steig' ich aus, weil ich die beschreibung nicht mehr durchblicke. vor allem, weil ich keine blassen schimmer mehr habe, wie man anhand der adjazenzmatrizen feststellen kann, ob zwei graphen isomporh sind...
kennt sich jemand aus? weiß jemand wie es funktioniert?
Dieser Post wurde am 18.01.2004 um 14:26 Uhr von Pablo editiert. |
