Планарный граф
В теории графов планарный граф — это граф , который можно вложить в плоскость , т. е. его можно нарисовать на плоскости таким образом, что его ребра пересекаются только в своих концах. Другими словами, его можно нарисовать так, чтобы ни одно ребро не пересекалось. [1] [2] Такой рисунок называется плоским графом или планарным вложением графа . Плоский граф можно определить как планарный граф с отображением каждого узла в точку на плоскости и каждого ребра в плоскую кривую .на этой плоскости, так что крайние точки каждой кривой являются точками, отображаемыми из ее конечных узлов, и все кривые не пересекаются, кроме своих крайних точек.
Любой график, который можно нарисовать на плоскости, можно нарисовать и на сфере , и наоборот, с помощью стереографической проекции .
Класс эквивалентности топологически эквивалентных рисунков на сфере, обычно с дополнительными предположениями, такими как отсутствие перешейков , называется планарной картой . Хотя плоский граф имеет внешнюю или неограниченную грань , ни одна из граней плоской карты не имеет определенного статуса.
Планарные графы обобщаются до графов, которые можно рисовать на поверхности данного рода . В этой терминологии плоские графы имеют род 0, поскольку плоскость (и сфера) являются поверхностями рода 0. Другие связанные темы см. в разделе « вложение графов ».
Польский математик Казимеж Куратовский дал характеристику плоских графов в терминах запрещенных графов , теперь известную как теорема Куратовского :
Подразделение графа получается в результате вставки вершин в ребра (например, изменение ребра •——• на •—•—•) ноль или более раз.
