577
правок
Изменения
→Алгоритм
<tex>2.</tex> Второй этап - общий шаг.
Построим множество '''сегментов'''. Каждый сегмент <tex>S</tex> относительно уже построенного <tex>G_{plane}</tex> представляет собой одно из двух:
# ребро, оба конца которого принадлежат <tex>G_{plane}</tex>, но само оно не принадлежит <tex>G_{plane}</tex>,
# связную компоненту графа <tex>G \backslash G_{plane}</tex>, дополненную всеми ребрами графа <tex>G</tex> такими, у которых один из концов принадлежит связной компоненте, а второй принадлежит графу <tex>G_{plane}</tex>.
Вершины, одновременно принадлежащие <tex>G_{plane}</tex> и какому-либо сегменту, назовем '''контактными'''. На рис. 3 изображены сегменты для нашего примера. Контактные вершины обведены в квадрат.
{| cellpadding="2"
| || [[Файл:Гамма-алгоритм3.jpg|thumb|left|370px|Рис. 3. Выделение сегментов.]]
|}
Пусть в каком-то сегменте нет ни одной контактной вершины. В таком случае граф до выделения <tex>G_{plane}</tex> был несвязным, что противоречит условию. Пусть контактная вершина в сегменте только одна. Это значит, что в графе был мост, чего быть не может так же по условию. Таким образом, в каждом сегменте имеется не менее двух контактных вершин. Соответственно, в каждом сегменте есть цепь между любой парой контактных вершин.
