Файл: Дискретная_мат._пос.pdf

 81 
 

3.3.3. Критерий планарности 
 
Графы 

5

K

 и 

3

,

3

K

 (рис. 3.7) интересны тем, что они являются эталонами 

непланарных  графов.  Все  другие  непланарные  графы  имеют  подграфы, “по-
добные” или 

5

K

, или 

3

,

3

K

. Что значит “подобные”? 

Элементарное стягивание графа 

)

,

(

U

X

G

=

 заключается в следующем: 

а) удаляем ребро 

}

,

{

y

x

из 

U

; б) заменяем символы 

x

 и 

y

 в 

U

 на новый символ  

z

; в) удаляем вершины  

x, y

 из  

X

; г) добавляем 

z

 в 

X

. Элементарное стягивание 

графа 

G

 означает слияние двух смежных вершин 

x

 и  

y

  в одну 

z

 после удале-

ния ребра между ними. 

Граф 

1

G

  называется  стягиваемым  к  графу 

2

G

,  если 

2

G

  может  быть 

получен из 

1

G

 путем последовательных элементарных стягиваний (рис. 3.8). 

Первый  критерий  планарности  независимо  друг  от  друга  доказали  рус-

ский математик Л.С. Понтрягин и польский математик К. Куратовский. 

Теорема  Понтрягина - Куратовского.  Граф  планарен  тогда  и  только  то-

гда, когда он не содержит подграфов, стягиваемых к 

5

K

 или 

3

,

3

K

. 

Пример.  Граф 

1

G

(рис. 3.9, а)  является  непланарным,  так  как  его  под-

граф 

2

G

 (рис. 3.9,  б)  изоморфен  графу 

3

,

3

K

  (рис.  3.9, в).  Вершины  графа  

 82 
 

2

G

покрашены в два цвета, чтобы   легче      было      установить    изоморфизм    

2

G

3

,

3

K

3.3.4. Решение задачи 7 контрольной работы №2 
 
Задача. Даны графы 

1

G

и 

2

G

(рис. 3.10). Показать,  что  графы  изоморф-

ны. Является ли граф 

1

G

планарным? 

Решение. Число вершин 

1

n

 и число ребер 

1

m

графа 

1

G

совпадает с чис-

лом  вершин 

2

n

  и  числом  ребер 

2

m

графа 

2

G

: 

8

,

6

2

1

2

1

=

=

=

=

m

m

n

n

. 

Зададим произвольную нумерацию вершин и ребер графа 

1

G

. В графе 

1

G

 две 

вершины  

1

x

 и 

2

x

имеют степень 

2

)

(

)

(

2

1

=

=

x

p

x

p

. Найдем в графе 

2

G

 две 

вершины, имеющие степень 2 и обозначим их 

1

y

 и 

2

y

. 

Вершина 

1

x

смежна вершинам 

3

x

 и 

4

x

. Обозначим 

3

y

 и 

4

y

 вершины 

графа  

2

G

, смежные вершине 

1

y

. Соответственно ребрам 

1

u

 и 

2

u

 графа 

1

G

, 

занумеруем 

2

1

, v

v

  ребра  графа 

2

G

,  инцидентные  вершинам 

1

y

и 

3

y

, 

1

y

  и 

4

y

.  Далее  занумеруем  в  графе   

2

G

  вершины,  смежные  с 

2

y

,  как 

6

5

, y

y

,  а 

2 

 83 
 
инцидентные  им  ребра 

3

4

, v

v

.  Вершина 

4

x

в  графе 

1

G

смежна  вершинам 

5

3

1

,

,

x

x

x

; обозначим соответствующие  ребра 

7

6

2

,

,

v

v

v

. Ребру 

}

,

{

5

3

5

x

x

u

=

графа 

1

G

сопоставим  ребро 

}

,

{

5

3

5

y

y

v

=

  графа 

2

G

;  ребру 

}

,

{

6

5

8

x

x

u

=

  – 

ребро 

}

,

{

6

5

8

y

y

v

=

.  Построена  биекция 

,

6

,

1

,

)

(

,

:

2

1

=

=

→

i

y

x

G

G

i

i

ϕ

ϕ

8

,

1

,

)

(

=

=

i

v

u

j

j

ϕ

  такая,  что  смежным  вершинам 

i

x

  и 

j

x

  графа 

1

G

  сопос-

тавляются  смежные  вершины 

i

y

  и 

j

y

.  Следовательно,  графы

1

G

и 

2

G

  изо-

морфны. 

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

3

G

,  изо-

морфный графу 

1

G

(рис. 3.11). Граф 

1

G

является планарным. 

 
3.3.5. Контрольные вопросы и упражнения 
 
1.

Какие графы называются изоморфными? 

2.

Изоморфны ли графы 

8

K

 и 

4

,

2

K

? 

3.

Запишите  матрицы  смежности  изоморфных  графов 

1

G

  и 

2

G

(рис.3.6). 

4.

Как  связаны  между  собой  матрицы  инцидентности  двух  изоморф-
ных графов? 

5.

Какой граф называется плоским? 

6.

Какой граф называется планарным? 

 
3.4. Связность графов 
 
3.4.1. Маршруты 
 
Пусть 

задан 

неорграф 

)

,

(

U

X

G

=

. 

Последовательность 

1

3

2

2

1

1

+

k

k

x

u

x

u

x

u

x

…

  вершин 

,

X

x

i

∈

1

,

1

+

=

k

i

,  и  ребер 

,

U

u

j

∈

k

j

,

1

=

 84 
 
графа 

G

 называется маршрутом  длины 

k

, соединяющим вершины 

1

x

и 

1

+

k

x

. 

Вершина 

1

x

называется  начальной,  а 

1

+

k

x

–  конечной  вершиной  маршрута. 

Маршрут  называется  замкнутым,  если  его  конечная  вершина  совпадает  с 
начальной. Незамкнутый маршрут, в котором все ребра различны, называется  
цепью. Цепь, в которой все вершины различны, называется  простой цепью. 
Замкнутый маршрут, в котором все ребра различны, называется циклом. Цикл, 
в  котором  все  вершины  (кроме  начальной  и  конечной)  различны,  называется 
простым. 

Пример.  В  графе 

G

  (рис. 3.12) последователь-

ность 

4

2

5

1

2

5

c

b

f

a

b

  определяет  марш-рут  длины 5, 

соединяющий вершину 5 с вершиной 4; 

4

5

3

1

2

5

e

g

d

a

b

–  цепь  длины 5; 

4

2

5

c

b

–  простую  цепь; 

5

4

2

5

e

c

b

– 

простой цикл. 

 
3.4.2. Компоненты связности 
 
Граф 

)

,

(

U

X

G

=

  называется  связным,  если  для  любой  пары  вершин 

X

y

x

∈

,

 найдется цепь, соединяющая эти вершины. Например, граф 

1

G

 (рис. 

3.13)  является  связным,  а  граф 

2

G

 – нет  (вершины 

1

x

  и 

2

x

  не  могут  быть 

соединены цепью). 

Компонентой  связности    графа 

G

  называется  максимальный  связный 

подграф графа 

G

. Слово “максимальный ” здесь означает, что добавление лю-

бой  вершины  графа 

G

  превращает  этот  граф  в  несвязный.  Так,  у  графа 

2

G

(рис. 3.13) имеется  две  компоненты  связности: 

G

′

 – подграф,  содержащий 

вершины x

5

,x

2

 и соединяющее их ребро; 

G

′′

 – вершины 

4

3

1

,

,

x

x

x

и соединяю-

щие  их  ребра.  Подграфы 

G

′

  и 

G

′′

  не  имеют  общих  вершин  и  ребер,  причем 

 85 
 

G

G

G

′′

∪

′

=

2

, т.е. множество компонент связности {

G

′

,

G

′′

} образует  разби-

ение графа 

2

G

. 

 
3.4.3. Эйлеровы цепи и циклы 
 
Задача. Дан граф 

)

,

(

U

X

G

=

. Требуется построить цикл (цепь), прохо-

дящий через все ребра графа 

G

 ровно по одному разу. Такой цикл (цепь), если 

он существует, называется эйлеровым циклом (цепью), а граф 

G

 – эйлеровым 

графом. В популярной формулировке эта задача звучит так: заданную плоскую 
фигуру нарисовать, не отрывая карандаша от бумаги и не проходя по одной и 
той же линии дважды (рис. 3.14). 

Теорема 1 (об эйлеровом цикле). Для того, чтобы в графе 

G

 существовал 

эйлеров цикл, необходимо и достаточно, чтобы: 1) он был связен; 2) степени 
всех вершин были четными. 

Необходимость. Пусть в графе 

G

 существует эйлеров цикл. Тогда граф 

G

связен (любую пару вершин можно соединить цепью – частью эйлерова цик-
ла),  и  степень  каждой  вершины  четна:  так  как  все  ребра  эйлерова  цикла  раз-
личны,  то  с  каждым  проходом  эйлерова  цикла  через  вершину 

x

  в  этот  цикл 

войдут два новых инцидентных вершине 

x

 ребра, следовательно, общее число 

ребер, инцидентных вершине 

x

,

 четно. 

 Достаточность докажем индукцией по количеству ребер 

m

. 

Основание  индукции.  Проверим  справедливость  теоремы  при 

3

0

=

=

m

m

. Пусть граф 

G

 связен и все вершины его имеют четную степень. 

Тогда граф может быть только таким, как на рисунке 3.15, а. Очевидно, что в 
нем есть эйлеров цикл.  

Индукционный  переход.  Предположим,  что  теорема  справедлива  для 

всех графов с числом ребер 

k

m

≤

. Покажем, что теорема справедлива и  для 

графов с числом ребер 

).

1

(

)

(

:

1

+

=

⇒

≤

+

=

k

m

T

k

m

T

k

m

Пусть 

)

,

(

U

X

G

=

связный  граф,  все  вершины  которого  имеют  четную 

степень и 

.

1

+

=

k

U