Ваша задача - определить, является ли график плоским.

График является плоским, если он может быть встроен в плоскость, или, другими словами, если его можно нарисовать без каких-либо пересекающихся ребер.

Входные данные: Вам будет предоставлен неориентированный граф на ваш выбор следующих форматов:

• Пограничный список, например [(0, 1), (0, 2), (0, 3)]

• Карта смежности, например {0: [1, 2, 3], 1:[0], 2:[0], 3:[0]}

• Смежная матрица, например [[0, 1, 1, 1], [1, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 0]]

Имена узлов могут быть числами, строками или аналогичными, но выбранный вами формат должен поддерживать произвольный граф. Не помещайте код в имена узлов. Там не будет никаких петель.

Стандартный выбор ввода, включая STDIN, аргументы командной строки и аргументы функций.

Вывод: вы должны вернуть определенный вывод для всех плоских графиков и другой конкретный вывод для всех непланарных графиков.

Стандартный выбор выхода, включая STDOUT, возвращаемое значение функции.

Примеры:

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

непланарный:

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

Любая функция, которая явно выполняет тестирование на плоскостность или иным образом специально ссылается на плоские вложения, запрещена.

Это код гольф. Пусть победит самый короткий код.

Mathematica, 201 байт

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

Это оценивает безымянную функцию, которая принимает список границ как

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

Это ужасно неэффективный рекурсивный подход, основанный на теореме Вагнера :

Конечный граф является плоским в том и только в том случае, если он не имеет K ₅ или K _3,3 в качестве минора.

Здесь K ₅ - полный граф с 5 вершинами, а K _3,3 - полный двудольный граф с 3 вершинами в каждой группе. Граф A является второстепенным по отношению к графу B, если он может быть получен из B последовательностью удалений ребер и сокращений ребер.

Таким образом, этот код просто проверяет, изоморфен ли граф K ₅ или K _3,3, и если нет, то он рекурсивно вызывает себя один раз для каждого возможного удаления или сжатия ребра.

Подвох заключается в том, что удаление или сжатие ребер в одном компоненте несвязанного графа никогда не избавит от всех вершин, поэтому мы никогда не найдем нужные изоморфизмы. Следовательно, мы применяем этот поиск к каждому связанному компоненту входного графа отдельно.

Это работает очень быстро для заданных входов, но если вы добавите еще несколько ребер, это быстро займет катастрофически много времени (и также займет много памяти).

Вот версия с отступом f(безымянная функция после того, как она просто генерирует графовый объект из входных данных:

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

И это безымянная функция, которая преобразует входные данные в график и вызывает fдля каждого подключенного компонента:

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

Я могу сэкономить пару байтов, изменив условие завершения с EdgeCount@g<9на g==Graph@{}, но это значительно увеличит время выполнения. Второй тест занимает 30 секунд, а последний еще не завершен.