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

Дискретная

математика

С

одержание

Введение3

Комбинаторика_ 3

§1. Правила суммы и прямого произведения.3

§2.Размещения с повторениями.4

§3. Размещения без повторений.4

§4. Перестановки.5

§5. Сочетания.5

§6. Сочетания с повторениями.6

§7. Перестановки с повторениями. Мультимножества.7

§8. Полиномиальная формула.7

Методы подсчета и оценивания.8

§1. Производящие функции.8

§2. Линейные операции.8

§3. Сдвиг начала вправо.9

§4. Сдвиг начала влево.9

§5. Частичные суммы.9

§6. Дополнительные частичные суммы.9

§7. Изменение масштаба10

§8. Свертка.10

§9. Линейные рекуррентные соотношения.11

§10. Неоднородные линейные рекуррентные соотношения.12

§11. Числа Фибоначчи.15

Введение в теорию графов17

§1. Основные понятия теории графов.17

§2. Ориентированные и неориентированные графы.18

§3. Изоморфизм графов. Подграф. Связные графы.20

§4. Способы представления графов.24

§5. Число ребер простого графа. Разрезы.26

§6. Эйлеровы графы.27

§7. Гамильтоновы графы.29

§8. Деревья.29

§9. Двудольные графы.31

§10. Укладка графов.33

§11. Планарные и плоские графы. Теорема Эйлера о плоских графах.33

§12. Раскрашивание графов.35

Литература_ 36

Введение

Слово «дискретный» происходит от латинского discretus, что означает разделенность, прерывистость и противопоставляется непрерывности. Например, дискретное изменение какой-либо величины во времени – это изменение, происходящее через определенные промежутки времени (скачками); система целых чисел (в противоположность системе действительных чисел) является дискретной.

Дискретная математика – область математики, занимающаяся изучением свойств дискретных структур, которые возникают как внутри математики, так и в ее приложениях (в частности, в вычислительной технике и программировании). Традиционно к дискретной математике относят такие области математического значения, как комбинаторика, теория чисел, математическая логика, теория алгебраических систем, теория графов и т.д.

Комбинаторика

Простейшие понятия комбинаторики появились еще в доньютоновский период (П.Ферма, Б.Паскаль, Франция XVIII в.). Комбинаторика возникла как основа дискретной теории вероятностей в связи с исследованиями в области азартных игр.

Напомним некоторые важные обозначения. Множества будем обозначать заглавными буквами, а элементы множеств – малыми буквами.

а∈А – элемент а принадлежит множеству А.

{a, b, x, y} – в фигурных скобках изображаются множества заданные перечислением элементов.

|A| - мощность множества, количество множества.

А´В={(a,b) | a∈A, b∈B} – прямое произведение множеств.

АÈВ={x| x∈A или x∈B} – объединение множеств.

АÇВ={x| x∈A и x∈B} – пересечение множеств.

АВ={x| x∈A и xÏB} – разность множеств.

Æ – пустое множество.

U – универсальное множество.

=UА={x| xÏA} – дополнение множества.

§1. Правила суммы и прямого произведения.

Правило суммы
. Пусть А и В конечные множества такие что АÇВ=Æ, |A|=m, |B|=n. Тогда |AÈB|=m+n.

В общем случае: Пусть X1
, X2
, …, Xn
– попарно не пересекающиеся множества, Xi
ÇXj
=Æ, где i¹j. Тогда выполняется равенство: .

Правило прямого произведения.
Пусть А, В – конечные множества, |A|=m, |B|=n. Тогда |A´B|=m∙n.

В общем случае: Пусть X1
, X2
, …, Xk
– произвольные множества, |Xi
|=ni
, i=. Тогда |X1
, X2
, …, Xk
|=|{(x1
, x2
, …, xk
)| xi
∈Xi
, i=}|=n1
∙n2
∙…nk
.

Пример.
Сколько четырехзначных чисел можно составить из цифр 0, 1, 2, 3, 4, 5, если: а) ни одна из цифр не повторяется более одного раза; б) цифры могут повторяться; в) числа должны быть нечетными (цифры могут повторяться)?

Решение.

а) Первой цифрой числа может быть одна из пяти цифр: 1, 2, 3, 4, 5. Когда первая цифра выбрана, то вторая может быть выбрана пятью способами, третья цифра уже может быть выбрана четырьмя способами, четвертая – тремя способами. Согласно правилу умножения общее число способов равно: 5∙5∙4∙3=300.

б) Первая цифра – одна из {1, 2, 3, 4, 5}. Каждая из следующих цифр будет из множества {0, 1, 2, 3, 4, 5}. Итак, число искомых чисел: 5∙6∙6∙6=1080.

в) Первая цифра принадлежит {1, 2, 3, 4, 5}. Четвертая цифра принадлежит {1, 3, 5}. Вторая и третья цифра принадлежит {0, 1, 2, 3, 4, 5}. Всего чисел: 5∙6∙6∙3=540.

§2.Размещения с повторениями.

Имеются предметы n различных видов а1
, а2
, …, аn
.
Из них составляют всевозможные расстановки длины k. ( Например, а2
а1
а3
а3
а4
– расстановка длины 5). Такие расстановки называются размещениями с повторениями из
n
по
k
элементов.

Найдем общее число расстановок, среди которых две расстановки считаются различными, если они отличаются друг от друга или видом входящих в них предметов, или порядком этих предметов.

При составлении указанных расстановок длины k на каждое место можно поставить предмет любого вида. Рассмотрим множества Х1
=Х2
=…=Хk
={a1
, a2
, …, an
}. Тогда все размещения с повторениями составят множество Х1
´Х2
´…´Хk
. По правилу прямого произведения получаем, что общее число размещений с повторениями из n элементов по k местам равно |Х1
´Х2
´…´Хk
|=nk
.

§3. Размещения без повторений.

Имеются n различных предметов а1
, а2
, а3
, …, аn
. Сколько из них можно составить расстановок длины k. Две расстановки считаются различными, если они отличаются видом входящих в них элементов или порядком их в расстановке. Такие расстановки называются размещенные без повторений, а их число обозначают .

При составлении данных расстановок на первое место можно поставить любой из имеющихся n предметов. На второе место можно поставить только любой из n-1 оставшихся предметов. И наконец, на k-ое место – любой из n-k+1 оставшихся предметов. Таким образом, по правилу прямого произведения =n(n-1)(n-2)∙…∙(n-k+1)=.

Пример.
В соревнованиях участвуют 17 команд. Сколькими способами могут быть распределены три призовые места?

Решение.
Первое место, то есть золотая медаль, может получить любая из 17 команд так как одна команда не может сразу получить две медали, то серебренная медаль уже может получить любая команда из 16 оставшихся. И наконец, бронзовую медаль – любая из 15 оставшихся. Итак, тройку призеров можно выбрать А=17∙16∙15=4080. Или по формуле:

А=15∙16∙17=4080.

§4. Перестановки.

При составлении размещений без повторений из n по k мы получаем расстановки, отличающиеся друг от друга либо составом, либо порядком элементов. Но если брать расстановки, которые включают все n элементов, то они могут отличаться друг от друга лишь порядком входящих в них элементов. Такие расстановки называются перестановками из n элементов, а их число обозначается Рn
. Pn
=A=n!

Пример.

1) |S3
|=P3
=3!=6

|S4
|=P4
=4!=24

2) Сколькими способами можно расположить на шахматной доске 8 ладей, чтобы они «не били» друг друга?

Решение.
Условие «не могли бить» означает, что на каждой горизонтали и вертикали может стоять лишь одна ладья. Ввиду этого, каждому расположению ладей на доске соответствует перестановка π=. Верхняя строка – это номера горизонталей, нижняя – вертикалей.

а1
– номер вертикали, в которой стоит ладья из первой горизонтали,

а2
– номер вертикали, в которой стоит ладья из второй горизонтали, и т.д.

Среди чисел а1
а2
…а8
нет ни одной пары равных, иначе две ладьи попали бы в одну вертикаль. Согласно, расположению ладей соответствует определенная перестановка чисел 1, …, 8 и наоборот, каждой перестановке чисел 1, …, 8 соответствует такое расположение ладей на шахматной доске, при котором они «не бьют друг друга»

Всего таких перестановок Р8
=8!=40320.

§5. Сочетания.

В тех случаях, когда нас не интересует порядок элементов в расстановке, а интересует лишь ее состав, то говорят о сочетаниях.

Сочетаниями
из n различных элементов по k местам называют все возможные расстановки длины k, образованные из этих элементов и отличающиеся друг от друга составом, но не порядком элементов.

# 123 и 132 – одинаковые сочетания.

Общее число сочетаний обозначают С. Определим это число

# Число сочетаний из 5 элементов по 3.

1, 2, 3, 4, 5.

123 134 234 345

124 135 235

125 145 245

В общем случае составим все сочетания из n по k. Затем переставим в каждом сочетании элементы всеми возможными способами. Получаем расстановки, отличающееся либо составом, либо порядком, то есть это все размещения без повторений из n элементов по k местам. Их число А. Учитывая, что каждое сочетание дает k! размещений, получаем: С∙k!=A. Следовательно, С=. Из формулы непосредственно следует, что С=С.

Пример.
Сколькими способами из 7 человек можно сформировать комиссию, состоящую из трех человек?

С==35.

§6. Сочетания с повторениями.

Имеются предметы n различных видов число элементов каждого вида неограниченно. Сколько существует расстановок длины k, если не принимать во внимание порядок элементов? Такие расстановки называются сочетаниями с повторениями
и обозначаются .

Пусть а, b, с, …, d– исходные различные типы элементов, количество которых n. Рассмотрим произвольное сочетание с повторениями cbbcaccda…ccbbb из данных типов элементов. Так как порядок элементов не учитывается, то расстановку можно записать так: aa…a|bb…b|cc…c|…|dd…d где элементы каждого из типов завершается вертикальной чертой, за исключением последней серии элементов. Длина такой расстановки с учетом вертикальных линий составляет k+(n-1)=n+k-1, где k – количество элементов в расстановке, (n-1) – число вертикальных линий. Очевидно, что любую такую расстановку можно задать выбором из n+k-1 мест n-1 место для положений вертикальных линий. Это можно сделать С способами. Промежуточные места между линиями заполняются соответствующими типами элементов. Таким образом, =С=С.

Пример.
Трое ребят собрали в саду 7 яблок. Сколькими способами они могут их разделить между собой?

Решение.
Поставим в соответствие каждому делению яблок между ребятами сочетание с повторениями следующим способом. Типами элементов в нашем случае будут ребята. Таким образом, имеем три типа элементов a, b, c (n=3) из которых предстоит составить все различные расстановки k=7. Наличие в расстановке какого либо из элементов a, b, с отвечает принадлежности данного яблока соответствующему мальчику. Порядок элементов в такой расстановке не играет роли. При делении яблок между ребятами не важно, какое из них попадет тому или иному мальчику. Тогда число способов разделить яблоки между ребятами равно

=С=С===36

§7. Перестановки с повторениями. Мультимножества.

Имеются предметы k различных видов. Сколько существует перестановок из n1
элементов первого типа, n2
элементов второго типа и т.д., nk
элементов k-го типа?

Рассмотрим например, мультимножество (множество, содержащее повторяющееся элементы): М={a,a,a,b,b,c,d,d,d,d}={3∙a, 2∙b, 1∙c, 4∙d}. Таким образом искомые перестановки мультимножества М. Если рассмотреть М как множество с различными элементами, обозначив их а1
, а2
, а3
, b1
, b2
, c1
, d1
, d2
, d3
, d4
, то получили бы 10! перестановок. Но после отбрасывания индексов многие из них оказались бы одинаковыми. Фактически каждая перестановка множества М встретилась бы ровно 3!∙2!∙1!∙4! раз, так как в любой перестановке М индексы при буквах а можно расставить 3! способами, при буквах b – 2! способами, при с – одним способом, при d – 4! способами. Поэтому число перестановок множества М равно .

В общем случае Р(n1
, n2
, …, nk
)=, где n=n1
+n2
+…+nk
– общее число элементов.

Справедлива формула: Р(n1
, …, nk
)=C.

Пример.
Сколько существует различных перестановок из букв слова «математика»? Р(3а, 2т, 2м, 1е, 1и, 1к)==151200.

§8. Полиномиальная формула.

Формула (х1
+х2
+…+хk
)n
= называется полиномиальной, где суммирование выполняется по всем решениям уравнения n1
+n2
+…+nk
=n в целых неотратимых числах, ni
≥0, i=1,2,…k.

При k=2 получаем частный случай полиномиальной формулы – бином Ньютона (а+b)n
=.

Методы подсчета и оценивания.

§1. Производящие функции.

Любая а0
, а1
, а2
, … - произвольная последовательность. Сопоставим последовательности функцию действительного или компактного переменного

А(х)=(1)

Функция А(х) называется производящей функцией последовательности а0
, а1
, …. Как правило, поиск функции А(х) по формуле (1) прямыми методами является сложной задачей. Однако, последовательность {ak
} может быть восстановлена по А(х). Выражение (1) является разложением А(х) в ряд Маклорена. Приведем некоторые наиболее распространенные производящие функции и соответствующие им последовательности.

Производящие функции, А(х)	Последовательности, {ak }
	ak =1, k≥0
	ak =k+1, k≥0
	a0 =0, ak =, k≥1
	a0 =0, ak =, k≥1
	ak =, k≥0
	ak =, k≥0, r – любое
	ak =, k≥1, r – любое
	ak =, k≥0, r – любое

Простейшие производящие функции будем использовать для получения производящих функций более сложных последовательностей. С этой целью рассмотрим наиболее важные из операций над производящими функциями, то есть способы получения новых производящих функций и соответствующих им последовательностей. Обозначим через {ak
}, {bk
}, {ck
} последовательности, а соответствующие им производящие функции как А(х), В(х), С(х).

§2. Линейные операции.

Если α и β – константы, то последовательность ck
=αak
+βbk
имеет производящую функцию С(х)=αА(х)+βВ(х).

# ak
=1 A(x)=

bk
=B(x)=ex

ck
=100+C(x)=100A(x)+5B(x)=+5ex
.

§3. Сдвиг начала вправо.

Пусть последовательность {bk
} определяется через {ak
} следующим образом: bk
=0 для k=0, 1, …, i-1 и bk
=ak
-
i
для k=i, i+1, …. Тогда, В(х)=хi
A(x). Действительно,

В(х)=А(х).

§4. Сдвиг начала влево.

Пусть последовательность {bk
} определяется через {ak
} следующим образом: bk
=ak
+
i
для k=0, 1, 2, …, тогда, В(х)=[A(x)-]x-
i
. Действительно,

В(х)=

.

§5. Частичные суммы.

Пусть последовательность {bk
} определяется через {ak
} следующим образом: bk
= для k=0, 1, 2, …. Тогда, В(х)=. Действительно,

В(х)=

=а0
+(а0
+а1
)х+(а0
+а1
+а2
)х2
+(а0
+а1
+а2
+а3
)х3
+…+(а0
+а1
+…+аk
)хk
+…= =a0
(1+x+x2
+x3
+…)+a1
x(1+x+x2
+x3
+…)+ a2
x2
(1+x+x2
+x3
+…)+…= =(a0
+a1
x+a2
x2
+…)(1+x+x2
+x3
+…)=

=A(x)=.

§6. Дополнительные частичные суммы.

Пусть последовательность {bk
} определяется через {ak
} следующим образом: bk
= для k=0, 1, 2, …. Тогда, В(х)=. Действительно,

В(х)=

=а0
+а1
+а2
+…+а1
х+а2
х+а3
х+…+а2
х2
+а3
х2
+а4
х2
+…= =a0
+a1
(1+x)+a2
(1+x+x2
)+а3
(1+x+x2
+x3
)+…=

.

§7. Изменение масштаба

I.
Пусть последовательность {bk
} определяется через {ak
} следующим образом bk
=k×ak
. Тогда В(х)=хА¢(х). Действительно, А(х)= и А¢(х)= или хА¢(х)=

II.
Пусть последовательность {bk
} определяется через {ak
} следующим образом bk
=. Тогда В(х)=.

Так как А(х)=, то .

§8. Свертка.

Пусть последовательность {сk
} определяется через {ak
} и {bk
} следующим образом: ck
=, k=0, 1, …. Тогда С(х)=А(х)×В(х). Действительно: A(x)=,B(x)=.

C(x)=

.

§9. Линейные рекуррентные соотношения.

Рассмотрим последовательность {un
}, n=0,1,2…. Будем говорить, что задано однородное линейное рекуррентное соотношение с постоянными коэффициентами порядка r, если для членов последовательности {un
} выполняется равенство:

un+r
=С1
un+r-1
+С2
un+r-2
+…+Сr
un
, (1)

где Сi
, i= – постоянные величины. Выражение (1) позволяет вычислить очередной член последовательности по предыдущим r членам. Ясно, что, задав начальные значения u0
, u1
, …, ur
-1
, можно последовательно определить все члены последовательности.

Рассмотрим общий метод решения рекуррентного соотношения (1), то есть поиска un
, как функции от n. для решения задачи достаточно найти производящую функцию

U(x)=(2)

последовательности {un
}. Введем обозначение:

К(х)=1-С1
х-С2
х2
-…-Сr
xr

и рассмотрим произведение U(x)K(x)=C(x), deg C(x)£r-1, так как коэффициенты при xn
+
r
, n=0,1,2… в произведении U(x)K(x) с учетом (1), равны:

un+r
-(С1
un+r-1
+С2
un+r-2
+...+Сr
un
)=0.

Характеристическим полиномом соотношения (1) называется многочлен

F(x)=xr
-С1
xr-1
-С2
xr-2
-…-Сr-1
x-Сr
(3)

Выполним разложение F(x) на линейные множители:

F(x)=(x-α1
)(x-α2
)…(x-αr
), где e1
+e2
+…+er
=r.

Сравнивая К(х) и F(x) можно записать: К(х)=xr
⋅F. Тогда

К(х)==

=(1-α1
х)(1-α2
х)…(1-αr
х), e1
+e2
+…+er
=r.

Данное разложение на множители используется для представления выражения U(x)= в виде суммы простых дробей:

U(x)==(4)

Таким образом, U(x) является суммой функций вида

.

Тогда выражение (4) примет вид:

U(x)==(5)

Данное разложение является производящей функцией U(x)= последовательности {un
}. Для определения un
необходимо найти коэффициент при хn
в разложении (5).

Пример.
Найти члены последовательности {un
}, удовлетворяющие рекуррентному соотношению un
+2
=5un
+1
-6un
, если u0
=u1
=1.

Решение.
Начальные условия: r=2, C1
=5, C2
=-6.

K(x)=1-5x+6x2

K(x)⋅U(x)=С(x), где U(x)=

С(х)=(1-5x+6x2
)(u0
+u1
x+u2
x2
+…)=

=u0
+u1
x+u2
x2
+…-5u0
x-5u1
x2
-5u2
x3
-…+6u0
x2
+6u1
x3
+6u2
x4
+…=

=u0
+(u1
-5u0
)x+(u2
-5u1
+6u0
)x2
+(u3
-5u2
+6u1
)x3
+…

Но u2
=5u1
-6u0
, u3
=5u2
-6u1
и так далее. Следовательно,

С(х)=u0
+(u1
-5u0
)x=1-4x.

Характеристическим полиномом будет F(x)=x2
-5x+6=(x-2)(x-3).

Отсюда следует, что U(x)==.

С помощью неопределенных коэффициентов разложим последнюю дробь в сумму дробей:

===.

Следовательно, Þ.

Тогда U(x)=, но =, и таким образом, и .

Итак, U(x)===.

Получаем, что uk
=2k
+1
-3k
.

§10. Неоднородные линейные рекуррентные соотношения.

Неоднородное линейное рекуррентное соотношение имеет вид:

un+r
=С1
un+r-1
+С2
un+r-2
+…+Сr
un
+bn
(1)

где величина bn
в общем случае является функцией от n. Общее решение соотношения (1) представляет собой сумму частного решения неоднородного уравнения (1) (то есть любого решения, которое ему удовлетворяет) и общего решения соответствующего ему однородного соотношения (1).

Общих способов определения частного решения нет, однако для некоторых значений bn
существуют стандартные приемы определения un
.

Пример.
Найти {un
}, если un+1
=un
+(n+1) и u0
=1.

Решение.
Умножив левую и правую части рекуррентного соотношения на хn
, получим:

un+1
xn
=un
xn
+(n+1)xn
.

Суммирование последнего уравнения для всех n дает:

.

Воспользуемся свойствами операций с производящими функциями:

=U(x) – по определению,

====,

= – см. табл. §9.

Итак, получаем =U(x)+.

Учитывая, что u0
=1, запишем:

U(x)-1=х×U(x)+,

U(x)-x×U(x)=1+,

U(x)×(1-x)=,

U(x)==.

Из таблицы следует == (так как ).

Тогда U(x)==(1-x+x2
) . Но U(x)=. Сравнивая коэффициенты при xn
, заключаем, что

un
==-+= ==(n2
+3n+2-n2
-n+n2
-n)=(n2
+n+2).

Ответ: un
=(n2
+n+2).

Для неоднородного линейного рекуррентного соотношения вида

un+2
+p×un+1
+q×un
=αn+β, (2)

где α, β, p, q – данные числа, справедливы следующие утверждения:

1) если х0
=1 не является корнем многочлена х2
+px+q, то частным решением рекуррентного соотношения (2) является последовательность u=аn+b;

2) если х0
=1 является простым корнем многочлена х2
+px+q, частное решение рекуррентного соотношения (2) может быть найдено в виде u=n(аn+b);

3) если х0
=1 является кратным корнем многочлена х2
+px+q, частное решение рекуррентного соотношения (2) может быть найдено в виде u=n2
(аn+b).

Найдем значения а и b в каждом из перечисленных случаев.

1) u=аn+b, u=а(n+1)+b, u=а(n+2)+b.

Подставляя эти значения в выражение (2). получим

an+2a+b+pan+pa+pb+qan+qb=αn+β,

(a+pa+qa)n+2a+b+pa+pb+qb=αn+β.

Следовательно, Так как х0
=1 не является корнем многочлена х2
+px+q, то 1+p+q¹0, и тогда имеем

а=,

b=.

2) u=n(аn+b), u=(n+1)(an+a+b), u=(n+2)(an+2a+b).

Подставляем эти значения в (2):

(n+2)(an+2a+b)+p(n+1)(an+a+b)+qn(an+b)=αn+β,

an2
+2an+nb+2an+4a+2b+pan2
+pan+pbn+pan+pa+pb+qan2
+qbn=αn+β,

(a+pa+qa)n2
+(4a+b+2pa+pb+qb)n+(4a+2b+pa+pb)=αn+β.

Тогда

1+p+q=0, так как х0
=1 является простым корнем многочлена х2
+px+q. Значит,

a(4+2p)=α Þ a=.

b==.

3) u=n2
(аn+b), u=(n+1)2
(an+a+b), u=(n+2)2
(an+2a+b).

(n+2)2
(an+2a+b)+p(n+1)2
(an+a+b)+qn2
(an+b)=αn+β,

Заметим, что, если х0
=1 является кратным корнем уравнения х2
+px+q=0, то уравнение имеет вид (х-1)2
=0 или х2
-2х+1=0, то есть р=-2 и q=1.

(n+2)2
(an+2a+b)-2(n+1)2
(an+a+b)+n2
(an+b)=αn+β,

(n2
+4n+4)(an+2a+b)-2(n2
+2n+1)(an+a+b)+an3
+bn2
=αn+β,

an3
+2an2
+bn2
+4an2
+8an+4bn+4an+8a+4b-2an3
-2an2
-2bn2
-4an2
-4an-4bn-2an-2a- -2b+an3
+bn2
=αn+β,

n3
(a-2a+a)+n2
(2a+b+4a-2a-2b-4a+b)+n(8a+4b+4a-4a-4b-2a)+(8a+4b-2a-2b)=αn+β.

Þ a=, b=.

Пример.
Решить рекуррентное соотношение un
+2
-3un
+1
+2un
=n, u0
=1, u1
=1.

Решение.
p=-3, q=2, α=1, β=0.

Соответствующее уравнение х2
-3х+2=0 или (х-1)(х-2)=0. х0
=1 является простым корнем многочлена, следовательно, частное решение будет иметь вид u=аn+b, где а==- и b==-.

Итак, u=n(-n-)=-n(n+1).

Найдем общее решение соответствующего однородного рекуррентного соотношения или . Начальные условия изменятся следующим образом , .

С1
=3, С2
=-2

К(х)=1-3х+2х2

С(х)=U(x)×K(x)=(1-3x+2x2
)=

=-3x+ +2x2
=

F(x)=x2
-3x+2=(x-2)(x-1)

K(x)=(1-2x)(1-x)

U(x)=Þ

Итак, .

§11. Числа Фибоначчи.

Последовательность Фибоначчи задается рекуррентным соотношением un
+2
=un
+1
+un
, u0
=1, u1
=1. То есть 1, 1, 2, 3, 5, 8, 13, 21, …. Найдем un
.

K(x)=1-x-x2

U(x)=

С(x)=K(x)×U(x)=u0
+u1
x+u2
x2
+…-u0
x-u1
x2
-u2
x3
-…-u0
x2
-u1
x3
-u2
x4
-…=

=u0
+u1
x-u0
x=1+x-x=1

F(x)=x2
-x-1=

K(x)=

U(x)==

.

ÞÞ

Þ B=, A=1-B=.

U(x)=×+×=

=+.

un
=×+×=

=.

Покажем, что un
и un
+1
– взаимно простые числа. Воспользуемся методом математической индукции.

База индукции.
(u0
, u1
)=1, выполняется.

Индукционное предположение.
Допустим, что (un
-1
, un
)=1.

Шаг индукции.
Докажем, что (un
, un
+1
)=1.

Действительно, если предположить, что (un
+1
, un
)=d>1, то получаем un
+1
∶d и un
∶d, но un
+1
=un
+un
-1
. Два члена последнего равенства делятся на d, а значит, и третий член un
-1
должен делится на d. Следовательно, (un
, un
-1
)=d. Получили противоречие с индукционным предположением. Значит, (un
, un+1
)=1.

Введение в теорию графов

Множество самых разнообразных задач естественно формулируется в терминах точек и связей между ними, то есть в терминах графов.

Первой работой теории графов, как математической дисциплины, считают статью Эйлера (1736 г.), в которой рассматривалась задача о Кенигсбергских мостах. Эйлер показал, что нельзя обойти семь городских мостов и вернуться в исходную точку, пройдя по каждому мосту ровно один раз.

С графами, сами того не замечая, мы сталкиваемся постоянно. Например, графом является схема метрополитена. Точками на ней представлены станции, а линиями – пути движения поездов. Исследуя свою родословную и возводя ее к далекому предку, мы строим так называемое генеалогическое древо. И это древо – граф.

В настоящее время методы теории графов широко применяются при анализе сетей в электротехнике, анализе цепей Маркова в теории вероятностей, в программировании, в проектировании электронных схем, в экономике, социологии, кристаллографии, органической химии и др. науках.

§1. Основные понятия теории графов.

Определение 1.
Пара (V(G), E(G)) называется простым графом
, если V(G) – непустое конечное множество элементов, называемых вершинами
(или узлами, или точками), а E(G) – конечное множество неупорядоченных пар различных элементов из V(G), называемых ребрами
(или линиями).

Иногда V(G) называют множеством вершин, а E(G) – множеством ребер графа G.

#1. V(G)={u, v, w, z},

E(G)={{u, v}, {v, w}, {u, w}, {w, z}}.

Говорят, что ребро {u, v} соединяет вершины u и v.

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

Определение 2.
Общим графом
, или просто графом называется пара (V(G), E(G)) где V(G) – непустое конечное множество элементов, называемых вершинами
, а E(G) – конечное семейство неупорядоченных пар элементов из V(G) (не обязательно различных), называемых ребрами
.

V(G) – множество вершин,

E(G) – семейство ребер.

#2. V(G)={u, v, w, z},

E(G)={{u, v}, {v, v}, {v, v}, {v, w}, {v, w}, {u, w}, {u, w}, {u, w}, {w, z}}.

Определение 3.
Орграфом
(ориентированным графом) D называется пара (V(D), A(D)) где V(D) – непустое конечное множество элементов, называемых вершинами
, а A(D) – конечное семейство упорядоченных пар элементов из V(D), называемых дугами
(или ориентированными ребрами).

Дуга, у которой вершина v является первым элементом, а вершина w – вторым, называется дугой из v в w и обозначается (v, w).

#3.

V(D)={u, v, w, z},

A(D)={(u, v), (v, v), (v, w), (w, v), (w, v), (w, u), (w, z)}.

Определение 4.
Граф называется псевдографом
, если в нем допускаются петли и кратные ребра, то есть две вершины могут быть соединены более чем одним ребром. Псевдограф без петель называется мультиграфом
.

#4.

Псевдограф Мультиграф

§2. Ориентированные и неориентированные графы.

Основные понятия для неориентированных и ориентированных графов удобно вводить «параллельно». Такое изложение позволит наглядно сопоставить соответствующие понятия.

Неориентированные графы	Ориентированные графы
Неориентированный граф G задается двумя множествами G=(V, E), где V – конечное множество, элементы которого называют вершинами или узлами ; E – множество неупорядоченных пар на V, то есть подмножество множества двухэлементных подмножеств V, элементы которого называют ребрами . Для каждого ребра {u, v}ÎE считаем, что u и v – различные вершины.	Ориентированный граф G задается двумя множествами G=(V, E), где V – конечное множество, элементы которого называют вершинами или узлами ; E – множество упорядоченных пар на V, то есть подмножество множества V´V, элементы которого называют дугами .
Если ребро e=(u, v), то говорят, что ребро e соединяет вершины u и v, и обозначают это uv; если необходимо указывают имя графа G: uv	Если дуга e=(u, v), то говорят, что дуга e ведет из вершины u в вершину v, и обозначают это uv; если необходимо указывают имя графа G: uv
Вершины u и v, соединенные ребром (uv), называют смежными , а также концами ребра {u, v}. Если u v, говорят, что вершины u и v связаны отношением непосредственной достижимости .	Вершины u и v такие, что из вершины u в вершину v ведет дуга (uv), называют смежными , причем u называют началом , а v – концом дуги (u, v). Дуга, начало и конец которой есть одна и та же вершина, называется петлей . Если uv, то говорят, что вершины u и v связаны отношением непосредственной достижимости .
Ребро е называется инцидентным вершине v, если она является одним из его концов.	Дугу (u, v) называют заходящей в v и исходящей из вершины u. Дугу называют инцидентной вершине v, если она заходит в v или исходить из нее.
Степенью вершины v называют число dg v всех инцидентных ей ребер (при вычислении степени вершины v петля учитывается два раза, а не один).	Полустепенью захода вершины v называют число dg- (v) заходящих в нее дуг, а полустепенью исхода вершины v – число dg+ (v) исходящих из нее дуг. Степень вершины v, обозначаемая dg(v) – это сумма полустепеней захода и исхода.
Цепь в неориентированном графе G – это последовательность вершин (конечная или бесконечная) v0 , v1 , …, vn , … такая, что vi vi +1 для любого i, если vi +1 существует.	Путь в ориентированном графе G – это последовательность вершин (конечная или бесконечная) v0 , v1 , …, vn , … такая, что vi vi +1 для любого i, если vi +1 существует.
Для конечной цепи v0 , v1 , …, vn число n (n³0) называют длиной цепи . Таким образом, длина цепи ес ть число ее ребер, то есть всех ребер, соединяющих вершины vi и vi +1 (i=). Цепь длины 0 – это произвольная вершина графа.	Для конечного пути v0 , v1 , …, vn число n (n³0) называют длиной пути (n³0). Тем самым длина пути есть число его дуг, то есть всех дуг, которые ведут из вершины vi в вершину vi +1 (i=). Путь длины 0 – это произвольная вершина графа.
Простая цепь – это цепь, все вершины которой, кроме, быть может, первой и последней, попарно различны и все ребра попарно различны.	Простой путь – это путь, все вершины которого, кроме, быть может, первой и последней, попарно различны.
Простая цепь ненулевой длины с совпадающими концами называется циклом .	Простой путь ненулевой длины, начало и конец которого совпадают, называется контуром .
Произвольную цепь ненулевой длины с совпадающими концами, все ребра которой попарно различны, называют замкнутой цепью.	Произвольный путь ненулевой длины, начало и конец которого совпадают, называют замкнутым путем.
Неориентированный граф, не содержащий циклов, называется ациклическим графом .	Ориентированный граф, не содержащий контуров, называется бесконтурным графом .

#5. V={v1
, v2
, v3
, v4
, v5
, v6
, v7
},

E={{v1
, v2
}, {v1
, v3
}, {v2
, v3
}, {v3
, v4
}, {v5
, v6
}}.

v1
, v3
, v4
– простая цепь,

v1
, v3
, v2
, v1
, v3
, v4
– цепь (не простая),

v3
, v1
, v2
, v4
– не цепь.

v1
, v3
, v2
, v1
– цикл,

v4
, v3
, v1
, v2
, v3
, v4
– цепь с совпадающими концами, но не цикл, так как цепь не простая.

dg v1
=dg v2
=2, dg v3
=3, dg v4
=dg v5
=1, dg v7
=0.

#6. V={v1
, v2
, v3
, v4
, v5
, v6
},

E={(v1
, v2
), (v1
, v3
), (v2
, v1
), (v2
, v3
), (v2
, v4
), (v3
, v1
), (v3
, v4
), (v5
, v6
), (v6
, v4
)}.

v1
, v2
, v3
, v4
– простой путь,

v1
, v2
, v3
, v1
, v3
, v4
– путь (не простой),

v3
, v1
, v2
, v3
– контур,

v3
, v1
, v2
, v1
, v3
– замкнутый путь, но не контур,

v1
, v3
, v4
, v6
– не путь.

dg-
(v1
)=dg-
(v3
)=2, dg+
(v1
)=dg+
(v3
)=2, dg(v1
)=dg(v3
)=4;

dg-
(v2
)=1, dg+
(v2
)=3, dg(v2
)=4;

dg-
(v4
)=3, dg+
(v4
)=0, dg(v4
)=3;

dg-
(v5
)=0, dg+
(v5
)=1, dg(v5
)=1;

dg-
(v6
)=1, dg+
(v6
)=1, dg(v6
)=2.

Определение 5.
Вершина степени 0 называется изолированной
, вершина степени 1 называется висячей
(или концевой
).

В #5 вершина v7
– изолированная; а вершины v4
, v5
, v6
– висячие.

Легко видеть, что если сложить степени всех вершин графа, то получится четное число равное удвоенному числу ребер. Этот результат, известный еще 200 лет назад Эйлеру часто называют леммой о рукопожатиях
.

§3. Изоморфизм графов. Подграф. Связные графы.

Определение 6.
Два графа G1
и G2
называются изоморфными
, если существует взаимно однозначное соответствие между множествами их вершин, обладающее тем свойством, что число ребер соединяющих любые две вершины в G1
равно числу ребер, соединяющих соответствующие вершины в G2
.

#7.

v1
«u1
, v2
«u3
, v3
«u5
, v4
«u2
, v5
«u4
, v6
«u6
.

v1
«w1
, v2
«w3
, v3
«w6
,

v4
«w5
, v5
«w4
, v6
«w2
.

Определение 7.
Подграфом
графа G называется граф G1
=(V(G1
), E(G1
)), все вершины которого принадлежат V(G), а все ребра принадлежат E(G), то есть V(G1
)ÍV(G), E(G1
)ÍE(G).

Замечание.
Так как в определении 7 пара G1
=(V(G1
), E(G1
)) является графом, то для любого ребра {u, v}ÎE(G1
) или дуги (u, v)ÎE(G1
) предполагается, конечно, что u, vÎV(G1
).

Если V(G1
)ÌV(G) или E(G1
)ÌE(G), то G1
называют собственным подграфом
графа G, если V(G1
)=V(G), то G1
называют остовным подграфом
графа G.

Определение 8.
Подграф G1
неориентированного (ориентированного) графа G называют подграфом, порожденным множеством вершин
V(G1
)ÍV(G), если каждое ребро (дуга)( тогда и только тогда принадлежит E(G1
)ÍE(G), когда его (ее) концы принадлежат V(G1
).

Отметим, что подграф графа G порожденный множеством вершин V(G1
), в отличие от произвольного подграфа графа G с множеством вершин V(G1
) должен включать все ребра (дуги), концы которых принадлежат множеству V(G1
).

#8. Граф G:

V(G)={u, v, w, z, x},

E(G)={{u, v}, {u, v}, {v, w}, {v, w}, {w, w}, {w, z}, {z, z}, {w, x}, {z, x}}.

Собственный подграф G1
не является порожденным подграфом:

V(G1
)={u, v, w}ÌV(G),

E(G1
)={{u, v}, {v, w}, {w, w}}.

G2
– подграф, порожденный множеством

вершин u, v, w:

V(G2
)={u, v, w}.

E(G2
)={{u, v}, {u, v}, {v, w}, {v, w}, {w, w}}.

Определение 9.
Подграф G1
ÍG называют максимальным подграфом
, если он не является собственным подграфом никакого другого подграфа графа G.

#9. G1
G2
G3
G4
G5

Подграфы G1
, G2
, G3
, G4
являются максимальными ациклическими подграфами графа G5
. Они также являются собственными и основными подграфами.

Следующее важное понятие снова введем параллельно для неориентированных и ориентированных графов.

Неориентированные графы	Ориентированные графы
Неориентированный граф называют связным , если любые две его вершины u и v соединены цепью.	Ориентированный граф называется связным , если для любых двух его вершин u и v вершина v достижима из вершины u или вершина u достижима из вершины v.

Определение 10.
Компонента связности
(или просто компонента
) неориентированного (ориентированного) графа – это его максимальный связный подграф.

В неориентированном графе две вершины, соединенные цепью, связаны отношением достижимости, которое является отношением эквивалентности:

1. Рефлексивность. Вершина u достижима сама с собой, так как существует цепь u.

2. Симметричность. Если вершина v достижима из u, то существует цепь u0
=u, u1
, …, un
=v, но так как граф неориентированный, то отсюда следует, что существует цепь v=un
, un
-1
, …, u1
, u0
=u, то есть вершина u достижима из вершины v.

3. Транзитивность. Пусть v достижима из u и w достижима из v. следовательно, существует цепь u=u0
, u1
, u2
, …, un
=v и существует цепь v=v0
, v1
, v2
, …, vm
=w. Но тогда существует цепь u0
=u, u1
, …, un
=v=v0
, v1
, v2
, …, vm
=w, то есть w достижима из u.

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

В ориентированном графе отношение достижимости не является отношением эквивалентности (не всегда выполняется симметричность) и поэтому компоненты ориентированного графа могут пересекаться.

#10.

Граф G не связный.

Он состоит из трех компонент.

В примере 9 все графы связные.

¬Этот граф связный.

Не связный, так как вершина v2
и v5
не достижимы друг из друга. ®

Определение 11.
Ориентированный граф называется сильно связным
, если для любых двух его вершин u и v вершина v достижима из u и вершина u достижима из v (u и v взаимно достижимы). Бикомпонента
ориентированного графа – это его максимальный сильно связный подграф.

#11.

Граф G не связный. Бикомпонентой является подграф G1
, порожденный множеством вершин {v1, v2, v3}.

G1
– сильно связный, ведь:

v1
достижима из v2
;

v1
достижима из v3
;

v2
достижима из v1
;

v2
достижима из v3
(v3
, v1
, v2
);

v3
достижима из v1
;

v3
достижима из v2
.

Подграф G1
является максимальным сильно связным. Вершины v4
и v5
уже ни с одной из вершин v1
, v2
, v3
не взаимно достижимы.

Определение 12.
Граф, у которого множество ребер пусто E(G)=Æ, называется вполне несвязным
(или пустым
)графом.

#12.

Определение 13.
Простой граф, в котором любые две вершины смежны, называется полным
графом. Обозначается Кn
, где n – число вершин.

#13.

Определение 14.
Граф, у которого все вершины имеют одну и ту же степень, называется регулярным
. Если степень каждой вершины равна r, то граф называется регулярным степени
r
. Регулярные графы степени 3, называются кубическими
(или трехвалентными
).

#14.

¬ Кубический граф

Полный регулярный граф степени 5 ®

§4. Способы представления графов.

Наиболее известный и популярный способ представления графов состоит в геометрическом изображении точек (вершин) и линий (ребер). При численном решении задач на вычислительных машинах граф должен быть представлен дискретным способом. Представим несколько таких способов.

Определение 15.
Матрицей смежности
ориентированного графа с n вершинами называется матрица A=(aij
), i, j=1, 2, …, n, в которой .

Для неориентированного графа матрица смежности определяется следующим образом:

Матрица смежности однозначно определяет структуру графа. Петля в матрице смежности может быть представлена соответствующим единичным диагональным элементом. Кратные ребра можно представить, позволив элементу матрицы быть больше 1.

#15. Для ориентированного графа:

Для соответствующего неориентированного графа:

Заметим, что в А в i-ой строке количество единиц равно полустепени исхода dg+
vi
, а количество единиц в i-ом столбце – полустепени захода dg-
vi
.

Для неориентированного графа матрица смежности вершин всегда симметрическая и сумма чисел в любой строке или столбце равна степени соответствующей вершины (здесь петля учитывается 1 раз).

Определение 16.
Матрицей инцидентности
графа с n вершинами и m ребрами называется матрица В=(bij
), i=, j=, строки которой соответствуют вершинам, а столбцы – ребрам. Элементы матрицы равны для неориентированного графа:

Для ориентированного графа:

#16.

Строки соответствуют вершинам, расположенным по порядку, а столбцы – дугам в таком порядке: (1,2), (1,3), (2,1), (2,3), (2,4), (2,5), (2,7), (3,5), (4,1), (4,5), (4,7), (6,4), (6,5), (6,7), (7,4), (7,5).

В=

§5. Число ребер простого графа. Разрезы.

Теорема 1.
Пусть G – простой граф с n вершинами и k компонентами связности. Тогда число m его ребер удовлетворяет неравенствам

.

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

База индукции.
Если G вполне несвязный граф, то утверждение верно.

Индукционное предположение.
Предположим, что утверждение верно для количества ребер меньше m.

Шаг индукции.
Если в графе G число ребер минимально (скажем m0
), то удаление любого ребра должно привести к увеличению числа компонент на 1. Таким образом, в получившемся графе будет n вершин, k+1 – компонент и m0
-1 – ребер. Следовательно, в силу индуктивного предположения получается: m0
-1³n-(k+1) Þm0
³n-k. Утверждение верно.

Для доказательства оценки сверху можно считать каждую компоненту графа G полным графом. Предположим, что Ci
и Cj
– две компоненты соответственно с ni
и nj
вершинами и ni
³nj
>1. Если мы заменим Сi
и Cj
на полные графы с ni
+1 и nj
-1 вершинами, то общее число вершин не изменится, а число ребер увеличится на положительную величину равную ni
-nj
+1. Следовательно, для того, чтобы число ребер в графе G было максимально возможным (при заданных n и k), G должен состоять из k-1 изолированных вершин и полного графа с n-k+1 вершинами. Тогда количество ребер будет . Отсюда следует нужное неравенство. ■

Следствие 1.1.
Любой простой граф с n вершинами и более чем ребрами связен.

Определение 17.
Разделяющим множеством
связного графа G называется такое множество его ребер, удаление которого приводит к несвязному графу.

#17. Для данного графа разделяющими множествами будут

S1
={e1
, e2
, e4
}

S2
={e3
, e5
, e6
, e7
}

Определение 18.
Разрезом
называется такое разделяющее множество, никакое собственное подмножество которого не является разделяющим.

#18. В примере 17 S1
не является разрезом. S2
– разрез.

Определение 19.
Если разрез состоит из единственного ребра е, то е называется мостом
или перешейком
.

#19.

е – мост

Все вышеприведенные определения легко переносятся на несвязные графы:

В произвольном графе Gразделяющим множеством
называется такое множество ребер, удаление которого увеличивает число компонент в G. Разрезом
в G называется разделяющее множество, никакое собственное подмножество которого не является разделяющим. Заметим, что в результате удаления ребер, принадлежащих разрезу, число компонент в G увеличивается ровно на единицу.

§6. Эйлеровы графы.

Определение 20.
Связный граф G называется эйлеровым
, если существует замкнутая цепь, проходящая через каждое его ребро. Такая цепь называется эйлеровой цепью
.

Отметим, что в этом определении требуется, чтобы каждое ребро проходилось только один раз. Если снять ограничение на замкнутость цепи, то граф называется полуэйлеровым
. При этом каждый эйлеров граф будет полуэйлеровым.

#20.

Не эйлеров граф Полуэйлеров граф Эйлеров граф

Лемма 1.
Если степень каждой вершины графа G не меньше двух, то граф G содержит цикл.

Доказательство.
Если в графе G имеются петли или кратные ребра, то утверждение очевидно; поэтому предположим, что G является простым графом. Пусть v – произвольная вершина графа G; построим по индукции маршрут v®v1
®v2
®…, выбирая вершину v1
смежной вершине v, а для i³1 – выбирая vi
+1
смежной vi
и отличной от vi
-1
(существование такой вершины vi
+1
гарантировано условием леммы). Так как G имеет конечное число вершин, то в конце концов мы придем к вершине, которая была уже выбрана ранее.

Предположим, что vk
– первая такая вершина; тогда часть маршрута лежащая между двумя вхождениями vk
и является требуемым циклом.

Теорема Эйлера 2.
Связный граф G является эйлеровым тогда и только тогда, когда каждая вершина в G имеет четная степень.

Доказательство.
Необходимость.
Пусть связный граф G является эйлеровым. Это значит, что существует эйлерова цепь x1
u1
x2
u2
…xn
un
x1
, где xi
ÎV(G) (множество вершин) ui
ÎE(G) (множество ребер), в которой все ребра содержатся по одному разу. Такая цепь включает в себя все вершины графа G. каждая тройка цепи ui
-1
xi
ui
приносит вершине xi
степень 2, а так как все ребра в цепи различные, то степени внутренних вершин четные.

Рассмотрим вершину x1
: в начале цепи ребро u1
ей приносит степень 1, если эта вершина встречается внутри цепи, то степень ее увеличивается на 2 при каждом повторе; и в конце цепи ребро un
приносит ей степень 1. Всего, если посчитать, степень вершины х1
будет четной.

Достаточность.
Пусть каждая вершина графа G имеет четную степень. Построим эйлерову цепь. Пусть х1
ÎV(G) – произвольная вершина. Из нее будем строить цепь, выбирая в качестве продолжения пути ребро, которое еще не пройдено. Эта цепь может закончится только в вершине х1
, так как при входе в любую другую вершину, всегда существует ребро, по которому можно из нее выйти (степени вершин четные).

Возможны два случая: 1) построенный цикл содержит все ребра графа G и тогда теорема доказана; 2) построенный цикл содержит не все ребра графа G. Тогда рассмотрим граф G1
, полученный из G удалением всех ребер, входящих в построенный цикл. Граф G1
вновь содержит вершины только с четными степенями (так как у каждой вершины удалили по четному числу ребер). Так как G – связный граф, то в построенном цикле существует вершина инцидентная ребру графа G1
. Пусть это вершина xk
ÎV(G). Построим из нее второй цикл так же, как строили предыдущий. Далее построим общий цикл, который получится из первого цикла, если включить в него второй цикл как составную часть.

#

dg 1=dg 2=dg 3=2,

dg 4=dg 5=4,

dg 6=6.

Пусть х1
=1.

Построим первый цикл следующим образом: 1е1
2е3
6е11
5е12
6е4
2е2
1.

Выбираем вершину графа G инцидентную какому-либо не пройденному ребру такую, чтобы эта вершина была в первом цикле. Это возможно, так как граф G связный.

Пусть х2
=6. Второй цикл: 6е5
3е6
4е7
1е8
5е9
4е10
6.

Теперь объединяем первый и второй циклы вместе, вставляя второй цикл внутрь первого, там, где стоит вершина 6.

Если после двух циклов еще остаются не пройденные ребра, повторяем аналогичный процесс. Так как количество ребер конечно, то на каком-то шаге процесс завершится и в итоге мы получим эйлерову цепь и, значит, G - эйлеров граф. ■

Следствие 2.1.
Связный граф является эйлеровым тогда и только тогда, когда семейство его ребер можно разбить на непересекающиеся циклы.

Следствие 2.2.
Связный граф является полуэйлеровым тогда и только тогда, когда в нем не более двух вершин имеют нечетные степени.

Заметим, что если Полуэйлеров граф содержит ровно две вершины с нечетными степенями, то в любой полуэйлеровой цепи одна из этих вершин обязательно будет начальной, а другая – конечной. По лемме о рукопожатиях граф не может иметь только одну вершину нечетной степени.

Теорема 3 (алгоритм Флёри).
Пусть G – эйлеров граф, тогда следующая процедура всегда возможна и приводит к эйлеровой цепи графа G. Выходя из произвольной вершины, идем по ребрам графа произвольным образом, соблюдая лишь следующие правила:

1)
стираем ребра по мере их прохождения. И стираем также изолированные вершины, которые при этом образуются;

2)
на каждом этапе идем по мосту только тогда, когда нет других возможностей.

# С помощью алгоритма Флёри найти эйлерову цепь в следующем графе

§7. Гамильтоновы графы.

В предыдущем пункте мы рассмотрели замкнутые цепи, проходящие через каждое ребро заданного связного графа G. Можно рассмотреть аналогично, замкнутую цепь, проходящую ровно один раз через каждую вершину графа G.

Ясно, что такая цепь должна быть циклом, если такой цикл существует, то он называется гамильтоновым циклом
, а граф G называется гамильтоновым графом
. Граф, который содержит простую цепь, проходящую через каждую его вершину, называется полугамильтоновым
. Заметим, что всякий гамильтоновый граф является полугамильтоновым.

#

Не гамильтоновый Гамильтоновый Полугамильтоновый

граф граф граф

В теореме Эйлера приведено необходимое и достаточное условие для того, чтобы связный граф был эйлеровым. Однако, для гамильтоновых графов аналогичная задача до сих пор является нерешенной.

Теорема 4 (Дирарк, 1952).
Если в простом графе G с n (³3) вершинами степень любой вершины vρ(v)³, то граф G является гамильтоновым.

§8. Деревья.

Определение 21.
Связный неориентированный ациклический граф G называется деревом
, множество деревьев называется лесом
. Ориентированным деревом
называется бесконтурный ориентированный граф, у которой полустепень захода любой вершины не более 1 и существует ровно одна вершина, называемая корнем ориентированного дерева
, полустепень захода которой равна 0.

#21. На данном рисунке изображено ориентированное дерево. v0
– корень ориентированного дерева.

Неориентированный лес ®

¬ Ориентированный лес

Определение 22.
Основным деревом
связного графа G называется дерево, являющееся основным подграфом графа G, то есть это дерево, содержащее все вершины графа G.

#22.

¬ Связный граф G

Остовные деревья

графа G®

Определение 23.
Вершину v ориентированного дерева называют потомком
(подлинным потомком
) вершины u, если существует путь из u в v (путь ненулевой длины). В этом случае u называют предком
(подлинным предком
) вершины v, а если длина пути из u в v равна 1, то вершину v называют сыном
вершины u, которая при этом именуется отцом
вершины v. Вершину, не имеющую потомков, называют листом
.

#23.

v4
, v5
– сыновья вершины v2
, которая в свою очередь является сыном v0
- корня дерева.

Вершины v4
и v5
являются подлинными потомками вершин v0
и v2
, которые будут их подлинными предками.

v1
, v4
, v5
, v6
, v8
, v9
– листья.

Определение 2
4
.
Ориентированное дерево, у которого каждая вершина отличная от корня, есть лист, называют кустом
.

#24.

Куст

§9. Двудольные графы.

Определение 25.
Граф G=(V, E) называется двудольным
, если множество его вершин можно разбить на два независимых подмножества V1
и V2
так, что V=V1
ÈV2
и V1
ÇV2
=Æ. Если каждая вершина из V1
соединена с каждой вершиной из V2
, то G называется полным двудольным графом
и обозначается Km
,
n
, где m – число вершин в V1
, а n – число вершин в V2
. полный двудольный граф вида K1,
n
, называется звездным графом
.

#25.

¬ Двудольный граф

Полный двудольный граф ®

¬ Звездный граф

Теорема 5.
Граф G=(V, E) является двудольным тогда и только тогда, когда любой его простой цикл четной длины.

Доказательство.
Необходимость.
Ясно, что для двудольного графа любой цикл будет иметь четную длину.

Достаточность.
Пусть у графа G каждый цикл имеет четную длину. разобьем граф G на компоненты связности G1
, G2
, …, Gm
. Пусть Gk
=(Vk
, Ek
) и пусть аÎVk
– произвольная вершина Gk
. Далее разобьем множество вершин Vk
на непересекающиеся множества Vk
1
и Vk
2
, где Vk
1
– вершины, расстояние до которых от а нечетно, Vk
2
– вершины, расстояние до которых от а четно. Получаем, что аÎVk
2
. Множества Vk
1
и Vk
2
являются незавиДимыми. действительно, если предположить, что вершины b и c смежные и принадлежат одновременно одному из множеств Vk
1
или Vk
2
, то существовал бы цикл нечетной длины:

1) Предположим, что b, cÎVk
1
.

от a к b – нечетная длина,

от b к с – длина 1,

от с к а – нечетная длина.

Нечетная длина

2) Предположим, что b, cÎVk
2
.

от a к b – четная длина,

от b к с – длина 1,

от с к а – четная длина.

Нечетная длина

Итак, это противоречит условию теоремы.

Рассмотренное разбиение вершин выполним для каждой компоненты G1
, G2
, …, Gm
связности. И когда объединим независимые компоненты Vk
1
и Vk
2
для всех разбиений, то получим разбиение множества всех вершин исходного графа G на два независимых подмножества V1
= и V2
=. Таким образом, G – двудольный граф. ■

Определение 26.
Паросочетанием
в двудольном графе G=(V1
ÈV2
, E) называется независимое подмножество ребер πÍE, ребра π не имеют общих вершин.

#26.

π1
={{1,a}, {2,b}}

π2
={{3,a}, {2,b}}

π1
, π2
– паросочетания.

Паросочетание называется максимальным
, если любое другое паросочетание содержит меньшее количество ребер.

Задача.
Дан двудольный граф G=(V1
ÈV2
, E), где V1
={1, 2, 3, 4, 5, 6}, V2
={a, b, c, d, e, f}. Соединение вершин задано соотношениями: 1®{d}, 2®{a, f}, 3®{d, e, f}, 4®{a, c}, 5®{b}, 6®{a, c}. Найти максимальное паросочетание.

Решение.
выберем начальное паросочетание π таким образом, что вершина jÎV1
соединим с вершиной xÎV2
первой незанятой ранее из списка соединений для j.

Исходное паросочетание π={{1,d}, {2,a}, {3,e}, {4,c}, {5,b}}, |π|=5.

Вершины 6 и f не вошли в паросочетание. Попытаемся увеличить π. Будем обозначать переход по ребрам графа из V1
в V2
; а - переход по ребрам паросочетания из V2
в V1
.

Так 6{a, c} (из 6ÎV1
можно попасть в V2
, перейдя в вершины либо а, либо с).

{a, c}{2, 4}, то есть из вершин а и с можно достичь по ребрам паросочетания вершин 2 и 4.

Строим чередующиеся цепи:

6{a, c}{2, 4}{a, b, f}.

Переходы следует закончить, если вершина f достигнута или подмножество вершин из V2
, доступных из 6, повторилось. Во втором случае это означает, что вершина f недоступна из 6 и, следовательно, исходное паросочетание было бы максимальным. В нашем случае f доступна. Строим обратную чередующуюся цепь: f2a6.

Теперь новое паросочетание строим из старого исключая из него ребро {2, a} и включая ребра {f, 2} и {a, 6}.

Итак, максимальное паросочетание: π={{1,d}, {2,f}, {3,e}, {4,c}, {5,b}, {6, a}}, |π|=6.

Описанный в примере алгоритм построения максимального паросочетания называется алгоритмом чередующихся цепей.

§10. Укладка графов.

Для представления графов мы пользовались диаграммами, на которых точки изображали вершины, а отрезки – ребра. Такие диаграммы очень удобны при исследовании свойств отдельных графов. Было бы хорошо, если бы мы имели возможность изображать графы в некотором пространстве так, чтобы они не имели «пересечений».

#27. Граф K4
можно представить на плоскости с пересечением и без пересечений.

Определение 27.
Жордановой кривой
на плоскости называется непрерывная кривая, не имеющая самопересечений; замкнутой жордановой кривой
называется жорданова кривая, начало и конец которой совпадают.

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

Теорема 6.
Каждый граф может быть уложен в трехмерном евклидовом пространстве.

Доказательство.
Построим укладку в явном виде. Сначала поместим вершины графа в различные точки на оси абсцисс, затем для каждого ребра выберем плоскость, проходящую через ось абсцисс таким образом, что различные ребра графа соответствуют различным плоскостям. (Это всегда можно сделать в силу конечности множества ребер).

Требуемая укладка получается следующим образом: для каждой петли графа рисуем в соответствующей плоскости окружность, проходящую через соответствующую вершину; для каждого ребра, соединяющие две различные вершины, рисуем в соответствующей плоскости полуокружность, проходящую через эти две вершины. Ясно, никакие их этих кривых не могут пересекаться, так как они лежат в различных плоскостях. Отсюда вытекает нужный результат. ■

§11. Планарные и плоские графы. Теорема Эйлера о плоских графах.

Определение 29.
Плоским графом
называется граф, изображенный на плоскости так, что никакие два его ребра (или представляющие их кривые) геометрически не пересекаются нигде, кроме как в инцидентной им обоим вершине. Граф, изоморфный плоскому графу, называется планарным
. Иначе можно сказать, что граф планарен, если его можно уложить на плоскость.

#28.

Все три графа планарны, но только второй и третий являются плоскими.

Определение 30.
Пусть граф G уложен в некотором пространстве; точка х этого пространства называется дизъюнктной с
G
, если она не соответствует ни одной вершине графа G и не лежит ни на каком его ребре.

Определение 31.
Если точка х плоскости дизъюнктна с G, то определим грань графа
G
, содержащую х
, как множество всех таких точек плоскости, которые можно соединить с х жордановыми кривыми, состоящими из точек, дизъюнктных с G. Отметим, что у графа одна грань неограниченна; она называется бесконечной гранью
.

#29. У данного графа 4 грани.

f4
– бесконечная грань.

Теорема 7 (Эйлер, 1752).
Пусть G – связный плоский граф, пусть n, m и f обозначают соответственно число вершин, ребер и граней графа G. Тогда n+f=m+2.

Доказательство.
Доказательство проводим индукцией по числу ребер в G. Если m=0, то n=1 (так как G связен) и f=1 (бесконечная грань); в этом случае теорема верна.

Предположим теперь, что теорема верна для любого графа G, имеющего m-1 ребер, и добавим к G новое ребро е. Тогда либо 1) е является петлей и, в этом случае возникает новая грань, а число вершин остается неизменным; либо 2) е соединяет две различные вершины из G, и в этом случае одна из граней графа G расщепляется на две увеличивая число граней на 1, но оставляя число вершин неизменным; либо 3) е инцидентно только одной вершине в G, и в этом случае необходимо добавить еще одну вершину, увеличивая тем самым число вершин на 1, но оставляя число граней неизменным. Теорема остается справедливой в каждом из трех случаев. Других случаев нет. ■

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

Следствие 1.
Если G – граф многогранника, то n+f=m+2, где n – число вершин, m – число ребер, f – число граней.

Теорему Эйлера легко перевести на несвязные графы:

Следствие 2.
Пусть G – плоский граф с n вершинами, m ребрами, f гранями и k компонентами, тогда n+f=m+k+1.

Следствие 3.
Если G – связный простой планарный граф с n(³3) вершинами и m ребрами, то m£3n-6.

Доказательство.
Так как каждая грань ограничена по крайней мере тремя ребрами, то при подсчете числа ребер вокруг каждой из граней получим, что 3f£2m (множитель 2 появляется оттого, что каждое ребро ограничивает не более двух граней). Используя это неравенство в теореме Эйлера, получаем требуемый результат. ■

Следствие 4.
Графы К5
и К3,3
не являются планарными.

Доказательство.
Если К5
планарен, то применяя следствие 3, получим 10£9. Получили противоречие.

Чтобы показать, что К3,3
не планарен, достаточно заметить, что каждая его грань ограничена по крайней мере четырьмя ребрами и следовательно, 4f£2m (то есть 2f£9). Но этого не может быть, поскольку теорема Эйлера утверждает, что f=5. ■

Следствие 5.
В любом простом планарном графе существует вершина, степень которой не больше 5.

§12. Раскрашивание графов.

Определение 32.
Пусть граф G не имеет петель; тогда G называется k
-раскрашиваемым
, если каждой его вершине можно приписать один из k цветов таким образом, чтобы никакие две смежные вершины не оказались одного цвета. Если граф G является k-раскрашиваемым, но не является (k-1)-раскрашиваемым, то назовем его k
-хроматичным
, а число k назовем хроматичным числом графа
G
и обозначим через χ(G).

Теорема 8. (о пяти красках).
Каждый планарный граф 5-раскрашиваем.

Без доказательства.

Уже сто лет математики пытаются доказать знаменитую нерешенную проблему теории графов – гипотезу четырех красок.

Гипотеза 4 красок.
Всякий планарный граф 4-раскрашиваем.

При попытках доказательства этой гипотезы были получены некоторые интересные результаты:

1) если гипотеза четырех красок не верна, то любой опровергающий пример будет очень сложным; известно, например, что всякий планарный граф, имеющий менее 52 вершин 4-раскрашиваем;

2) любой, не содержащий треугольников, планарный граф 3-раскрашиваем (теорема Грёча);

3) если доказывать гипотезу четырех красок, то достаточно доказать ее для гамильтоновых графов (результат Уитни).

Литература

1.
Акимов О.Е. Дискретная математика. Логика, группы, графы. – М.: Лаборатория базовых знаний, 2001.

2.
Иванов Б.Н. Дискретная математика. Алгоритмы и программы. – М.: Лаборатория базовых знаний, 2002.

3.
Новиков Ф.А. Дискретная математика для программистов. – Издательство: Питер, 2003.

4.
Виленкин Н.Я. Комбинаторика. – М.: Наука, 1969.

5.
Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики. – М.: Наука, 1992.