Основываясь на комментариях к моему более раннему ответу:
Кажется, что все графики являются ненаправленными и плоскими, то есть могут быть встроены в 2D-плоскость без пересечения ребер, и одно такое вложениедано.Это вложение разделит плоскость.Например, фигура 8 разделяет плоскость на три части: две «внутренние» области и бесконечная внешняя область.Альтернативное представление состоит в том, что все ребра узла циклически упорядочены.(Это важная часть, которая позволяет нам применять теорию графов)
Разделение обязательно заключено в цикл, но не все циклы могут разделять одну область.В тривиальном случае на рисунке 8 все три области непосредственно связаны с отдельным циклом.
Входной граф в общем случае может быть упрощен.Некоторые узлы могут иметь только одно ребро;они не могут способствовать разделению и могут быть удалены вместе с краем.Другие узлы имеют два ребра, соединяющих разные узлы.Здесь узел и два ребра могут быть заменены прямым ребром, соединяющим соседей.Т.е. граф на рисунке 8 можно упростить до двух узлов и трех ребер между ними.(Это не обязательный шаг, но помогает вычислению).
Теперь каждая вершина будет иметь две области по обе стороны (так как они не направлены, «левый и правый» не являются очевидными различиями).Итак, для |V| вершин нам нужно рассмотреть 2 * |V| сторон.Они вообще не различны.Два смежных ребра (соединенных с одним и тем же узлом) могут граничить с одной и той же областью, если они также смежны в циклическом порядке ребер этого узла.Очевидно, что для узлов, имеющих только два ребра, два ребра совместно используют обе области (именно поэтому мы удалили их на предыдущем шаге).Для узлов с тремя ребрами любые два ребра имеют общую не менее одну область.
Итак, вот как перечислить эти области: Присвойте порядковый номер всем ребрам и вершинам.Назначьте направление каждому ребру, чтобы он проходил от края с меньшим номером к верхнему.Начните с вершины 1, правой стороны и пронумеруйте эту область 1. Обведите граничные ребра этой области, присвоив то же число 1 соответствующим сторонам ее граничных ребер.Вы делаете это, беря в каждом узле следующее смежное ребро в контрциклическом порядке.Когда вы вернетесь к исходной точке, вы знаете все граничные области ребер 1.
Затем вы проверяете левый край первой вершины.Если это не часть области 1, то это область 2, и вы применяете тот же алгоритм.Затем, проверьте вершину 2, правую сторону и левую сторону и т. Д. Каждый раз, когда вы найдете ребро и сторону, которая еще не пронумерована, присвойте номер следующей области и проследите края недавно основанной области.
Естьнебольшая проблема с определением, какой номер области соответствует бесконечности.Чтобы увидеть это, возьмем простой график (): два ребра, два узла и две области (внутри и снаружи).Из-за случайной нумерации ребер и вершин внешняя сторона может закончиться как 1 или 2. Это неизбежно;в теории графов нет различия между внутренним и внешним.