Добавил:

oih07968 Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Полоцкий Государственный Университет

Предмет:

Дискретная математика

Файл:

2 Графы - лекции

.pdf

Скачиваний:

Добавлен:

18.02.2023

Размер:

1.58 Mб

Скачать

☆

<<< < Предыдущая 1 2 3 4 56 / 66

Алгоритм укладки графа на плоскости. Пусть имеется некоторая

		~					~
плоская укладка подграфа G			графа G . Сегментом Gi			относительно G
называется подграф графа G одного из следующих двух видов:
1.	Ребро u		~	, x	~	~
		(x; y) G такое, что u G			G , y	G .
2.	Связная	компонента	~	дополненная всеми			рѐбрами
			графа G \ G ,
графа G , инцидентными вершинам взятой компоненты, и концами этих
рѐбер.							~
Вершина z сегмента Gi
			называется контактной,			если z	G . Граф
~			он разбивает плоскость на грани. Допусти-
G – плоский, следовательно,
мой гранью для сегмента Gi относительно				~	называется грань Г графа
				G
~
G , содержащая все контактные вершины сегмента Gi . Пусть							Г (Gi ) –

множество допустимых граней для Gi . Для непланарных графов может

быть Г (Gi ) .

Рассмотрим путь сегмента Gi без петель и кратных рѐбер, соединяющий две различные контактные вершины и не содержащий других контактных вершин. Такие пути называются б -путями. Всякий б -путь может быть уложен в любую грань, допустимую для данного сегмента.

Два сегмента G1 и G2	относительно	~	называются конфликтующи-
Два сегмента G1 и G2	относительно	G	называются конфликтующи-
ми, если
1. и Г (G1 ) Г (G2 )	.
2. Существуют два б -пути L1 G1		и	L2 G2 , которые нельзя уло-

жить без пересечений одновременно ни в какую грань Г и.

Пусть G – плоская укладка некоторого подграфа графа G . Для каж-

дого сегмента Gi относительно G находим множество допустимых граней. Тогда может осуществиться один из трѐх случаев:

1.Существует сегмент Gi , для которого Г (Gi ) . В этом случае

исходный граф непланарен.

2. Для некоторого сегмента Gi существует единственная допустимая грань Г . Тогда можно расположить любой б -путь сегмента Gi в грани Г . При этом грань Г разобьѐтся на две грани.

3.Г (Gi ) 2 для Гi . В этом случае можно расположить б -путь в

любой допустимой грани.

Сам алгоритм укладки планарного графа G на плоскость состоит из следующих шагов.

Шаг 1. Выбираем любой простой цикл13 C графа G . Этот цикл

	~	C .
укладывается на плоскости и полагается G		C .
	~
	Шаг 2. Находим все грани графа G и все сегменты Gi относительно
~	. Если множество сегментов пусто, то переходим на шаг 7.
G	. Если множество сегментов пусто, то переходим на шаг 7.
	Шаг 3. Для каждого сегмента Gi определяем множество допустимых
граней Г (Gi ) . Если найдѐтся сегмент Gi ,		для которого Г (Gi )	, то ис-

ходный граф G непланарен. Конец алгоритма, иначе – переход на шаг 4. Шаг 4. Если существует сегмент Gi , для которого имеется един-

ственная допустимая грань Г , то происходит переход на шаг 6, иначе – на шаг 5.

	Шаг 5. Для некоторого сегмента Gi , для которого Г (Gi ) 1, выбира-
ем произвольную допустимую грань.
	Шаг 6. Произвольный б -путь L сегмента Gi помещается в грань Г ,
~	~
G	заменяется на G L и переход на шаг 1.
	~	на плоскости. Конец алгорит-
	Шаг 7. Построена укладка G графа G	на плоскости. Конец алгорит-

ма.

►Пример. Осуществить плоскую укладку графа G , изображѐнного на рис. 11.

			x1	x2		x3		x4
		G
			x8	x7		x6		x5
					Рис. 11
	Решение
	Шаг 1. Выберем простой цикл C					{x1 , x2 , x3 , x4 , x5 } , который разби-
вает плоскость на две грани Г1				и Г	2 . Положим		~	C .
вает плоскость на две грани Г1				и Г	2 . Положим		G	C .
	Шаг 2. Изобразим граф			~	C и сегменты G1 , G2 исходного графа
	Шаг 2. Изобразим граф			G	C и сегменты G1 , G2 исходного графа
G		~
G	относительно G		(рис. 12). Контактные вершины обведены кружками.
Г (Gi ) {Г1 , Г2 }, i			1, 2 .
	x1	x2	x3		x8	x7	x6	x3

~
13 G
Простым циклом называется путь, содержащий различные вершины (кроме крайних) и раз-
личные рѐбра.	Г2	G1			G2
Г1
x5	x4	x1	x4	x5	x5
		x1	x4	x5	x5
					98

Рис. 12

Шаг 3. Г (Gi )			, i	1, 2 .
Шаг 4. Нет сегмента, для которого имеется единственная допустимая
грань.
Шаг 5. Любой б -путь можно уложить в						Г1 или	Г 2 . Выберем для
укладки грань Г1 .
Шаг 6. Пусть L			{x1 , x8 , x7 , x6 , x5 }. Поместим этот б -путь в Г1 . Воз-
		~
никает новый граф G			и его сегменты (рис. 13)			G1 , G2 , G3 . Появляется и
новая грань Г 3 .
x8		x1		x2	x3	x8	x6	x3
~
G					G1	G2		G3
Г1	Г2			Г3	G1	G2		G3
	Г2			Г3

x7		x6		x5	x4	x4	x4	x5
					Рис. 13
Переходим на шаг 1.
Шаг 1. Новых сегментов три: G1 , G2 , G3 .
Шаг 2. Г (G1 ) {Г1}, Г (G2 ) {Г1} , Г (G3 ) {Г1 , Г3}.
Шаг 3. Г (Gi )			, i	1, 2, 3 .

	Шаг 4. Г (G1 ) Г (G2 )	{Г1}, переход на шаг 6.
	Шаг 6. б -путь L1	{x4 , x8 } поместим в	грань Г1 , б -путь
L2	{x4 , x6 } также поместим в эту грань. В результате возникает новый
граф	~
граф	G , изображѐнный на рис. 14. Этот граф имеет пять граней и один

сегмент.

x8	x1	x2 Г4	x3
			x3

~
G
Г1				G1
Г1	Г2	Г3
	Г2	Г3
x7	x6	x5 Г5	x4	x5
				x5
			Рис. 14
Шаг 1. G1 – ребро (x3 , x5 ) .
Шаг 2. Г (G1 )		{Г3}.
Шаг 3. Г (G1 ) .
Шаг 4. Г (G1 )		{Г3}, переход на шаг 6.
Шаг 6. б -путь		L1 {x3 , x5 } поместим в грань Г 3 . Новый граф			~
Шаг 6. б -путь		L1 {x3 , x5 } поместим в грань Г 3 . Новый граф			G

(рис. 15) является плоской укладкой исходного планарного графа.

x8	x1	x2	Г6	x3
~
G
Г1	Г2	Г3	Г4
	Г2	Г3	Г4
x7	x6	x5	Г5	x4

Рис. 15

◄

100

<<< < Предыдущая 1 2 3 4 56 / 66

Соседние файлы в предмете Дискретная математика

#
18.02.20231.3 Mб31 Множества. Логика Буля - лекции.pdf
#
18.02.20231.58 Mб22 Графы - лекции.pdf
#
18.02.2023449.45 Кб43 Элементы комбинаторики - лекции.pdf
#
18.02.2023450 Кб25 Контрольная работа.pdf