Презентации лекций / Презентация лекции 11 ДМ нов 20
.pdf
1
2
3
Для всякогосвязногоплоского графа верно равенство 4
– формула Эйлера
S -множествограней, -множестворебер, - множествовершин
,
Граф 
, непланарен
11
План лекции
1.Укладка графов в 3-х мерном пространстве
2.Укладка графа на плоскости, планарныеграфы
3.Критерии планарности
4.Алгоритм укладки графа на плоскости
12
В графе два ребра
= и =
( –вершина графа степени2) замененонаодно = ,
а остальныевершиныи ребране изменились.
Включение |
|
|
вершины |
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
В графе одно из ребер = |
2 |
|||||
|
|
|
|
|
|||||
|
|
|
|
|
замененонадва новых |
3 |
|||
|
|
|
|
= и |
|
= |
|
4 |
|
|
|
|
|
|
|
|
|
||
|
|
|
|
( – новая вершина графа), |
|
||||
|
|
|
|
|
а остальныевершиныи ребране |
|
|||
|
|
|
|
изменились. |
|
|
|||
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
= ( ,) |
Исключение |
|
|
|
|
|
|
|
|
вершины |
|
|
|
||
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
13 |
1
2
3
4
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
||
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
14 |
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
2 |
|
|
|
|
|
|
3 |
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
, |
Пример: |
|
2 |
|
|
2 |
2 |
|
|
|
|
|
1 |
|
|
|
7 |
|
|
7 |
|
1 |
6 |
3 |
1 |
6 |
3 |
|
|
8 |
|
8 |
|
||
|
|
|
|
|
8 |
6 |
|
10 |
9 |
|
10 |
9 |
|
|
|
4 |
|
|
9 |
5 |
|
5 |
|
5 |
4 |
||
|
|
|
|
|
||
|
Граф непланарен: |
|
|
Его подграф гомеоморфен , |
15 |
|
1
2
3
4
(1) |
(2) |
(3) |
Отождествляем |
Отождествляем |
Отбрасываем |
концы и |
возникшиеприэтом |
возникшиеприэтом |
ребра = |
кратныеребра |
петли |
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
( ) |
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
( ) |
|
|
|
|
|
16
1
2
3
4
получениз путемприменения конечногочисларазоперации стягиванияребер
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
( ) |
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
стянем |
и |
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
||||
|
|
|
|
|
|
|||
|
|
|
|
|
|
( ) |
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
17
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
, |
Пример: |
|
2 |
|
|
|
|
|
|
|
|
7 |
|
|
(2)7 |
|
(2)7 |
|
|
|
|
|
|
|
|
||
|
|
3 |
|
|
|
|
|
|
1 |
6 |
8 |
1(6) |
|
|
1(6) |
|
|
|
|
3(8) |
3(8) |
|||||
|
|
|
|
|||||
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
10 |
9 |
|
|
|
|
|
|
|
|
|
|
5(10) |
|
4(9) |
5(10) |
4(9) |
|
|
|
|
|
|
|
||
|
5 |
4 |
|
|
|
|
|
|
|
|
|
|
|
Его можно стянуть к |
|
||
|
Граф непланарен: |
|
|
|
18 |
|||
|
|
|
|
|
|
|||
План лекции
1.Укладка графов в 3-х мерном пространстве
2.Укладка графа на плоскости, планарныеграфы
3.Критерии планарности
4.Алгоритм укладки графа на плоскости
19
Пусть = (, ) планарный подграф связного графа = ( ,) и построенаегоплоскаяукладка |
1 |
||||||||
2 |
|||||||||
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
3 |
|
Сегмент R |
|
|
ребро = ,такоечто ,а , |
|
4 |
||||
|
|
|
|
|
|
|
|
||
относительно |
|
связнаякомпонентаграфа − ,дополненнаявсеми |
|
||||||
|
|
|
|||||||
|
|
ребрамиграфа,инцидентнымивершинамвзятой |
|
||||||
|
|
|
компоненты,иконцамиэтихребер |
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Вершину сегмента |
|
|
|
|
|
|
|
||
|
|
|
|
|
|
||||
|
|
|
|
|
|
||||
относительно |
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|||
будем |
|
|
|
|
|
|
|
|
|
называть контактной, |
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|||
если . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
||
Контактные вершины |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
на диаграммах сегментов |
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
||
будем обозначать кружками. |
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
20 |
||
|
|
|
|
|
|
|
|
||