Горбатов В.А. Фундаментальные Основы Дискретной Математики. Информационная Математика

Подождите немного. Документ загружается.

§ 3.5. Устойчивость, покрытия, паросочетания

191

Определение числа внешней устойчивости сводится к построе

нию модифицированной матрицы смежности и выделению покры

тия с минимальным числом элементов.

Пример 3.10. Определим вершинное число внешней устойчивости /3o(G)

графа G (рис. 3.16), матрица 5(G) которого имеет сле

дующий вид:

5 =

с d

1 0

0 0

1 1 1

0 1 Ь

1 1

0 с

1 1 1

0 1 0 1

1 1

Покрываем строки столбцами или столбцы стро

ками матрицы смежности, что равнозначно в силу ее

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

получаем

(а + с + /)(Ь + с + d + f)(a + b + c + d + e)(b + с + d + /)(с + e + f) x

x(a + b + d + e + f) = (c + f + ae)(a + b + d + в + cf)(b + с + d + /) =

= (c + / + ae)(b + d + ac + c f + ae + ce + e/) =

= bc + cd + ac + cf + ce + bf + df + a f + e f + abe + ade.

Каждый мультипликативный члеи полученного выражения определяет внешне

устойчивое множество вершин; минимальная мощность такого множества равна

вершинному числу внешней устойчивости /3o(G) = 2.

В случае ориентированного графа кроме вершинного числа

внешней устойчивости /?o(G) графа G различают положительное

0q (G) и отрицательное (G) вершинные числа внешней устой

чивости.

Положительным вершинным числом внешней устойчивости

0о (G) графа G = = (V, Г) называется минимальная мощность

Множества вершин V + = {«*} такого, что

{i.t}U {r ^ } = V, (3.14)

И при удалении хотя бы одной вершины из V + соотношение (3.14)

ДО выполняется. Это число определяет минимальное количество

вершин, из которых наблюдаются (достижимы за один шаг) все

Вершины графа.

Отрицательным вершинным числом внешней устойчивости

(G) графа G = (V, Г) называется минимальная мощность мно

жества вершин V~ = {и~} такого, что

{u-}U {r-V } = F,

(3.15)

И при удалении хотя бы одной вершины из V~ соотношение (3.15)

Не выполняется. Это число равно минимальному количеству вер-

ЭДШн, которые наблюдаются всеми вершинами графа.

192

Гл. 3. Теория графов и мографов

Очевидно, что число Pq (G) вычисляется как минимальная

мощность покрытия столбцов строками, число (G) — как ми

нимальная мощность покрытия строк столбцами в модифициро

ванной матрице смежности 5(G) графа G.

Пример 3.11. Вычислим числа /^ (G ) и Po(G) графа G (рис. 3.17), мо

дифицированная матрица смежности которого имеет

вид

5 =

Согласно определению внешне устойчивого мно-

Рис 3 17 жества, в котором вершины, принадлежащие этому

множеству, “наблюдаемы самими собой” , диагональ

ные элементы 5,у матрицы смежиостн 5(G) имеют

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

модифицированной матрице смежности с помощью алгоритма Петрика

(а + /)(Ь + d)(a + Ь + с)(с + d)(c + е)(Ь + d + е + /) =

= (а + /)(с + ed)(b+ ad + dc) =

= (а + f)(cb + dc + ebd + aed) =

= abc + adc + ade + bcf + cdf + bedf,

получаем /3$ (G) = 3. Каждый мультипликативный член в этих выражениях

определяет соответствующее внешне устойчивое множество.

Реберное число независимости Si(G), число реберного покры

тия tti(G) и реберное число внешней устойчивости Pi(G) графа

G = (V-, Г) определяются аналогично, только вместо модифици

рованной матрицы смежности вершин исходной информацией яв

ляется модифицированная матрица смежности ребер SP(G)

графа G:

5P(G) = 5P(G)V{1, 1, 1},

где SP(G) — матрица смежности ребер, {1, 1, ..1} — диагональ

ная единичная матрица.

Пример 3.12. Найдем ffi(G), »i(G ) и (G) графа G = (V, Г), изображен

ного в верхней половине рис. 3.18.

Для определения реберного числа независимости ffi(G) графа G восполь

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

заданный граф и определим ребро, смежное с минимальным количеством ре

бер. Это ребро к, оио смежно с тремя ребрами: /, р и т. Сопоставим ре

брам к, /, р и m концы исходящих из кория дерева дуг и взвесим каждую

вершину построенного яруса частичным подграфом, каждое ребро которого ие

смежно с ребром, сопоставленным этой вершине (рис. 3.18). Другими словами,

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

яруса дерева, каждую из которых взвешиваем неокрестностыо соответствующ его

§ 3.5. Устойчивость, покрытия, паросочетания 193

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

Рис. 3.18

0, порождаем все реберно независимые множества (рис. 3.19):

Ei = {Ь, k, n}, Е2 = {d, к, п},

Е3 = {с, к, n}, Et = {а, с, к},

Es = {а, е, к), Е6 = {cf, е, к},

Ei = {Ь, /, р}, Eg = {d, f, р},

Еэ = {с, /, р}, Ею = {of, е, /} ,

Ец = {е, /, т } , £12 = {Ь, /, т } ,

Ец = {а, с, р}, Ец = {а, е, т } ,

Ец = {Ь, т , п}.

Покрывая строки столбцами модифицированной матрицы смежности ребер

Рис. 3.19

7 В. А. Горбатов

194

Гл. 3. Теория графов и мографов

заданного графа G

с d е к

тп п

1 1

0 0

0 1 0

1 1 1

0 0 0 0 0

0 1 1 1 1 0 0 1 0 0 с

1 1

0 0 0 1 0

1 0 1 0

1 1

0 0 0 0

1 1

1 0

0 0 0 0

1 0

1 1

тп

0 0

1 0

0 0

0 1

S.=

получаем, что реберное число внешней устойчивости 0i(G) графа G равно 3:

|{Ь, тп, п}| = 3.

§ 3.6. Вложение графов

Рассмотрим топологические свойства графов. Топология иссле

дует свойства графов, инвариантные относительно гомеоморфных

преобразований. Эти свойства определяются топологическими ин

вариантами.

Два графа гомеоморфны, если они изоморфны с точностью до

вершин степени 2. Другими словами, два графа гомеоморфны,

если они преобразуются до графов, изоморфных друг другу, заме

ной некоторых ребер цепями соответствующей длины.

Род поверхности — это наибольшее число простых замкну

тых кривых на поверхности, которые не разъединяют эту поверх

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

поскольку их разъединяет любая замкнутая кривая. Тор — по

верхность первого рода. Любая поверхность p-то рода эквива

лентна сфере с р ручками.

Род графа 7(G) — это минимальный род среди всех поверхно

стей, на которых граф G можно изобразить так, чтобы его ребра

пересекались только в вершинах. Граф называется

планарным,

если изображается на плоскости так, что его ребра пересекаются

только в вершинах. Проблема характеризации планарных графов

долгое время оставалась нерешенной. В 1927 г. Л.С. Понтрягин

доказал (но не опубликовал) критерий планарности, который неза

висимо от него был открыт и опубликован польским математиком

Куратовским в 1930 г.

Теорема 3.18 (Л.С. Понтрягин). Граф планарен тогда и

только тогда, когда он не содержит подграфа, гомеоморфного

F5 или К3<3 (рис. 3.20).

Основываясь на критерии Понтрягина, можно получить еще

один критерий планарности, если ввести понятие элементарного

стягивания, которое состоит в следующем. При стягивании лю

бого ребра графа оно выбрасывается, а обе его вершины а и Ь

(рис. 3.21), коинцидентные ему, отождествляются; полученная при

§ 3.6. Вложение графов 195

этом вершина коинцидентна тем же ребрам, что и а, b (кроме

ребра, которое выброшено).

Теорема 3.19. Граф планарен тогда и только тогда, ко

гда он не содержит подграфов, стягиваемых к Fs или к Кз1з.

В 1932 г. американец Уитни ввел еще один критерий планар

ности, использовав понятие абстрактной двойственности графа.

Граф G* называется абстрактно двойственным к G, если между

ребрами графов G и G* существует взаимно однозначное соответ-

Рис. 3.20

ствие; подмножеству ребер из G, образующих цикл в G, соответ

ствует подмножество ребер из G*, образующих разрез в G*.

Если G содержит висячую вершину v, s(u) = 1, то в G* по

лучается петля. На рис. 3.22 изображены графы G и G*, причем

граф G изображен штриховыми линиями.

Теорема 3.20 (Уитни). Граф является планарным тогда и

только тогда, когда существует абстрактно двойственный к

нему граф.

196

Гл. 3. Теория графов и мографов

Рассмотрим задачу, возникшую при проектировании печатной

схемы. При изготовлении электронных приборов соединительные

провода наносят печатным способом на плоскую поверхность изо

ляционного материала. Печатные проводники не изолированы, по

этому они не должны пересекаться. Однако расположение прибо

ров на плате может быть таким, что невозможно избежать пересе

чения, поэтому, чтобы правильно спроектировать печатную схему,

надо знать, является ли граф, в котором роль вершин играют

приборы, а ребрами служат соединения между ними, планарным.

Если граф непланарный, то печать должна проводиться на не

скольких плоскостях и необходимо знать либо число скрещива

ний графа (наименьшее возможное число пересечений при изо

бражении его на плоскости), либо его толщину. Толщиной графа

G называется наименьшее число планарных графов, объединение

которых дает G. Толщина планарного графа равна 1. Нижняя

оценка толщины t(G) графа G = (F, U), определяется неравен

ством п

Х>,- - 2

t(G) > 1 +

»=1

6(п - 2)

(3.16)

где ] [ — целая часть, \V\ = n, st- — степень i-й вершины.

Рассмотрим граф, изображенный на рис. 3.23, а. Определим,

можно ли осуществить однослойную печать, й если нет, то вы-

Рис. 3.23

ясним, сколько потребуется слоев и какие ребра следует удалить,

чтобы граф стал плоским.

Согласно критерию Понтрягина этот граф является непланар

ным, поскольку содержит подграфы, гомеоморфные F5 (рис. 3.24, а)

и К3<3 (рис. 3.24,6). Толщина графа G ие меньше 2:

32-2

t(G) > 1 -f-

2, t(G) > 2.

6(7-2)

Чтобы определить, какие ребра необходимо удалить для пре

образования графа в планарный, выделим все запрещенные фи

§3-6. Вложение графов

197

гуры и построим двумерную таблицу, каждая строка которой вза

имно однозначно соответствует запрещенной фигуре Qi, а стол

бец — ребру pj. Тогда покрытие строк столбцами этой таблицы

определит, какие ребра необходимо удалить, чтобы граф стал пла

нарным. Минимальное покрытие будет соответствовать минималь

ному решению, так как удаление любого ребра выводит запрещен

ную фигуру из класса подграфов, гомеоморфных F5 или К3,3.

Таблица для рассматриваемого графа имеет следующий вид:

Таблица 3.1

Q i

P i

{ 1.2}

{2,6} {2,3}

{!,«} {*Д} О Д }

{2,4}

{2,7}

{*,«}

{а,7}

{».*}

{«,«}

{*,5}

{5,7}

Q i

111

Q i

Минимальное покрытие содержит одно из ребер* {2, 3}, {2, 4},

^3, 6}, {3, 7}, {4, 6}, {4, 5} или {5, 7}. После удаления, например,

ребра {3, 6} получаем планарный граф, плоское представление ко-

Торого изображено на рис. 3.23, б. Соединение, которое соответ

ствует удаленному ребру (показано штриховой линией), реализу

ется на второй плоскости. Толщина t(G) графа G равна 2.

Большой практический интерес представляет проблема вло

жения графов в другие графы, имеющие специальные структур

ные свойства. Важным классом таких графов является класс

Ягмерных кубов. Они находят применение в теории кодирования

При передаче данных и при проектировании автоматов. Обозна

чим n-мерный куб через Мощность его носителя равна 2П,

Мощность сигнатуры — п • 2п~1.

Введем метрику на графе # „ следующим образом. Пусть неот

рицательная функция от двух переменных d(a, b) определяет рас

стояние между двумя вершинами a, b G Нп, равное числу ребер в

Кратчайшей простой цепи, соединяющей а и 6. При этом выпол

няются следующие условия:

1) d(a, а') = 0 тогда и только тогда, когда вершины а, и а'

Совпадают;

198

Гл. 3. Теория графов и мографов

2) d(a, b) = d(b, а);

3) d(a, b) + d(b, с) > d(a, с) для любых а, Ь, с G Нп.

Следовательно, множество вершин n-куба вместе с введенной

таким образом метрикой, является метрическим пространством,

которое назовем булевым пространством. Если метрика введена

в данное множество, то она введена и в любое его подмножество

как ограничение функции d. Поэтому всякий подграф n-куба также

есть метрическое пространство.

Рассмотрим задачу вложения графа G в булево пространство

Нп. Граф G = (V, U) называется вложимым в булево простран

ство Нп = (Vh , Uh ) или кубируемым, если существует соответ

ствие <р между вершинами графа G и гиперкуба Нп такое, что если

(Va, vp) 6 и, то (<p(va), <p(vp)) в Uh - Кубируемый граф не следует

путать с кубическим графом — графом, каждая вершина которого

имеет степень, равную 3.

Так как n-куб является двудольным графом, то в соответствии

с теоремой Кёнига все его простые циклы четны, и поэтому любой

граф, который содержит подграф, являющийся нечетным циклом,

некубируем. Так как n-куб изомор

фен дистрибутивной решетке, то граф

Кёнига K %t3 (рис. 3.25) также явля

ется некубируемым графом. Любой

же частичный граф цикла нечетной

длины и граф К2,з вложимы в булево

р 3 2 пространство. Следовательно, циклы

ис' ’ нечетной длины и граф Кёнига

являются запрещенными фигурами вложения графа в булево про

странство. Под запрещенной фигурой в данном случае понимаем

критически невложимый граф, т. е. некубируемый граф, у кото

рого все частичные графы кубируемые. Рассмотрим процедуры

порождения запрещенных фигур на основе известных.

Теорема 3.21 (Грехем). Замена ребра р в грани запрещен

ной фигуры Q на граф Кёнига К2,з без этого ребра р, т. е. на

^ 2,3\Pi порождает новую запрещенную формулу T\(Q) (рис. 3.26).

Порождение запрещенных фигур вложения графов в булево про

странство с помощью процедуры Грехема (теорема 3.21) показано

на рис. 3.27.

Характеризация кубируемых графов достаточно сложна из-за

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

тур.

Для того чтобы определить причины, мешающие графу быть

кубируемым, надо выявить его структурные свойства, сформули

ровав, например, условия, описывающие взаимосвязь между его

параметрами, которые несут информацию об этих причинах.

Рассмотрим некоторые свойства n-куба, влияющие на струк

туру запрещенных фигур. Максимальная длина цепи, соединяю-

§3.6. Вложение графов 199

шей две вершины va, vp n-куба, равна 2П — 1. Этой цепью явля

ется остов графа Нп. Расстояние d(x, у) между двумя вершинами

х, у € Нп равно г, г = 1, 2, . . п. Две вершины х и у п-куба, уда-

Рис. 3.27

ленные друг от друга на расстояние, равное диаметру, соединены

между собой п! цепями.

Теорема 3.22. Если зафиксировать любую вершину п-куба

X G Нп, то множество всех остальных вершин разбивается

на п подмножеств V; Е Нп таких, что каждая вершина i-го

Подмножества и; е имеет расстояние до фиксированной

рершины, равное d(x, V{) = г, а число таких вершин в i-м под

множестве равно (") для всех i.

Поставим в соответствие каждой вершине п-куба двоичный

вектор длины п. Так как п-куб является регулярным графом, каж

дая вершина которого имеет степень, равную п, то, не теряя общ

ности, в качестве фиксируемой вершины возьмем вершину 00.. .0.

200

Гл.З. Теория графов и мографов

Разбив множество вершин п-куба на подмножества вершин, ко

торым соответствуют векторы с равным числом единиц, заметим,

что каждая вершина г-го подмножества, которой соответствует век

тор с i единицами, удалена от рассматриваемой вершины на рас

стояние, равное г. Количество таких вершин равно (").

Теорема 3.23. В п-кубе количество простых цепей длины

к, к< п, между вершинами va, vp, расстояние между которыми

d(va, vp) — к и которые не имеют других общих вершин, кроме

va, vp, равно к.

Все к\ цепей длины к между вершинами va и vp, d(va, vp) — к,

образуют к-куб. В этом кубе минимальная мощность множества

отделяющих вершин равна к — количеству вершин, смежных с

1000

п = 3

юооо

п = 5

п = 4

100000

Рис. 3.28

va и vp. Отсюда согласно теореме 3.9 количество простых вершин

непересекающихся цепей между вершинами va и vp равно к.

Полученный результат является важным при изучении запре

щенных (критических) графов. Заметим, что число наикратчай

ших простых (геодезических) цепей между двумя вершинами,

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

Число же непересекающихся простых цепей' между вершинами

п-куба, для которых расстояние по Хеммингу между ними меньше

их длины, находится в зависимости от размерности п-куба.