Восточноукраинский национальный

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

ВОСТОЧНОУКРАИНСКИЙ НАЦИОНАЛЬНЫЙ

УНИВЕРСИТЕТ

СЕВЕРОДОНЕЦКИЙ ТЕХНОЛОГИЧЕСКИЙ ИНСТИТУТ

 

 

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

К ПРАКТИЧЕСКИМ ЗАНЯТИЯМ ПО КУРСУ «ДИСКРЕТНАЯ МАТЕМАТИКА»

(ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ, ЧАСТЬ ІІ)

Северодонецк СТИ 2001

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

ВОСТОЧНОУКРАИНСКИЙ НАЦИОНАЛЬНЫЙ

УНИВЕРСИТЕТ

СЕВЕРОДОНЕЦКИЙ ТЕХНОЛОГИЧЕСКИЙ ИНСТИТУТ

 

 

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

К ПРАКТИЧЕСКИМ ЗАНЯТИЯМ ПО КУРСУ «ДИСКРЕТНАЯ МАТЕМАТИКА»

(ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ, ЧАСТЬ ІІ)

для студентов всех форм обучения специальностей «Компьютерные системы и сети», «Системное программирование»

Северодонецк СТИ 2001

Методические указания к практически занятиям по курсу «Дискретная математика» (элементы теории графов, часть II) для студентов всех форм обучения специальностей «Компьютерные системы и сети», «Системное программирование» (Сост. А.Е. Богданов, - Северодонецк: СТИ, 2001. – 49 с.

 

 

Составитель А.Е. Богданов

 

Данные методические указания содержат темы, не вошедшие в первую часть одноименных методических указаний.

 

А b c d e f

0 1 1 0 0 0 a 1 0 0 0 0 0 1 1 1 0 0 0

1 0 1 0 1 1 b 0 1 0 0 0 0 1 1 1 0 1 1

= SV{1,1,…1}= 1 1 0 1 1 0 c V 0 0 1 0 0 0 = 1 1 1 1 1 0

0 0 1 0 1 0 d 0 0 0 1 0 0 0 0 1 1 1 0

0 1 1 1 0 1 e 0 0 0 0 1 0 0 1 1 1 1 1

0 1 0 0 1 0 f 0 0 0 0 0 1 0 1 0 0 1 1

 

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

(a + b + c) (a + b + c + e + f) (a + b + c + d + e) (c + d + e) (b + c + d + e + f) (b + e + f) =

1 2 3 4 5 6

1, 2, 3: а + b + c = A, A(A+B)=A

= 2: e + f = B, = A(A + B) (A + C) E (E + F)(e + F) = A(A+C)=A =

3: d + e = C, E(E+F)=E

4,5: c + d + e = E.

5,6: b + f = F

1: c + d = A

= A. E. (e+F)= (a + b + c) (c + d + e) (e + b + f) = 2: f + b = B =(a + b + c).(е+А). (е+В)=

 

1 2

= |(е+А)(е+В)=е+А.В | = (a + b + c).(е+(с+d)(f+b)) = (a + b + c).(e + cf+cb+df+db) = ae+acf+

bbc=bc, bbd=bd,

+acb+ adf+adb+be+bcf+bbc+ bdf+bbd+ce+ccf+ccb+cdf+cdb= ccb=cb, ccf=cf, =

cb+bc=bc,

= ae + be + ce + adf + bc + abc + bcf + dcd + cf + cfa + cfd + bd + bdf + bda =

dc = A:A +Aa=A, A + Af=A, A + Ad = A;

= cf = B:B+Ba=B, B+BD=B; = ae +be + ce + adf + bc + cf + bd.

bd=C:C+Cf=C, C+Ca=C.

Минимальными покрытиями являются покрытия, содержащие по два элемента. Любое из минимальных покрытий является решением, т.е.

β₀(G) = |{a,e}| = |{b,e}|= |{c,e}| = |{b,c}|= |{c,f}| = |{b,d}| = 2.

Для проверки рассмотрим, например, вершины а и е: вершина а в графе G покрывает вершины в и с, вершина е покрывает вершины f, b, c, d. Так как вершина а и е покрывают сами себя, то все вершины заданного графа покрыты двумя вершинами а и е. Аналогично можно проверить и другие минимальные покрытия.

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

β₀(G) = |{в,с}| = 2.

Проверка вершин в и с на покрытие всех вершин графа G подтверждает правильность такого решения: вершина в покрывает себя вершины а, с, е, f, а вершина с покрывает себя и вершины a,b,e,d, т.е. все вершины заданного графа G покрыты. ■

Аналогично определяется β₁(G).

Модифицированной матрицей смежности ребер _p(G) графа G называется

_p = S_p(G) v {1,1,…1},

где S_p(G) – матрица смежности ребер, {1,1,…1} – единичная диагональная матрица.

Пример 8. Определить β₁(G) графа G (рис. 1.10). Выписать все минимальные покрытия, соответствующие значению β₁(G).

Строим модифицированную матрицу смежности _p(G) заданного графа G:

а b c d e

0 1 1 0 0 a 1 0 0 0 0 1 1 1 0 0

1 0 0 1 0 b 0 1 0 0 0 1 1 0 1 0

=S _pV{1,1,1} = 1 0 0 0 1 c V 0 0 1 0 0 = 1 0 1 0 1

0 1 0 0 1 d 0 0 0 1 0 0 1 0 1 1

0 0 1 1 0 e 0 0 0 0 1 0 0 1 1 1

 

 

Покрываем строки столбцами. Используя алгоритм Петрика и законы операций дизъюнкции и конъюнкции, получим:

1, 2: а + b = A,

(a + b + c) (a + b + d) (a + c + e) (b + d + e) (c + d + e) = 3,4: d + e = B, =

1 2 3 4

(A+c)(A+d)=A+cd,

= (A+c)(A+d)(a+c+e)(B+b)(B+c)= (B+b)(B+c)=B+bc = (a + b + cd)(a+c+e)(d+e+bc)=

1 2

1:b+cd=A,

= 2:c+e=B = (a + A) (a + B)(d+e+bc) = (a+AB)(d+e+bc)= (a+(b+cd)(c+e))(d+e+bc)=

ccd=cd,

= (a+bc+be+ccd+cde)(d+e+bc)= cd=A = (a + bc + be +A + Ae)(d + e + bc = | A +AE=A| =

a + be + cd = A,

= (a + bc + be + cd)(d + e + bc) = d + e = B = (bc + A) (dc + B)= bc + AB = bc +

bee = be, be + bed=be;

+ad+ ae +bed + bee + cdd+ cde = cdd = cd. cd + cde = cd = dc + ad + ae + be + cd.

Все покрытия имеют одинаковую мощность, значит,

β₁(G) = |{b,c}| = |{a,d}|= |{a,e}| = |{b,e}|= |{c,d}| = 2.

Любое из этих покрытий является решением.

Если нет необходимости определять все минимальные покрытия, то решение можно найти сразу из матрицы _p(G). Одой строки, которая покрывала бы все столбцы матрицы, нет. Две строки, которые покрывали бы все столбцы, имеются. Например, строки b и с.

Значит,

β₁(G) = |{b,c}| = 2.

Это минимальное число ребер, покрывающих все ребра заданного графа G:

ребро b покрывает себя и ребра a и d, ребро с покрывает себя иребра а и е. ■

1.4. Определение чисел β₀⁺(G), β₀^-(G).

В случае ориентированного графа G кроме вершинного числа внешней устойчивости β₀(G) различают положительное β₀⁺(G) и отрицательное β₀^-(G) вершинные числа внешней устойчивости.

Положительным вершинным числом внешней устойчивости β₀⁺(G)

графа G = < V, Г > называется минимальная мощность множества вершин V⁺= {v_i⁺} такого, что

{v_i⁺} {Гv_i⁺} = V, (1.2)

и при удалении хотя бы одной вершины из V⁺ указанное соотношение не выполняется.

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

Отрицательным вершинным числом внешней устойчивости β₀^-(G)

графа G = < V, Г > называется минимальная мощность множества вершин

V^-= {v_i^-} такого, что

{v_i^-} {Г ^-1v_i^-} = V, (1.3)

и при удалении хотя бы одной вершины из множества V^- указанное соотношение не выполняется.

Это число равно минимальному количеству вершин, которые «наблюдаются» всеми вершинами графа.

Пример 9. Найти V⁺, V^-, Гv_i⁺, Гv_i^- в ориентированном графе G (рис. 1.11).

v₁

 

 

v₄ v₂

v₃

 

G

 

Рис. 1.10

Заданный граф G имеет множество вершин V= {v_1, v_2, v_3, v₄}. Определим V⁺.

Множество вершин V⁺ состоит из вершин графа G, из которых исходят дуги, т.е. состоит из вершин, из которых «наблюдаются» другие вершины графа. Значит

V⁺= {v_1, v_2, v₄}.

Найдем Гv_i⁺ для этих вершин.

Гv₁= { v_2, v₄}, т.е. окрестность Гv₁ состоит из вершин, в которые входят дуги из вершины v₁. Аналогично

Гv₂= { v₃}, Гv₄= { v₃}.

Проверим соотношение (1.2):

{v_1, v_2, v_3, } { v_2, v₄} { v₃ } { v₃ } = {v_1, v_2, v_3, v₄} = V.

Определим V^-.

Множество вершин V^-состоит из вершин графа G, в которые входят дуги, т.е. состоит из вершин, которые «наблюдаются» из других вершин графа. Значит,

V^-= { v_2, v_3, v₄}.

Найдем Г ^-1v_i^- для этих вершин.

Г ^-1v₂ = {v₁}, т.е. окрестность Г ^-1v₂ состоит из вершины, из которой исходит дуга в вершину v₂.

Аналогично Г ^-1v₃ = {v_2, v₄}, Г ^-1v₄ = { v₁}.

Проверим соотношение (1.3):

{v_2, v_3, v_4, } { v₁} { v_2, v₄ } { v₁ } = {v_1, v_2, v_3, v₄} = V■

Число β₀⁺(G) вычисляется как минимальная мощность покрытия столбцов строками, а число β₀^-(G) – как минимальная мощность покрытия строк столбцами в модифицированной матрице смежности S(G) графа G.

а

f b

 

 

e c

d

G

 

Рис. 1.12

 

Пример 10. Для ориентированного графа G (рис. 1.12) определить числа β₀⁺(G) и β₀^-(G). Выписать все минимальные покрытия, соответствующие значениям β₀⁺(G) и β₀^-(G).

Находим модифицированную матрицу смежности (G) заданного графа G:

 

 

А b c d e f

0 0 0 0 0 1 a 1 0 0 0 0 0 1 0 0 0 0 1

0 0 0 0 0 1 b 0 1 0 0 0 0 0 1 0 0 0 1

= SV{1,1,…1} = 1 1 0 1 1 0 c V 0 0 1 0 0 0 = 1 1 1 1 1 0

0 1 0 0 0 0 d 0 0 0 1 0 0 0 1 0 1 0 0

0 0 0 0 0 1 e 0 0 0 0 1 0 0 0 0 0 1 1

0 0 0 1 0 0 f 0 0 0 0 0 1 0 0 0 1 0 1

 

Найдем β₀⁺(G). Для этого рассмотрим покрытие столбцов строками в S. Используя алгоритм Петрика и законы операций дизъюнкции и конъюнкции, получим:

(a + c) (b + c + d) c (c ++ d + f) (c + e) (a + b + e + f)=

 

c(c + d + f)= c, c(c + e) = c,

= c(c + b + d)=c, c(c + a) = c = c (a + b + e + f) = ca + cb + ce + cf.

 

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

 

β₀(G) = |{a,c}| = |{b,c}|= |{c,e}| = |{c,f}| = 2.

Проверим, например, вершины а и с. Из вершины а «наблюдается» вершина f, из вершины с «наблюдаются» вершины a,b,d,e. То есть из вершин а и с «наблюдаются» все вершины графа G.

Найдем β₀^-(G). Для этого рассмотрим покрытие строк столбцами в . Используя алгоритм Петрика и законы операций дизъюнкции и конъюнкции, получим:

(a + f) (b + f) c (a + b + c + d + e) (b + d) (e + f) (d + f) =

 

(b + d) ((b + d) + (a + c + e)) = b + d,

(f + a) (f + b) = f + ab,

= (f + ab)(f + e) = f + abe, =(b + d)(f + abde) = fb+babde+df+

(f + abe)(f + d) = f + abde

 

+ dabde= bf+df+abde+abde= bf+df+abde.

 

Следовательно, β₀(G) = |{b,f}| = |{d,f}| = 2.

Проверим, например, вершины b,f. Вершина f «наблюдается» из вершин a, b, e; вершина b «наблюдается» всеми вершинами графа G. ■

Плотность p(G) графа G.

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

Плотностью p(G) графа G=<V, Г> называется максимальная мощность носителя полного подграфа F графа G.

Значит, для определения плотности p(G) графа G необходимо выделить в графе G все полные подграфы.

Алгоритм выделения полных подграфов.

1. Сопоставляем корню синтезируемого дерева заданный граф.

2. Фиксируем в графе вершину v₀ с максимальной степенью, сопоставив ее концу исходящей из корня дуги. Строим | v₀ | исходящих из корня дуг (| v₀ | - мощность носителя неокрестности вершины v₀). Конец каждой из этих дуг взаимно однозначно сопоставляем вершине неокрестности (v₀).

3. Каждый конец v_α построенных дуг взвешиваем окрестностью G(v_α) вершины v_α графа, сопоставленного рассматриваемому корню.

4. Считаем конец v_α п построенного яруса корнем нового дерева.

5. Устанавливаем, взвешена ли вершина v_α символом Ø. Если «нет», то переходим к п.2, если «да» - то к п.6.

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

Закон поглощения. Если в k-ом ярусе дерева вершины v_i и v_j смежны, поддерево с корнем v_i построено и если в поддереве с корнем v_j, то соответствующая ветвь не строится.

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

Пример 11. Определить плотность p(G) графа G (рис. 1.1).

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

2 6

3 5

4

 

1

6 6

3 4 4

 

3 6 6 6

1

^{Ø Ø Ø Ø}

^F₁ ^F₂ ^F₃ ^F₄

Рис. 1.13

Здесь F_i – полные подграфы. Из рисунка видно, что мощность носителей всех подграфов равна трем, значит.

р(G) = |{2, 4, 3}| = |{2, 4, 6}| = |{2, 1, 6}|= |{4, 5, 6}| = 3.

Каждое множество состоит из попарно смежных вершин. ■

Н н а а

a,b,d,e - краски

Рис. 2.1 Рис. 2.2

Если теперь каким-либо образом отметить вершины,

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

Аналогичным образом говорят о раскраске ребер графа и вообще о

раскраске элементов произвольного множества.

Часто рассматривают не произвольные раскраски вершин (ребер)

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

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

Раскраской вершин графа G = < V, U > называется разбиение носителя V

графа G, при котором каждое подмножество V_i не содержит ни одной пары смежных вершин.

Каждому подмножеству сопоставляется цвет, в который окрашивают все элементы этого подмножества.

Вершины, окрашенные в один цвет, называют соцветными.

Хроматическим числом h(G) графа G называется минимальное число h (число красок), для которого граф имеет n-раскраску.

Если h(G)= n, то граф называется n-хроматическим.

Если h(G)<m, (m – число красок и раскраска удовлетворяет определению), то граф называется m –раскрашиваемым.

I – хроматический граф это пустой граф.

Теорема 2.1. Граф является 2-хроматическим тогда и только тогда, когда он не содержит циклов нечетной длины.

Двудольный граф – 2-хроматический граф.

Любое дерево – 2-хроматический граф.

Раскраска ребер графа.

Раскраской ребер графа G = < V, U > называется разбиение сигнатуры U графа G, при котором каждое подмножество U_i не содержит ни одной пары смежных ребер.

Каждому подмножеству сопоставляется краска, в которую окрашиваются все ребра этого подмножества.

Ребра одного цвета называются соцветными.

Хроматическим классом (хроматическим индексом) H(G) графа G называется минимальное число k (число красок), для которого граф имеет реберную k-раскраску.

Если H(G) < q (q – число красок и раскраска удовлетворяет определению), то граф называется реберно q-раскрашиваемым.

Теорема 2.6. Если граф G- двудольный граф и его максимальная степень равна s(G), то

H(G)= s(G). (2.8)

Теорема 2.7. Для любого графа F_n (кроме двудольного), построенного на n-вершинах

H(F_n) = n, если n-нечетное (n 1);

H(F_n) = n – 1, если n- четное.

Хроматический класс H(G) графа G совпадает с хроматическим числом h() графа = < , >, определяемого следующим образом: вершины из взаимно однозначно соответствуют ребрам графа G и

_а Г _b. когда соответствующие ребра графа G смежны.

Пример 2. Построить для графа G (рис. 2.3) граф = < >.

Обозначим в графе G ребра буквами (рис. 2.5а). Используя определение графа = < , >, построим этот граф (рис. 2.5б).

а b

1 3

k

f g 7 c

6 4

e d

G

a)

a b

k c

g d

f e

б)

Рис. 2.5

Согласно определению

H(G)= h().

Таким образом, определение H(G) сводится к задаче определения хроматического числа h(). ■

1 2 3 4 5 6 7

1. {1,3,5} 1 1 1

2. {1,5,7} 1 1 1

3. {1,4,7} 1 1 1

4. {2,4,7} 1 1 1

5. {2,5,7} 1 1 1

6. {2,4,6} 1 1 1

7. {3,6} 1 1

Определяем минимальное число строк, покрывающих все столбцы таблицы. Такими строками могут быть строки 1,4,7. Значит

h(G) = |{{1,3,5} {2,4,7}, {3,6}}| = 3.

Зададимся красками: для множества вершин {1,3,5} - краска а, для множества вершин {2,4,7} - краска b, для множества вершин {3,6} - краска с.

Раскрасим вершины графа G (рис. 2.6).

2 b

a 1 3 a,c

b

7

c 6 4 b

5 a

G

Рис. 2.6

Отметим, что вершину 3 можно раскрасить в две краски: а или с.

Сравним значение хроматического числа h(G) с оценками этого числа (пример 1). Видно, что т. 2.2 и т. 2.3 дали для заданного графа G хорошее приближение, а т.2.4 – удовлетворительное приближение.■

Пример 4. Определить хроматический класс H(G) графа G, у которого

V = {1,2,3,4,5,6,7}, U= {(1,2),(1,6), (2,3), (3,4),(3,7) (4,5),(5,6), (6,7)}.

Выделяем реберно пустые подграфы заданного графа G, предварительно обозначив ребра буквами (рис. 2.7)

2

a b

1 k 3

f g c

6 7

4

e d

5

 

b

k

g k c

d f

e g d

e

d

g b

k f

e g e d g Ø k Ø

 

E₈ E₁₀

 

Ø Ø Ø Ø Ø Ø Ø Ø