Гипероглавление:
Введение
Комбинаторика
§1. Правила суммы и прямого произведения.
§2.Размещения с повторениями.
§3. Размещения без повторений.
§4. Перестановки.
§5. Сочетания.
§6. Сочетания с повторениями.
§7. Перестановки с повторениями. Мультимножества.
§8. Полиномиальная формула.
Методы подсчета и оценивания.
§1. Производящие функции.
§2. Линейные операции.
§3. Сдвиг начала вправо.
§4. Сдвиг начала влево.
§5. Частичные суммы.
§6. Дополнительные частичные суммы.
§7. Изменение масштаба
§8. Свертка.
§9. Линейные рекуррентные соотношения.
§10. Неоднородные линейные рекуррентные соотношения.
§11. Числа Фибоначчи.
Введение в теорию графов
§1. Основные понятия теории графов.
§2. Ориентированные и неориентированные графы.
§3. Изоморфизм графов. Подграф. Связные графы.
§4. Способы представления графов.
§5. Число ребер простого графа. Разрезы.
§6. Эйлеровы графы.
§7. Гамильтоновы графы.
§8. Деревья.
§9. Двудольные графы.
§10. Укладка графов.
§11. Планарные и плоские графы. Теорема Эйлера о плоских графах.
§12. Раскрашивание графов.
Литература
--PAGE_BREAK-- продолжение
--PAGE_BREAK--§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.
продолжение
--PAGE_BREAK--§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
продолжение
--PAGE_BREAK--§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≥
ak=k+1, k≥
a0=0, ak=, k≥1
a0=0, ak=, k≥1
ak=, k≥
ak=, k≥0, r – любое
ak=, k≥1, r – любое
ak=, k≥, r – любое
Простейшие производящие функции будем использовать для получения производящих функций более сложных последовательностей. С этой целью рассмотрим наиболее важные из операций над производящими функциями, то есть способы получения новых производящих функций и соответствующих им последовательностей. Обозначим через {ak}, {bk}, {ck} последовательности, а соответствующие им производящие функции как А(х), В(х), С(х).
продолжение
--PAGE_BREAK--§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, …. Тогда, В(х)=хiA(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+…)+a1x(1+x+x2+x3+…)+ a2x2(1+x+x2+x3+…)+…= =(a0+a1x+a2x2+…)(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)+…=
.
продолжение
--PAGE_BREAK--§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=С1un+r-1+С2un+r-2+…+Сrun, (1)
где Сi, i= – постоянные величины. Выражение (1) позволяет вычислить очередной член последовательности по предыдущим rчленам. Ясно, что, задав начальные значения u, u1, …, ur-1, можно последовательно определить все члены последовательности.
Рассмотрим общий метод решения рекуррентного соотношения (1), то есть поиска un, как функции от n. для решения задачи достаточно найти производящую функцию
U(x)= (2)
последовательности {un}. Введем обозначение:
К(х)=1-С1х-С2х2-…-Сrxr
и рассмотрим произведение U(x)K(x)=C(x), deg C(x)£r-1, так как коэффициенты при xn+r, n=0,1,2… в произведении U(x)K(x) с учетом (1), равны:
un+r-(С1un+r-1+С2un+r-2+...+Сrun)=0.
Характеристическим полиномом соотношения (1) называется многочлен
F(x)=xr-С1xr-1-С2xr-2-…-Сr-1x-С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, если u=u1=1.
Решение.Начальные условия: r=2, C1=5, C2=-6.
K(x)=1-5x+6x2
K(x)⋅U(x)=С(x), где U(x)=
С(х)=(1-5x+6x2)(u0+u1x+u2x2+…)=
=u0+u1x+u2x2+…-5ux-5u1x2-5u2x3-…+6ux2+6u1x3+6u2x4+…=
=u0+(u1-5u0)x+(u2-5u1+6u0)x2+(u3-5u2+6u1)x3+…
Но u2=5u1-6u, u3=5u2-6u1и так далее. Следовательно,
С(х)=u+(u1-5u0)x=1-4x.
Характеристическим полиномом будет F(x)=x2-5x+6=(x-2)(x-3).
Отсюда следует, что U(x)==.
С помощью неопределенных коэффициентов разложим последнюю дробь в сумму дробей:
===.
Следовательно, Þ .
Тогда U(x)=, но =, и таким образом, и .
Итак, U(x)===.
Получаем, что uk=2k+1-3k.
продолжение
--PAGE_BREAK--§10. Неоднородные линейные рекуррентные соотношения.
Неоднородное линейное рекуррентное соотношение имеет вид:
un+r=С1un+r-1+С2un+r-2+…+Сrun+bn (1)
где величина bnв общем случае является функцией от n. Общее решение соотношения (1) представляет собой сумму частного решения неоднородного уравнения (1) (то есть любого решения, которое ему удовлетворяет) и общего решения соответствующего ему однородного соотношения (1).
Общих способов определения частного решения нет, однако для некоторых значений bnсуществуют стандартные приемы определения un.
Пример. Найти {un}, если un+1=un+(n+1) и u0=1.
Решение. Умножив левую и правую части рекуррентного соотношения на хn, получим:
un+1xn=unxn+(n+1)xn.
Суммирование последнего уравнения для всех nдает:
.
Воспользуемся свойствами операций с производящими функциями:
=U(x) – по определению,
====,
= – см. табл. §9.
Итак, получаем =U(x)+.
Учитывая, что u=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, u=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)= Þ
Итак, .
продолжение
--PAGE_BREAK--§11. Числа Фибоначчи.
Последовательность Фибоначчи задается рекуррентным соотношением un+2=un+1+un, u=1, u1=1. То есть 1, 1, 2, 3, 5, 8, 13, 21, …. Найдем un.
K(x)=1-x-x2
U(x)=
С(x)=K(x)×U(x)=u+u1x+u2x2+…-ux-u1x2-u2x3-…-ux2-u1x3-u2x4-…=
=u0+u1x-u0x=1+x-x=1
F(x)=x2-x-1=
K(x)=
U(x)==
.
Þ Þ
Þ B=, A=1-B=.
U(x)=×+×=
=+.
un=×+×=
=.
Покажем, что unи un+1– взаимно простые числа. Воспользуемся методом математической индукции.
База индукции. (u, 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.
продолжение
--PAGE_BREAK--Введение в теорию графов
Множество самых разнообразных задач естественно формулируется в терминах точек и связей между ними, то есть в терминах графов.
Первой работой теории графов, как математической дисциплины, считают статью Эйлера (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.
Псевдограф Мультиграф
продолжение
--PAGE_BREAK--§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, и обозначают это u v; если необходимо указывают имя графа G: u v
Если дуга e=(u, v), то говорят, что дуга eведет из вершины uв вершину v, и обозначают это uv; если необходимо указывают имя графа G: uv
Вершины uи v, соединенные ребром (u v), называют смежными, а также концами ребра {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– это последовательность вершин (конечная или бесконечная) v, v1, …, vn, … такая, что vi vi+1для любого i, если vi+1существует.
Путьв ориентированном графе G– это последовательность вершин (конечная или бесконечная) v, v1, …, vn, … такая, что vi vi+1для любого i, если vi+1существует.
Для конечной цепи v, v1, …, vnчисло n(n³0) называют длиной цепи. Таким образом, длина цепи есть число ее ребер, то есть всех ребер, соединяющих вершины viи vi+1(i=). Цепь длины 0 – это произвольная вершина графа.
Для конечного пути v, 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 лет назад Эйлеру часто называют леммой о рукопожатиях.
продолжение
--PAGE_BREAK--§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, то существует цепь u=u, u1, …, un=v, но так как граф неориентированный, то отсюда следует, что существует цепь v=un, un-1, …, u1, u=u, то есть вершина uдостижима из вершины v.
3. Транзитивность. Пусть vдостижима из uи wдостижима из v. следовательно, существует цепь u=u, u1, u2, …, un=vи существует цепь v=v, v1, v2, …, vm=w. Но тогда существует цепь u=u, u1, …, un=v=v, 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 ®
продолжение
--PAGE_BREAK--§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число ребер минимально (скажем m), то удаление любого ребра должно привести к увеличению числа компонент на 1. Таким образом, в получившемся графе будет nвершин, k+1 – компонент и m-1 – ребер. Следовательно, в силу индуктивного предположения получается: m-1³n-(k+1) Þ m³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увеличивается ровно на единицу.
продолжение
--PAGE_BREAK--§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является эйлеровым. Это значит, что существует эйлерова цепь x1u1x2u2…xnunx1, где xiÎV(G) (множество вершин) uiÎE(G) (множество ребер), в которой все ребра содержатся по одному разу. Такая цепь включает в себя все вершины графа G. каждая тройка цепи ui-1xiuiприносит вершине 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е12е36е115е126е42е21.
Выбираем вершину графа Gинцидентную какому-либо не пройденному ребру такую, чтобы эта вершина была в первом цикле. Это возможно, так как граф Gсвязный.
Пусть х2=6. Второй цикл: 6е53е64е71е85е94е106.
Теперь объединяем первый и второй циклы вместе, вставляя второй цикл внутрь первого, там, где стоит вершина 6.
Если после двух циклов еще остаются не пройденные ребра, повторяем аналогичный процесс. Так как количество ребер конечно, то на каком-то шаге процесс завершится и в итоге мы получим эйлерову цепь и, значит, G— эйлеров граф. ■
Следствие 2.1.Связный граф является эйлеровым тогда и только тогда, когда семейство его ребер можно разбить на непересекающиеся циклы.
Следствие 2.2.Связный граф является полуэйлеровым тогда и только тогда, когда в нем не более двух вершин имеют нечетные степени.
Заметим, что если Полуэйлеров граф содержит ровно две вершины с нечетными степенями, то в любой полуэйлеровой цепи одна из этих вершин обязательно будет начальной, а другая – конечной. По лемме о рукопожатиях граф не может иметь только одну вершину нечетной степени.
Теорема 3 (алгоритм Флёри).Пусть G– эйлеров граф, тогда следующая процедура всегда возможна и приводит к эйлеровой цепи графа G. Выходя из произвольной вершины, идем по ребрам графа произвольным образом, соблюдая лишь следующие правила:
1) стираем ребра по мере их прохождения. И стираем также изолированные вершины, которые при этом образуются;
2) на каждом этапе идем по мосту только тогда, когда нет других возможностей.
# С помощью алгоритма Флёри найти эйлерову цепь в следующем графе
продолжение
--PAGE_BREAK--§7. Гамильтоновы графы.
В предыдущем пункте мы рассмотрели замкнутые цепи, проходящие через каждое ребро заданного связного графа G. Можно рассмотреть аналогично, замкнутую цепь, проходящую ровно один раз через каждую вершину графа G.
Ясно, что такая цепь должна быть циклом, если такой цикл существует, то он называется гамильтоновым циклом, а граф Gназывается гамильтоновым графом. Граф, который содержит простую цепь, проходящую через каждую его вершину, называется полугамильтоновым. Заметим, что всякий гамильтоновый граф является полугамильтоновым.
#
Не гамильтоновый Гамильтоновый Полугамильтоновый
граф граф граф
В теореме Эйлера приведено необходимое и достаточное условие для того, чтобы связный граф был эйлеровым. Однако, для гамильтоновых графов аналогичная задача до сих пор является нерешенной.
Теорема 4 (Дирарк, 1952).Если в простом графе Gс n(³3) вершинами степень любой вершины vρ(v)³, то граф Gявляется гамильтоновым.
§8. Деревья.
Определение 21.Связный неориентированный ациклический граф Gназывается деревом, множество деревьев называется лесом. Ориентированным деревом называется бесконтурный ориентированный граф, у которой полустепень захода любой вершины не более 1 и существует ровно одна вершина, называемая корнем ориентированного дерева, полустепень захода которой равна 0.
#21. На данном рисунке изображено ориентированное дерево. v– корень ориентированного дерева.
Неориентированный лес ®
¬ Ориентированный лес
Определение 22.Основным деревом связного графа Gназывается дерево, являющееся основным подграфом графа G, то есть это дерево, содержащее все вершины графа G.
#22.
¬ Связный граф G
Остовные деревья
графа G ®
Определение 23.Вершину vориентированного дерева называют потомком (подлинным потомком) вершины u, если существует путь из uв v(путь ненулевой длины). В этом случае uназывают предком (подлинным предком) вершины v, а если длина пути из uв vравна 1, то вершину vназывают сыном вершины u, которая при этом именуется отцом вершины v. Вершину, не имеющую потомков, называют листом.
#23.
v4, v5– сыновья вершины v2, которая в свою очередь является сыном v— корня дерева.
Вершины v4и v5являются подлинными потомками вершин vи v2, которые будут их подлинными предками.
v1, v4, v5, v6, v8, v9– листья.
Определение 2
4
.Ориентированное дерево, у которого каждая вершина отличная от корня, есть лист, называют кустом.
#24.
Куст
продолжение
--PAGE_BREAK--§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на непересекающиеся множества Vk1и Vk2, где Vk1– вершины, расстояние до которых от а нечетно, Vk2– вершины, расстояние до которых от а четно. Получаем, что аÎVk2. Множества Vk1и Vk2являются незавиДимыми. действительно, если предположить, что вершины bи cсмежные и принадлежат одновременно одному из множеств Vk1или Vk2, то существовал бы цикл нечетной длины:
1) Предположим, что b, cÎVk1.
от aк b– нечетная длина,
от bк с – длина 1,
Нечетная длина
2) Предположим, что b, cÎVk2.
от aк b– четная длина,
от bк с – длина 1,
Нечетная длина
Итак, это противоречит условию теоремы.
Рассмотренное разбиение вершин выполним для каждой компоненты G1, G2, …, Gmсвязности. И когда объединим независимые компоненты Vk1и Vk2для всех разбиений, то получим разбиение множества всех вершин исходного графа 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.
Описанный в примере алгоритм построения максимального паросочетания называется алгоритмом чередующихся цепей.
продолжение
--PAGE_BREAK--