Twoim zadaniem jest ustalenie, czy wykres jest płaski.

Wykres jest płaski, jeśli można go osadzić w płaszczyźnie, lub innymi słowy, jeśli można go narysować bez przekraczania krawędzi.

Dane wejściowe: Otrzymasz niebezpośredni wykres w wybranych przez ciebie formatach:

• Lista krawędzi, np [(0, 1), (0, 2), (0, 3)]

• Mapa adiacyencji, np {0: [1, 2, 3], 1:[0], 2:[0], 3:[0]}

• Matryca sąsiednia, np [[0, 1, 1, 1], [1, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 0]]

Nazwy węzłów mogą być liczbami, łańcuchami lub podobnymi, ale wybrany format musi obsługiwać dowolny wykres. Brak umieszczania kodu w nazwach węzłów. Nie będzie żadnych pętli własnych.

Standardowy wybór danych wejściowych, w tym STDIN, argumenty wiersza poleceń i argumenty funkcji.

Dane wyjściowe: powinieneś zwrócić określone dane wyjściowe dla wszystkich wykresów płaskich i inne dane wyjściowe dla wszystkich wykresów niepłaskich.

Standardowy wybór wyjścia, w tym STDOUT, wartość zwracana funkcji.

Przykłady:

Planarny:

[]
[(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)]

Nonplanar:

[(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)]

Wszelkie funkcje, które jawnie wykonują testy płaskości lub w inny sposób odnoszą się do osadzania płaskiego, są niedozwolone.

To jest kod golfowy. Niech wygra najkrótszy kod.

Mathematica, 201 bajtów

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&@@@#]])&

To ocenia na funkcję nienazwaną, która przyjmuje listę krawędzi jak

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

Jest to okropnie nieefektywne podejście rekurencyjne oparte na twierdzeniu Wagnera :

Skończony wykres jest płaski, jeśli tylko nie ma K ₅ lub K _3,3 jako pomniejszej.

Tutaj K ₅ jest kompletnym wykresem z 5 wierzchołkami, a K _3,3 jest kompletnym wykresem dwustronnym z 3 wierzchołkami w każdej grupie. Wykres A jest nieznaczny dla wykresu B, jeśli można go uzyskać z B przez sekwencję usuwania krawędzi i skurczów krawędzi.

Zatem ten kod sprawdza tylko, czy wykres jest izomorficzny do K ₅ lub K _3,3, a jeśli nie, to rekurencyjnie wywołuje się raz dla każdego możliwego usunięcia lub skurczenia krawędzi.

Chodzi o to, że usuwanie lub kurczenie się krawędzi w jednym elemencie niepowiązanego wykresu nigdy nie pozbędzie się tam wszystkich wierzchołków, więc nigdy nie znajdziemy pożądanych izomorfizmów. Dlatego stosujemy to wyszukiwanie do każdego podłączonego komponentu wykresu wejściowego osobno.

Działa to bardzo szybko dla danych wejść, ale jeśli dodasz kilka dodatkowych krawędzi, szybko zajmie to katastrofalnie długo (i zajmie również dużo pamięci).

Oto wcięta wersja f(funkcja bez nazwy po wygenerowaniu obiektu wykresu na podstawie danych wejściowych:

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

A to jest nienazwana funkcja, która konwertuje dane wejściowe na wykres i wywołuje fkażdy podłączony komponent:

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

Mogę zaoszczędzić kilka bajtów, zmieniając warunek zakończenia z EdgeCount@g<9na g==Graph@{}, ale spowoduje to znaczne zużycie środowiska wykonawczego. Drugi przypadek testowy zajmuje wówczas 30 sekund, a ostatni jeszcze się nie zakończył.