Ist mein Diagramm planar?

29

Ihre Aufgabe besteht darin, festzustellen, ob ein Diagramm planar ist.

Ein Diagramm ist planar, wenn es in die Ebene eingebettet werden kann, oder mit anderen Worten, wenn es ohne überkreuzende Kanten gezeichnet werden kann.

Eingabe: Sie erhalten ein ungerichtetes Diagramm in einem der folgenden Formate:

  • Kantenliste, z [(0, 1), (0, 2), (0, 3)]

  • Angrenzungskarte, z {0: [1, 2, 3], 1:[0], 2:[0], 3:[0]}

  • Angrenzende Matrix, z [[0, 1, 1, 1], [1, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 0]]

Knotennamen können Zahlen, Zeichenfolgen oder Ähnliches sein, das von Ihnen gewählte Format muss jedoch ein beliebiges Diagramm unterstützen. Kein Putting-Code in den Knotennamen. Es wird keine Selbstschleifen geben.

Standardmäßige Auswahl der Eingabe, einschließlich STDIN, Befehlszeilenargumenten und Funktionsargumenten.

Ausgabe: Sie sollten eine bestimmte Ausgabe für alle ebenen Diagramme und eine andere bestimmte Ausgabe für alle nicht ebenen Diagramme zurückgeben.

Standardmäßige Auswahl der Ausgabe, einschließlich STDOUT, Funktionsrückgabewert.

Beispiele:

Planar:

[]
[(0,1), (0,2), (0,3), (0,4), (0,5), (0,6)]
[(0,1), (0,2), (0,3), (1,2), (1,3), (2,3)]
[(0,2), (0,3), (0,4), (0,5), (1,2), (1,3), (1,4), (1,5), (2,3),
 (2,5), (3,4), (4,5)]

Nichtplanar:

[(0,1), (0,2), (0,3), (0,4), (1,2), (1,3), (1,4), (2,3), (2,4), (3,4)]
[(0,3), (0,4), (0,5), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5)]
[(0,3), (0,4), (0,6), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (5,6), 
 (7,8), (8,9), (7,9)]

Jede Funktion, die explizit Planaritätstests durchführt oder auf andere Weise speziell auf planare Einbettungen Bezug nimmt, ist nicht zulässig.

Das ist Code Golf. Möge der kürzeste Code gewinnen.

isaacg
quelle
Gute Frage !
Es ist großartig, dass dies ein klassisches Problem ist, und es gibt immer noch mehrere mögliche Ansätze, einschließlich solcher, die für gewöhnliche Zwecke nicht im Code verwendet werden.
Lirtosiast
Ein Testfall für einen nicht verbundenen Graphen mit einer planaren und einer nicht planaren verbundenen Komponente wäre gut.
Peter Taylor
@PeterTaylor Sicher, ich werde einen hinzufügen.
Isaacg
5
@RenaeLider Sorry, aber ich verstehe nicht. Die Frage hat überhaupt nichts mit Gleitkommazahlen zu tun - sie verwendet nicht einmal Zahlen, sondern nur Bezeichnungen.
Isaacg

Antworten:

14

Mathematica, 201 Bytes

f@g_:=EdgeCount@g<9||!(h=g~IsomorphicGraphQ~CompleteGraph@#&)@5&&!h@{3,3}&&And@@(f@EdgeDelete[g,#]&&f@EdgeContract[g,#]&/@EdgeList@g);And@@(f@Subgraph[g,#]&/@ConnectedComponents[g=Graph[#<->#2&@@@#]])&

Dies ergibt eine unbenannte Funktion, die eine Kantenliste wie folgt annimmt

{{0, 3}, {0, 4}, {0, 5}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}}

Dies ist ein schrecklich ineffizienter rekursiver Ansatz, der auf Wagners Theorem basiert :

Ein endlicher Graph ist genau dann eben, wenn er nicht K 5 oder K 3,3 als Moll hat.

Hier ist K 5 der vollständige Graph mit 5 Eckpunkten, und K 3,3 ist der vollständige zweigeteilte Graph mit 3 Eckpunkten in jeder Gruppe. Ein Graph A ist ein Nebengraph von Graph B, wenn er durch eine Folge von Randlöschungen und Randkontraktionen aus B erhalten werden kann .

Dieser Code prüft also nur, ob der Graph zu K 5 oder K 3,3 isomorph ist, und wenn nicht, ruft er sich bei jeder möglichen Kantenlöschung oder -kontraktion einmal rekursiv auf.

Der Haken ist, dass das Löschen oder Zusammenziehen von Kanten in einer Komponente eines nicht verbundenen Graphen niemals alle Scheitelpunkte dort entfernt, sodass wir niemals die gewünschten Isomorphismen finden. Daher wenden wir diese Suche auf jede verbundene Komponente des Eingabediagramms separat an.

Dies funktioniert für die angegebenen Eingaben sehr schnell, aber wenn Sie ein paar weitere Kanten hinzufügen, dauert dies schnell katastrophal lange (und beansprucht auch viel Speicherplatz).

Hier ist eine eingerückte Version von f(der unbenannten Funktion, nachdem sie nur ein Diagrammobjekt aus der Eingabe generiert hat:

f@g_ := 
  EdgeCount@g < 9 || 
  ! (h = g~IsomorphicGraphQ~CompleteGraph@# &)@5 && 
  ! h@{3, 3} &&
  And @@ (f@EdgeDelete[g, #] && f@EdgeContract[g, #] & /@ EdgeList@g)

Und dies ist die unbenannte Funktion, die die Eingabe in einen Graphen umwandelt und ffür jede verbundene Komponente aufruft :

And @@ (
  f @ Subgraph[g, #] & /@ ConnectedComponents[
    g=Graph[# <-> #2 & @@@ #]
  ]
)&

Ich kann ein paar Bytes sparen, indem ich die Beendigungsbedingung von EdgeCount@g<9auf g==Graph@{}ändere, aber das wird die Laufzeit erheblich verkürzen. Der zweite Testfall dauert dann 30 Sekunden und der letzte ist noch nicht abgeschlossen.

Martin Ender
quelle
Sie können versuchen, die benannte Funktion zu entfernen, indem Sie #0die innerste reine Funktion verwenden.
LegionMammal978
@ LegionMammal978 Ich weiß, aber es speichert eigentlich nichts, denn dann brauche ich Klammern und muss #einer Variablen auch gmanuell zuweisen .
Martin Ender