Презентации лекций / Презентация лекции 11 ДМ нов 20
.pdf
Пусть –граньплоскойукладкиподграфа
ДопустимаяграньдлясегментаR |
|
Грань,содержащаявсе |
относительно |
|
контактныевершинысегментаR |
|
|
Обозначение: |
|
|
|
|
|
Г( ) –множестводопустимых |
|
|
|
|||
|
|
|
|
|||
|
гранейсегментаR |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Г |
= , |
Г |
= , |
|
|
|
|
|||
|
|
|
|
|
|
|
1
2
3
4
21
1
Простаяцепьсегмента 
2
3
4
5
Соединяетдвеконтактныевершины |
Несодержит других контактныхвершин |
цепь
|
|
|
|
|
|
Примеры –цепей сегмента |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Всякая–цепь,принадлежащаясегменту,можетбытьуложенав любуюгрань,допустимуюдляэтогосегмента
22
Алгоритм 
укладки графа на плоскости
0. Выберем некоторый простой цикл графа и уложим его на плоскости; положим = .
1.Найдем грани графа и сегменты относительно . Если множество сегментов пусто, то перейдем к п.7
2.Для каждого сегмента определим множество допустимыхграней Г( ).
3. Если существует сегмент , длякоторого множество Г = , то граф непланарен. Конец. Иначе перейдем к п. 4
4.Если имеетсясегмент , длякоторого имеетсяединственная допустимаягрань , то перейдем к пункту 6. Иначе – к п. 5
5.Для некоторого сегмента Г > 1 выбираем произвольную допустимую грань .
6.Поместим произвольную –цепь в грань ; заменим на и перейдемк п.1
7.Построена укладка графа на плоскости. Конец.
1
2
3
4
23
1
2
3
4
|
8 |
9 |
10 |
|
|
||
|
|
|
2 |
3 |
4 |
5 |
6 |
|
||||
|
|
1 |
7 |
24