Лекции по Дискретным моделям

Магистратура факультета ВМК МГУ имени М.В. ЛомоносоваЛекции по курсу «Дискретные модели».Лектор – доцент Селезнева Светлана Николаевна1Графы. Простейшие свойства графов.Графом G называется пара множеств (V, E), где V — множество вершин, E — множествонеупорядоченных пар различных вершин, называемых ребрами. Если e = (v, w) ∈ E, торебро e соединяет вершины v и w, v и w концы ребра e, при этом вершины v и w — смежны.Граф с n вершинами, в котором любые две его различные вершины смежны, называетсяполным графом Kn , граф K3 называется треугольником. Граф называется двудольным,если его вершины можно разбить на две доли так, что смежны только вершины из разных долей. Двудольный граф с долями из n и m вершин, в котором смежны любые двевершины из разных долей, называется полным двудольным графом Kn,m .Два графа G1 = (V1 , E1 ) и G2 = (V2 , E2 ) называются изоморфными, если найдется такоевзаимно однозначное отображение ϕ : V1 → V2 , что для любой пары вершин v, w ∈ V1(v, w) ∈ E1 тогда и только тогда, когда (ϕ(v), ϕ(w)) ∈ E2 .Граф H = (V 0 , E 0 ) называется подграфом графа G = (V, E), если V 0 ⊆ V и E 0 ⊆ E.Если v ∈ V , то граф G − v получается из графа G удалением вершины v и всех ребер,содержащих эту вершину.

Если e ∈ E, то граф G − e получается из графа G удалениемребра e. Граф Ḡ = (V, Ē) называется дополнительным к графу G = (V, E), если Ē состоитиз всех тех ребер, которых нет в E, т.е. Ē = {(v, w) | v, w ∈ V, v 6= w, (v, w) ∈/ E}.Степенью dG (v) вершины v ∈ V в графе G = (V, E) называется число смежных с нейвершин. Если dG (v) = 0, то вершина v называется изолированной, если dG (v) = 1, товершина v называется висячей. Пусть δ(G) = min dG (v) и ∆(G) = max dG (v) соответv∈V (G)v∈V (G)ственно обозначают наименьшую и наибольшую степени вершин в графе G.Предложение 1.1 (формула PЭйлера для степеней вершин). 1.

Для каждого графа G =(V, E) справедливо равенствоdG (v) = 2|E|.v∈V2. В каждом графе число вершин, имеющих нечетную степень, четно.Маршрутом длины m в графе G называется чередующаяся последовательность вершин и ребер v0 , e1 , v1 , . . . , vm−1 , em , vm , в которой ei = (vi−1 , vi ) ∈ E при всех i = 1, . . . , m.Маршрут замкнут, если vm = v0 . Маршрут называется цепью, если все его ребра различны; замкнутая цепь называется циклом. Цепь называется простой цепью, если все еевершины попарно различны. Цикл v0 , e1 , v1 , . .

. , vm−1 , em , v0 называется простым циклом,если вершины v0 , v1 , . . . , vm−1 попарно различны.Предложение 1.2. Из любого замкнутого маршрута нечетной длины m, m ≥ 3, можновыделить простой цикл.Предложение 1.3. В любом графе G найдутся простая цепь с длиной, не меньшейδ(G) − 1, и простой цикл с длиной, не меньшей δ(G).1Граф называется связным, если любая пара его вершин соединена цепью.

Связныйподграф, который нельзя расширить добавлением вершин или ребер исходного графа так,чтобы он остался связным, называется компонентой связности.Предложение 1.4. Если граф G с p вершинами, q ребрами и s компонентами связности,то s ≥ p − q, если при этом в графе G отсутствуют циклы, то s = p − q.Предложение 1.5. 1. Если к связному графу добавить ребро, соединяющее его несмежные вершины, то появится цикл.2. Если в связном графе удалить ребро из цикла, то останется связный граф.Предложение 1.6. Любой граф G = (V, E) с δ(G) ≥|V |−12связен.Связный граф без циклов называется деревом.Предложение 1.7.

1. Любое дерево с p ≥ 2 вершинами содержит хотя бы две висячиевершины.2. В любом дереве с p вершинами и q ребрами верно q = p − 1.3. В любом дереве любые две вершины соединены ровно одной простой цепью.4. Если к дереву добавить ребро, соединяющее его несмежные вершины, то появитсяровно один цикл.5. Если из дерева удалить ребро, то останется граф с двумя компонентами свяности.2Остовные деревья в графах.Остовным деревом связного графа называется его пограф на всех вершинах, являющийсядеревом.Теорема 2.1. В каждом связном графе G = (V, E) найдется остовное дерево.Доказательство. 1-й способ. Если в графе G нет циклов, то он является своим остовнымдеревом.

Иначе рассмотрим в графе G цикл, и пусть e — ребро из этого цикла. Повторимрассуждения для графа G − e, который также является связным. На каждом шаге мыудаляем хотя бы один цикл графа G, но циклов конечное число. Поэтому через конечноечисло шагов получим дерево, которое и есть остовное дерево графа G.2-й способ. Пусть V = {v1 , .

. . , vp }. Шаг 1. Положим D1 = ({v1 }, ∅). Шаг j +1 (j < p−1).Пусть на шаге j построено дерево Dj = (Vj , Ej ), где |Vj | = j. Граф G — связный, поэтомунайдется ребро e = (u, w) ∈ E, такое что u ∈ Vj , w ∈ V \ Vj . Положим Dj+1 = (Vj ∪{w}, Ej ∪ e). Дерево Dp — остовное.Теорема 2.2. В полном помеченном графе Kn найдется nn−2 остовных деревьев.Доказательство. Пусть Kn = (V, E), где V = {1, 2, .

. . , n}. Для каждого остовного дереваD1 графа Kn построим его код k(D1 ) = (j1 , . . . , jn−2 ). Пусть i1 — это висячая вершина cнаименьшим номером в дереве D1 . Она смежна с единственной вершиной j1 . Повторимрассуждения для дерева D2 = D1 − i1 и т.д. Останавливаемся, когда получим дерево Dn−1 ,являющееся ребром.Пусть получен код k(D1 ) = (j1 , . . . , jn−2 ). Как по нему восстановить дерево D1 ? Заметим, что если i не содержится в коде k(D1 ), то i — висячая вершина дерева D.

Пусть2V1 = V . Выбираем наименьший номер i1 из V1 , не содержащийся в k(D1 ). Соединяемвершины i1 и j1 . Пусть V2 = V1 \ {i1 }. Повторяем рассуждения для множества V2 и кода (j2 , . . . , jn−2 ). Заметим, что множество Vn−1 содержит ровно две вершины. Их нужносоединить ребром. Получим дерево D1 .Число остовных деревьев в графе Kn совпадает с числом кодов (j1 , . . . , jn−2 ), где j1 ,. . . , jn−2 ∈ V . Значит, число остовных деревьев равно nn−2 .Теорема 2.3. Пусть D1 и D∗ – два остовных дерева связного графа G с m и n висячимивершинами соответственно (m < n). Тогда для каждого числа k, m < k < n, в графе Gнайдется остовное дерево с k висячими вершинами.Доказательство. Пусть D1 = (V, E1 ), D∗ = (V, E ∗ ), и e∗1 ∈ E ∗ \ E1 .

Рассмотрим графG1 = D1 + e∗1 . В нем есть единственный цикл C1 . В этом цикле выберем ребро e1 ∈/∗D , и пусть D2 = G1 − e1 . Граф D2 – дерево, повторим для него рассуждения и т.д. Витоге получим последовательность остовных деревьев D1 , D2 , . . . , D∗ . Отметим, что числовисячих вершин в соседних деревьях Dj и Dj+1 отличается не более, чем на 2.Пусть для некоторого k, m < k < n, в последовательности остовных деревьев нет деревас k висячими вершинами. Значит, найдутся два соседних дерева Dj и Dj+1 , такие, что вдереве Dj — (k − 1) висячих вершин, а в дереве Dj+1 — (k + 1) висячих вершин.Рассмотрим цикл Cj в графе Gj .

Концы ребра e∗j имеют степень больше двух, а концыребра ej имеют степень два в цикле Cj . Значит, в цикле Cj найдется такое ребро e, чтоодин его конец имеет стень два, а другой его конец имеет степень, большую двух.Тогда дерево D = Gj − e – остовное дерево с k вершинами в графе G.Cколько висячих вершин может быть в остовном дереве графа G?Предложение 2.1. В любом связном графе G найдется остовное дерево с не менее, чем∆(G) висячими вершинами.Доказательство. Будем строить остовное дерево так: сначала выберем такую вершинуv ∈ V , что dG (v) = ∆(G), вместе со всеми ребрами, которые ее содержат, затем будемдобавлять к этой звезде ребра графа G так, чтобы не появились циклы.

В итоге построимостовное дерево, в котором будет не менее, чем ∆(G) висячих вершин.Теорема 2.4. В связном графе G = (V, E) c δ(G) ≥ 3 найдется остовное дерево с неменее, чем |V |/4 висячими вершинами.Доказательство. Опишем алгоритм построения такого остовного дерева. Пусть деревоD – это подграф графа G. Висячую вершину дерева D назовем устойчивой, если всесмежные ей вершины принадлежат также дереву D. Обозначим через u(D) число еговисячих вершин дерева D, через s(D) – число его устойчивых висячих вершин и черезv(D) — число всех его вершин. Положим α(D) = 3u(D)/4 + s(D)/4 − v(D)/4.Остовное дерево будем строить по индукции. Базис индукции: выберем в графе G произвольную вершину v. Пусть D1 – это эта вершина вместе со всеми исходящими из нее ребрами и их вторыми концами.

Тогда α(D1 ) ≥ 3dG (v)/4 − (dG (v) + 1)/4 ≥ 1/2, т.к. dG (v) ≥ 3.Индуктивный переход. Пусть уже построено дерево Dj = (Vj , Ej ), и Wj = V \ Vj .31. Если в дереве Dj есть невисячая вершина v, смежная с некоторой вершиной w ∈ Wj ,то пусть Dj+1 = Dj + (v, w). Тогдаα(Dj+1 ) − α(Dj ) ≥ 3/4 − 1/4 = 1/2.2.

Иначе если в дереве Dj есть вершина v, смежная с хотя бы с двумя вершинамиw1 , w2 ∈ Wj , то пусть Dj+1 = Dj + (v, w1 ) + (v, w2 ). Тогдаα(Dj+1 ) − α(Dj ) ≥ 3/4 − 2 · (1/4) = 1/4.3. Иначе если в множестве Wj есть вершина w, смежная с какой-то вершиной v дереваDj и хотя бы двумя вершинами w1 , w2 ∈ Wj , то пусть Dj+1 = Dj + (v, w) + (w, w1 ) + (w, w2 ).Тогдаα(Dj+1 ) − α(Dj ) ≥ 3/4 − 3 · (1/4) = 0.4. Иначе в множестве Wj есть вершина w, смежная с вершинами дерева Dj . Т.к. п.3не выполняется, то вершина w смежна не более, чем с одной вершиной из множества Wj .Но dG (v) ≥ 3, поэтому вершина w смежна хотя бы с двумя вершинами v, v1 ∈ Vj . ПустьDj+1 = Dj +(v, w).

Т.к. п.п.1-2 не выполняются, вершина v1 – висячая в дереве Dj и смежнарово с одной вершиной из множества Wj , а именно, с вершиной w. Поэтому в дереве Dj+1висячая вершина v1 – устойчивая. Тогдаα(Dj+1 ) − α(Dj ) ≥ 1/4 − 1/4 = 0.5. Если п.п.1-4 нельзя применить, то остовное дерево D построено.В остовном дереве D все висячие вершины устойчивые. Поэтомуα(D) = u(D) − v(D)/4, или u(D) = v(G)/4 + α(D).Но α(D) ≥ α(D1 ), т.к. на каждом шаге построения мы только увеличивали этот параметр.Отсюда получаемu(D) ≥ |V |/4.3Раскраски графов. Хроматическое число графа.Раскраской графа G = (V, E) в k цветов называется отображение ρ : V → {1, 2, . .

. , k},при котором из (v, w) ∈ E следует ρ(v) 6= ρ(w) (т.е. любые смежные вершины окрашены вразные цвета). Наименьшее возможное число цветов, в которое можно окрасить вершиныграфа G, называется его хроматическим числом и обозначается χ(G). Граф G называетсядвуцветным, если χ(G) = 2.Теорема 3.1 (Кёнига).

Граф G = (V, E) является двуцветным тогда и только тогда,когда в нем нет циклов нечетной длины.Доказательство. Если в графе G есть цикл нечетной длины, то вершины этого циклав два цвета не раскрасить. Пусть теперь в графе G нет циклов нечетной длины. Будемсчитать, что G – связный граф, иначе можно провести рассуждения для каждой его компоненты связности.

Построим в графе G его остовное дерево D. В любом дереве для4каждой пары вершин v, w ∈ V существует ровно одна цепь из v в w. Пусть v ∈ V – какаято вершина. Рассмотрим следующую раскраску ρ вершин w ∈ V дерева D в два цвета:ρ(w) = 1 (соответственно, ρ(w) = 2), если длина единственной цепи из v в w четна (соответственно, нечетна).