Votre tâche consiste à déterminer si un graphique est plan.

Un graphique est plan s'il peut être intégré dans le plan, ou en d'autres termes s'il peut être dessiné sans arêtes croisées.

Entrée: Vous recevrez un graphique non orienté dans votre choix des formats suivants:

• Liste des bords, par exemple [(0, 1), (0, 2), (0, 3)]

• Carte d'adjacence, par exemple {0: [1, 2, 3], 1:[0], 2:[0], 3:[0]}

• Matrice adjacente, par exemple [[0, 1, 1, 1], [1, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 0]]

Les noms de nœuds peuvent être des nombres, des chaînes ou similaires, mais le format que vous avez choisi doit pouvoir prendre en charge un graphique arbitraire. Pas de mise de code dans les noms de noeud. Il n'y aura pas de boucles auto.

Choix standard d'entrée, y compris STDIN, les arguments de ligne de commande et les arguments de fonction.

Sortie: vous devez renvoyer une sortie spécifique pour tous les graphiques planaires et une sortie spécifique différente pour tous les graphiques non plans.

Choix standard de sortie, y compris STDOUT, valeur de retour de fonction.

Exemples:

Planaire:

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

Non planaire:

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

Toute fonction qui effectue explicitement des tests de planéité ou fait autrement référence spécifiquement aux incorporations planaires est interdite.

C'est le golf de code. Que le code le plus court l'emporte.

Mathematica, 201 octets

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

Cela se traduit par une fonction sans nom, qui prend une liste de bord comme

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

Il s'agit d'une approche récursive horriblement inefficace basée sur le théorème de Wagner :

Un graphe fini est plan si et seulement s'il n'a pas K ₅ ou K _3,3 comme mineur.

Ici, K ₅ est le graphe complet avec 5 sommets, et K _3,3 est le graphe bipartite complet avec 3 sommets dans chaque groupe. Un graphique A est un mineur du graphique B s'il peut être obtenu à partir de B par une séquence de suppressions de bord et de contractions de bord.

Donc, ce code vérifie simplement si le graphique est isomorphe à K ₅ ou K _3,3 et sinon, il s'appelle récursivement une fois pour chaque suppression ou contraction de bord possible.

Le hic est que la suppression ou la contraction d'arêtes dans un composant d'un graphe non connecté ne se débarrassera jamais de tous les sommets, donc nous ne trouverons jamais les isomorphismes souhaités. Par conséquent, nous appliquons cette recherche à chaque composant connecté du graphique d'entrée séparément.

Cela fonctionne très rapidement pour les entrées données, mais si vous ajoutez quelques bords supplémentaires, cela prendra rapidement une durée catastrophique (et prendra également beaucoup de mémoire).

Voici une version en retrait de f(la fonction sans nom après avoir simplement généré un objet graphique à partir de l'entrée:

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

Et c'est la fonction sans nom qui convertit l'entrée en graphique et appelle fchaque composant connecté:

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

Je peux économiser quelques octets en changeant la condition de terminaison de EdgeCount@g<9à g==Graph@{}, mais cela fera exploser considérablement l'exécution. Le deuxième test élémentaire prend alors 30 secondes et le dernier n'est pas encore terminé.