Ich habe einen (ungerichteten) Graphen als Adjazenzmatrix gegeben und will ihn nun auf Planarität prüfen. Dabei reicht mir die notwendige Bedingung nicht aus, ich hätte gerne eine hinreichende. Gibt es nicht eine Methode, wie man alleine anhand der Adjazenzmatrix feststellen kann, ob der Graph planar ist oder eben nicht?
> Gibt es nicht eine Methode, wie man alleine anhand der Adjazenzmatrix feststellen kann, ob der Graph planar ist oder eben nicht?
Gibt es, den Satz von Kuratowski: ein Graph ist genau dann planar ist, wenn er keinen Teilgraphen besitzt, der ein Unterteilungsgraph des K5 oder des K3,3 ist.
Ja, davon habe ich gehört.Gucke ich also dann ob in meiner gegebenen Matrix entweder K5 oder K3,3 vorkommt ?
Was meinst du mit "vorkommt"? Du darfst Knoten und Kanten entfernen und Knoten zusammenziehen. Wenn du so K5 oder des K3,3 bekomment kannst, dann ist der Graph nicht planar. Andernfalls ist er planar.
genau das meinte ichdanke
Ein anderes Problem?
Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos