Дискретная математика. Краткий курс. Учебное пособие

Казанский А.А.

Возрастное ограничение: 0+ Жанр: Наука Издательство: Проспект Дата размещения: 15.09.2015 ISBN: 9785392196043 Язык: Объем текста: 163 стр. Формат: epub

Оглавление

Глава 1. Теория множеств

Глава 2. Отношения

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

Глава 4. Логика и исчисление высказываний

Для бесплатного чтения доступна только часть главы! Для чтения полной версии необходимо приобрести книгу

Глава 3.
ТЕОРИЯ ГРАФОВ

3.1. Введение

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

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

Принято считать, что первая работа по теории графов принадлежит швейцарскому математику Леонарду Эйлеру. Она была посвящена решению задачи о кёнигсбергских мостах и опубликована в 1736 г. Граф может быть математической моделью любой системы, между элементами которой существует бинарное отношение. Ни природа элементов, ни характер связи между ними не играют при этом никакой роли. Граф можно изобразить в виде диаграммы, состоящей из точек (вершин) и линий (ребер), соединяющих некоторые пары этих точек. Длина линии, а также является ли она прямой или кривой, несущественно, поскольку линия должна указывать только на наличие связей между точками. Свое название графы получили именно из-за того, что они допускают графическое представление, термин образован от первых пяти букв английского слова graphically.

3.2. Определения

Граф G состоит из двух объектов:

1) множество V = V(G), элементы которого называются вершинами, точками или узлами G;

2) множество E = E(G), представляющее собой неупорядоченные пары различных вершин, называемые ребрами G.

Обычно граф обозначается как G(V, E), чем подчеркивается, что в графе имеется две части. Вершины графа u и v называются смежными, если существует ребро e = {u, v}. Вершины u и v называются концевыми вершинами ребра и говорят, что ребро e соединяет вершины u и v. Кроме того, говорят, что ребро e инцидентно каждой из концевых вершин u и v.

Графы изображаются диаграммами на плоскости. Каждая вершина V изображается либо точкой, либо маленькой окружностью (чтобы не путать вершины с пересечениями ребер), а каждое ребро e = {v1, v2} представляется линией, соединяющей концевые вершины v1 и v2. На рис. 3.1(а) представлен граф G(V, E), имеющий 5 вершин v1, v2, v3, v4, v5 и 7 ребер e1 = {v1, v2}, e2 = {v2, v3}, e3 = = {v3, v4}, e4 = {v4, v5}, e5 = {v1, v4}, e6 = {v2, v5} e7 = {v1, v5}.

Рис. 3.1

На рис. 3.1(b) показан граф, у которого имеются ребра e4 и e5 с одними и теми же концевыми вершинами. Такие ребра называются кратными ребрами. Этот граф содержит также ребро e2, которое имеет не две, а одну концевую вершину. Такое ребро называется петлей. Граф с петлями и кратными ребрами называют мультиграфом. Формальное определение графа не допускает ни петель, ни кратных ребер.

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

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

Степенью (валентностью) вершины v в графе G (обозначается deg(v)), называется число ребер G, которые инцидентны вершине v.

Теорема 3.1 (Эйлера). Сумма степеней вершин графа G равна удвоенному числу его ребер.

deg(vi) = 2 · q, где р — число вершин графа G, а q — число его ребер.

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

Теорема Эйлера верна и для мультиграфов, при этом считается, что каждая петля имеет два конца.

Теорема 3.2. Количество вершин графа с нечетными степенями четно.

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

Если степени всех вершин графа одинаковы и равны r, то такой граф называют регулярным или однородным степени r. Число ребер в регулярном графе

где р — число вершин графа.

Регулярный граф степени 0 называется пустым.

Если в графе с р вершинами каждая пара вершин соединена ребром, то такой регулярный граф степени р – 1 называется полным графом и обозначается Кр. Число ребер в полном графе Для задания полного графа достаточно указать число его вершин.

Регулярный граф степени 2 является циклом и при р вершинах обозначается Ср.

Регулярный граф степени 3 называется кубическим.

Следствие теоремы 3.2. Каждый кубический граф имеет четное число вершин.

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

Рис. 3.2

Следует заметить, что для одного и того же графа можно нарисовать диаграммы, которые будут внешне выглядеть по-разному. Однако они будут иметь одно и то же количество вершин, а вершины (если их как-то пометить, например пронумеровать) будут иметь ребра между теми же самыми парами вершин. Такие графы называются изоморфными. Установление изоморфизма является довольно трудоемкой задачей. На рис. 3.3 показаны графы, которые изоморфны графам предыдущего рисунка. Граф на рис. 3.2(а) изоморфен графу на рис. 3.3(а), а граф на рис. 3.2(b) изоморфен графу на рис. 3.3(b).

Рис. 3.3

Рассмотрим, например, вершину 1 на рис. 3.2(a) и 3.3(а). На обоих этих рисунках она смежна одним и тем же вершинам {2, 4, 6}. Вершина 2 смежна вершинам {1, 3, 6}, и это соответствие выполняется и для всех остальных вершин. Таким образом, это один и тот же граф, просто он иначе нарисован на диаграммах.

На рис. 3.2(b) и 3.3(b) также изображен один и тот же граф, однако это сразу не видно и необходимо устанавливать соответствие между вершинами обоих графов.

С 8 вершинами имеется 6 кубических графов, с 10 вершинами — 19, с 12 вершинами — 85 кубических графов и т.д. На рис. 3.4 показан кубический граф с 10 вершинами, называемый графом Петерсена.

Рис. 3.4

3.3. Подграфы. Изоморфизм и гомеоморфизм графов

Граф H = H(Vh, Eh) называется подграфом графа G = G(V, E), если он получен из него удалением каких-либо вершин или ребер, т.е. если Vh ⊆ V и Eh ⊆ E. Обычно выделяется три случая:

(a) подграф H(Vh, Eh); графа G(V, E) называется подграфом, порожденным вершинами Vh, если множество его ребер Eh состоит из тех ребер G, концевые вершины которых являются вершинами H,

(b) удаление любого ребра е из G приводит к подграфу G – е,

(c) удаление любой вершины v из G приводит к подграфу G – v, который получается при удалении из G вместе с вершиной v и всех ребер, которые содержат v.

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

Улам и Харари высказали гипотезу, что если имеется набор всех подграфов G – vi, при i = 1, 2, …, p, где р — число вершин графа G, то по ним можно восстановить исходный граф. Доказательство этой гипотезы даже для частных случаев представляет интерес для многих приложений. Например, в системах связи, когда требуется восстановить сигнал, принимаемый с искажениями.

Графы G(V, E) и G1(V!, E1) называются изоморфными, если существует взаимно-однозначное соответствие ƒ : V → V1 такое, что ребро {u, v) в G имеется тогда и только тогда, когда имеется ребро {ƒ(u), ƒ(v)} в G1.

Функция ƒ называется изоморфизмом. Показать, что два графа изоморфны, это значит установить изоморфизм ƒ между ними. Установление изоморфизма является очень важной, но крайне трудоемкой задачей. Однако при небольшом числе вершин изоморфизм можно установить прямым перебором. Для этого вершины одного графа нумеруются произвольным образом различными числами. Затем ищется такая нумерация вершин второго графа этими же числами, при которой сохраняется смежность, т.е. для каждой вершины v, которая в первом графе смежна вершинам, помеченным номерами {vi, vj, …, vk), имеется вершина во втором графе, которая смежна вершинам с такими же номерами.

Представление графа диаграммами дает много преимуществ при изучении его свойств. Однако не всегда очевидно, как изобразить граф, чтобы это преимущество использовалось наилучшим образом. На рис. 3.5 рассмотрен еще один пример, где графы G1, G2 и G3 хотя и выглядят по-разному, однако это один и тот же граф, что показывает нумерация их вершин. Вершина 1 во всех трех графах смежна вершинам {3, 4, 5}, вершина 2 смежна этим же самым вершинам {3, 4, 5}, а каждая из вершин 3, 4 и 5 смежна вершинам {1, 2}. Для графа G4, хотя он имеет такое же количество вершин и ребер, найти такое же размечивание вершин невозможно, поэтому граф G4 не изоморфен графам G1, G2 и G3.

Рис. 3.5

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

Из любого графа G можно получить новый граф, если добавить в его ребра дополнительные вершины степени 2. Два графа называются гомеоморфными, если они могут быть получены из одного и того же графа или изоморфных графов при помощи этого метода. Например, графы на рис. 3.6 не изоморфны, но гомеоморфны, поскольку получены подразбиение ребер из одного и того же графа К4.

Рис. 3.6

3.4. Дополнение графа

Дополнением GC графа G называется граф, имеющий те же вершины V(G), но две вершины смежны в GC тогда и только тогда, когда они не смежны в G.

На рис. 3.7 показаны граф G и граф GC, являющийся его дополнением.

Рассмотрим использование дополнения при доказательстве следующей популярной задачи.

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

Рис. 3.7

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

Теорема 3.2. Если G является графом с шестью вершинами, то либо G, либо его дополнение GC содержит цикл длины три (треугольник).

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

Рассмотрим любую вершину v в G. Какой бы граф мы ни брали, всегда найдется вершина, которая смежна с не менее чем тремя другими вершинами, либо в G, либо в его дополнении GC. Это следует из того, что сумма степеней вершины v в G и его дополнении равна 5. Но если сумма двух чисел равна 5, то по крайней мере одно слагаемое должно быть не меньше трех. Пусть вершина v смежна с тремя вершинами в G (если это не так, то в качестве исходного графа можно взять его дополнение, потому что тогда там будет такая вершина) — рис. 3.8.

Рис. 3.8

Если смежна какая-либо пара вершин (v1, v2), (v1, v3) или (v2, v3), то граф G содержит треугольник и условие теоремы выполняется. Если же ни одна из этих пар не смежна, то тогда треугольник образуется на вершинах v1, v2, v3 в дополнении графа G, что и доказывает теорему.

Обобщая эту теорему, можно поставить вопрос: какое наименьшее число вершин должен иметь граф, чтобы либо он содержал полный подграф Km, либо его дополнение содержало полный подграф Kn. Иными словами, чтобы в графе имелось m попарно смежных, либо n попарно несмежных вершин. Такое наименьшее число вершин обозначается r(m, n) и называется числом Рамсея. Очевидно, что r(m, n) = r(n, m). Рамсей показал, что для любых целых m и n существует наименьшее целое, такое, что каждый граф с r(m, n) вершинами содержит либо подграф Km, либо имеет подмножество из n попарно несмежных вершин. Ясно, что r(1, m) = r(m, 1) = 1, r(2, n) = n, r(m, 2) = m. В теореме 3.1 было показано, что r(3, 3) = 6. На 5 вершинах имеется граф, который не содержит подграфа K3 и дополнение которого также не содержит K3. Такой граф показан на рис. 3.9.

Рис. 3.9

Числа Рамсея известны только для небольших значений m, n и задача их определения является очень трудной. Так, например, известно, что r(3, 4) = 9, поэтому имеется граф на 8 вершинах, который не содержит подграфа K3 и его дополнение не содержит подграфа K4 (рис. 3.10).

Рис. 3.10

Самодополнительным графом называется граф, изоморфный своему дополнению. Самодополнительный граф с 5 вершинами и его дополнение представлены на рис. 3.9. Кроме того, имеется еще два самодополнительных графа на 4 и 5 вершинах (рис. 3.11).

Рис. 3.11

Число вершин в самодополнительном графе р = 4 · k или p = 4 · k + 1, где k = 1, 2, 3, … т.е. p ≡ 0, 1(mod 4). На 8 вершинах имеется 10 неизоморфных самодополнителных графов, 4 из них показаны на рис. 3.12.

Рис. 3.12

3.5. Маршруты, цепи, циклы

Маршрутом (a walk) в графе G называется чередующаяся последовательность вершин и ребер v0, e1, v1, e2, …, en, vn, которая начинается и заканчивается вершиной. Вершина v0 называется начальной, а vn — конечной вершиной маршрута.

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

Маршрут называется цепью (a trail), если все его ребра различны и простой цепью (a path), если все его вершины (а значит, и ребра) различны.

Иногда вместо термина простая цепь используется термин путь.

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

Рис. 3.13

Для графа G на рис. 3.13:

v0, e1, v1, e2, v2, e2, v1, e5, v4 — маршрут (длина 4),

v0, e1, v1, e2, v2, e3, v3, e4, v4, e5, v1 — цепь,

v0, e1, v1, e2, v2, e3, v3, e4, v4 — простая цепь,

v0, e1, v1, e1, v0 — цикл,

v1, e2, v2, e3, v3, e4, v4, e5, v1 — простой цикл.

В простых цепях и циклах ребра можно не указывать, тогда приведенные примеры можно переписать так:

v0, v1, v2, v3, v4 — простая цепь,

v1, v2, v3, v4, v1 — простой цикл.

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

Рис. 3.14

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

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

Обхватом графа G называется длина его кратчайшего простого цикла, обозначается g(G).

Окружением графа G называется длина самого длинного простого цикла, обозначается c(G). Если в графе нет циклов, то обхват и окружение не определены. На рис. 3.14 g(G) = 3, а c(G) = 4.

3.6. Расстояние в графе

Расстоянием d(u, v) между двумя вершинами u, v графа G называется длина кратчайшей простой цепи (геодезической), которая их соединяет (если u, v не соединены, то принимается, что d(u, v) = ∞). В связном графе расстояние является метрикой, т.е. удовлетворяет всем трем аксиомам метрики: для любых трех вершин u, v, w.

1. d(u, v) ≥ 0 и d(u, v) = 0 тогда и только тогда, когда u = v.

2. d(u, v) = d(v, u) — свойство симметрии расстояния.

3. d(u, v) + d(v, w) ≥ d(u, w) — неравенство треугольника.

Эксцентриситетом вершины v в графе G называется наибольшее из расстояний от вершины v до всех остальных вершин графа, обозначается e(v).

Радиусом графа r(G) называется наименьший из эксцентриситетов, а диаметром графа называется наибольший из эксцентриситетов всех вершин графа G.

Из определения следует, что радиус графа r(G) равен 1 тогда и только тогда, когда в графе G имеется вершина, смежная со всеми остальными вершинами графа, а диаметр равен 1, когда G является полным графом.

Вершина v0, имеющая наименьший эксцентриситет называется центром графа. В графе может быть более одного центра. Например, для графа на рис. 3.13 вершины имеют следующие эксцентриситеты: e(v0) = e(v3) = 3 и e(v1) = e(v2) = e(v4) = 2. Поэтому его радиус r(G) = 2, а диаметр d(G) = 3, а центры — вершины {1, 2, 4}.

Диаметр используется при проектировании компьютерных сетей. Диаметр определяет максимально возможную длину маршрута передачи сообщений между источником и адресатом при условии, что пропускная способность каналов не ограничивается. Поскольку на каждой вершине сети на маршруте осуществляется коммутация пакета, то диаметр d(G) определяет максимальное число коммутаций пакета на маршруте, т.е. фактически наибольшее время передачи пакета между источником и адресатом. Поскольку при проектировании сетей очень часто используются регулярные графы, то возникает задача перечисления регулярных графов, имеющих требуемый диаметр. В качестве примера рассмотрим кубические графы. Самый маленький кубический граф имеет 4 вершины – это граф K4. На рис. 3.15 показаны неизоморфные кубическе графы с р = 6 и d(G) = 2.

Рис. 3.15

С восемью вершинами имеется шесть неизоморфных кубических графа, три из них имеют диаметр d(G) = 2 (рис. 3.16) и три — диаметр d(G) = 3 (рис. 3.17).

Рис. 3.16

Рис. 3.17

С десятью вершинами имеется 19 кубических графов, с 12 вершинами — 85 и по мере роста вершин увеличивается и значение диаметра, при этом диапазон изменения значений диаметра также существенно увеличивается. На рис. 3.18 изображен кубический граф с 30 вершинами и диаметром d(G) = 4, а на рис. 3.19 показан кубический граф тоже с 30 вершинами, но с диаметром d(G) = 10.

d(G) = 4

Рис. 3.18

d(G) = 10

Рис. 3.19

Граф на рис. 3.18 можно получить следующим образом. Сначала строится простой цикл длины р (получается регулярный граф степени 2 с р ребрами) и его вершины нумеруются последовательно целыми числами 1, 2, 3,... р. Для построения остальных р\3 ребер сначала соединяются ребрами пары (a, b), где a = 3 · i(i = 1, 2,..., p\3), а номер второй вершины пары b представляет собой остаток от деления суммы (а + х) на р, т.е. b = (a + x) mod p. Значение х равно значению длины цикла, образуемого данным ребром, минус 1(т.е. в данном случае х = 9 – 1 = 8). Например, а = 3, b = (3 + 8) = 11, …a = 10, b = (30 + 8) mod 30 = 8. Наконец, оставшиеся p – p\3 ребер образуют пары (r, t), где r = 3 · (i – 1) + 1 (i = 1, 2, … p – p\3), t = r + p\2. Например, при i = 1 r = 1, t = 16 и т.д.

Диаметр кубического графа с 30 вершинами можно увеличить до 20, если использовать следующую конструкцию (рис. 3.20).

d(G) = 20

Рис. 3.20

3.7. Двудольные и k-дольные графы

Граф G = G(V, E) называется двудольным, если множество его вершин V можно разбить на два непересекающихся подмножества V1 и V2 таким образом, что каждое ребро G имеет один конец в V1, а другой в V2. Разбиение множества вершин V на подмножества {V1, V2} иногда называют двудольным разбиением графа G.

На рис. 3.21(a) показан двудольный граф G, а на рис. 3.21(b) дано еще одно его представление, где показано разбиение его вершин на две доли V1 и V2.

Рис. 3.21

Такое разбиение вершин графа на две доли V1 и V2 единственно. Обозначим количество вершин одной доли m, а другой n. Если каждая вершина из V1 соединена со всеми вершинами V2, то такой граф называют полным двудольным графом и обозначают Km, n, при этом обычно принимается m ≤ n. Так, на рис. 3.22(a) и (b) показан полный двудольный граф K3,3.

Рис. 3.22

Вершины графа на рис. 3.22 можно разбить и на три доли, например, таким образом, как на рис. 3.23.

Рис. 3.23

Граф G = (V, E) называется k-дольным, если множество его вершин можно разбить на k непересекающихся подмножеств V1, V2, …, Vk, так что каждое ребро графа G имеет одну концевую вершину в некотором подмножестве Vi, а другую в каком-то другом подмножестве Vj(i ≠ j).

Не каждый граф допускает разбиение на k долей, если k > 1. Например, граф С3 невозможно разбить на две доли, поскольку, поместив две вершины в разные доли, третью вершину нельзя поместить ни в одну из них, потому что она смежна каждой из этих вершин. Размещение ее в любой из этих долей приводит к тому, что ребро будет иметь обе свои концевые вершины в этой доле, что противоречит определению двудольного графа. Граф С3 является трехдольным графов. Граф K4 не является ни двудольным, ни трехдольным, так как при любом разбиении одно из ребер будет иметь свои концевые в одной доле. Граф K4 является четырехдольным графом.

Полным k-дольным графом называется k-дольный граф G с разбиением вершин {V1, V2,..., Vk}, при котором каждая вершина любой из долей Vi соединена со всеми вершинами каждой из остальных долей.

На рис. 3.24 показан полный 3-дольный граф.

Рис. 3.24

Теорема 3.3. Граф является двудольным тогда и только тогда, когда все его простые циклы имеют четную длину.

Доказательство. Необходимость. Дано: граф двудольный и требуется доказать, что все его циклы имеют четную длину. Разобьем множество вершин графа на два подмножества V1 и V2 так, что любое ребро этого графа имеет одну концевую вершину в V1, а другую в V2 (это всегда возможно по определению двудольного графа). Каждый простой цикл графа имеет вершины попеременно, то в одной, то в другой доле, например в цикле v1, v2, v3, v4, v5, v6, …, v2k, v1 все вершины с нечетными номерами лежат в одной доле, а с четными в другой и количество вершин в каждой доле одинаково и равно k. Отсюда — общее число вершин такого цикла равно 2 · k и всегда четно, поэтому и длина цикла всегда четна.

Достаточность. Дано: все циклы графа имеют четную длину, и необходимо доказать, что граф двудольный. Полагаем, что граф связный; если это не так, то применим рассуждения теоремы отдельно к каждой компоненте. Покажем, что множество вершин графа можно разбить на два подмножества V1 и V2, так что каждое ребро графа имеет одну концевую вершину в V1 и другую в V2 и нет ни одного ребра, имеющего обе концевые вершины в каком-то одном из этих множеств.

Возьмем произвольную вершину v и обозначим через V1 множество, состоящее из всех вершин, находящихся от нее на четном расстоянии. Тогда V2 = V\V1 — все остальные вершины графа и они находятся на нечетном расстоянии от вершины v. Предположим, что в V2 имеются две вершины u и w, которые соединены ребром. Тогда в графе существует простая цепь длины k1 от вершины v до вершины u, а также простая цепь длины k2 от вершины v до вершины w и обе цепи имеют нечетную длину. Кроме того, эти цепи вместе с ребром (u, w) образуют цикл, длина которого нечетна, поскольку равна k1 + k2 + 1 (здесь k1 + k2 — это сумма нечетных чисел и она четна). Однако наличие в графе цикла нечетной длины является противоречием, что и доказывает теорему.

3.8. Операции над графами

Пусть графы G1 и G2 не имеют ни общих вершин, ни общих ребер.

Объединением графов G1 и G2 называется граф G = G1 ∪ G2, множество вершин которого V = V1 ∪ V2 и ребер E = E1 ∪ E2.

Рис. 3.25

На рис. 2.35 показано объединение графов G1 = K2 и G2 = C3.

Соединением графов G1 и G2 называется граф G = G1 + G2, который состоит из объединения этих графов G1 ∪ G2 и всех ребер, соединяющих V1 и V2.

На рис. 3.26 показано соединение графов K2 и C3.

Рис. 3.26

Произведением графов G1 × G2 называется граф, множество вершин которого состоит из всех упорядоченных пар декартова произведения V1 × V2. Две вершины произведения (ui, uj) ∈ V1 × V2 и (v, vj)) ∈ V1 × V2 смежны тогда и только тогда, когда либо первые вершины пар совпадают ui = vi, а вторые смежны (uj смежна vj), либо вторые вершины совпадают uj = vj, а первые смежны (ui смежна vi).

На рис. 3.27 показаны графы, являющиеся декартовым произведением K2 × C3 и

Рис. 3.27

3.9. Многомерный куб как произведение графа K2

При проектировании конечных автоматов, при передаче данных, при построении оптимальных блочных кодов используются графы, имеющие специальную структуру. Такие графы являются подграфами графа, называемого n-мерным кубом. Граф n-мерного куба Qn может быть определен рекурсивно:

Q1 = K2; Q2 = K2 × K2; …; Qn = K2 × Qn-1.

На рис. 3.28 представлены Q2 и Q3

Рис. 3.28

Граф n-мерного куба можно определить иначе: вершины представляют собой все различные последовательности из нулей и единиц длины n, а две вершины соединены ребром, если соответствующие им наборы различаются точно в одной позиции (в одном разряде). На рис. 3.29 представлен граф Q4.

Рис. 3.29

Граф n-мерного куба и любой его подграф являются двудольными графами. Вследствие этого граф, содержащий цикл нечетной длины, не может быть подграфом n-куба, однако и не всякий двудольный граф может быть подграфом n-куба (т.е. не может быть вложен в n-куб). Минимальный двудольный граф, который не вложим в n-куб, — это граф K2,3 (рис. 3.30).

Рис. 3.30

Подграфы n-куб иногда называют кубируемыми графам, однако при этом их не следует путать с кубическими графами, т.е. графами, каждая вершина которых имеет степень три. Для того чтобы определить, является ли граф G с p вершинами подграфом n-куба, надо пометить все его вершины различными последовательностями из нулей и единиц, так чтобы каждое ребро было инцидентно вершинам, помеченным последовательностями, различающимися точно в одной позиции. Размерность куба n (длина последовательности) определяется из условия p < 2n. В работе Garey M.R. и Graham R.L. (J. Combinatorial Theory, 1975, №18) исследованы критические некубируемые графы. Критическим графом называется граф, который не является подграфом n-куба, однако удаление из него любого ребра делает его подграфом n-куба, т.е. кубируемым графом. Под удалением ребра e = {vi, vj} понимается удаление пары {vi, vj}, сами вершины при этом остаются. При удалении вершины удаляется не только эта вершина, но и все ребра, инцидентные этой вершине. Очевидно, что удаление вершины приводит к удалению по крайней мере одного ребра. Изучение критических по вложению в n-куб графов важно потому, что знание каталога критических графов позволило бы определить является ли некоторый граф подграфом n-куба или нет. Данный граф будет подграфом n-куба тогда и только тогда, когда он не содержит критических подграфов. Garey M.R. и Graham R.L предложили следующее преобразование исходного критического графа в другой критический граф, содержащий на три вершины больше (новые вершины зачернены) — рис 3.31).

Рис. 3.31

Применим преобразование для графа K2,3 (рис. 3.32).

Рис. 3.32

Это преобразование дает новый критический граф на 8 вершинах. Данное преобразование не является единственным. Рассмотрим следующее преобразование (увеличивающее число вершин на одну) — рис. 3.33.

Рис. 3.33

Применим это преобразование к критическому графу, полученному на рис. 3.32(b).

Рис. 3.34

Получим новый критический граф на 9 вершинах, рис.3.34(b).

Подобных процедур можно построить довольно много, они нужны для построения каталога критических графов при заданном количестве вершин. Так, на 5 вершинах имеется один критический граф K2,3, на 6 и 7 вершинах таких графов нет. На 8 вершинах также один критический граф (рис. 3.23(b)). На 9 вершина имеется 2 графа: один из них на рис. 3.34(b), а второй граф представлен на рис. 3.35.

Рис. 3.35

На 10 вершинах также два графа, на 11 вершинах 12 графов и т.д.

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

Рис. 3.36

Этот граф не вложим в n-куб, поскольку он содержит критический подграф на 8 вершинах (рис. 3.34(a)).

3.10. Связность графов

В связном графе любая пара вершин соединена по крайней мере одной простой цепью. Если вершина v не принадлежит никакому ребру, то она называется изолированной вершиной и deg(v) = 0. Изолированная вершина фактически является компонентой связности. Формально если считать, что вершина соединена сама с собой, то отношение «вершина v соединена с вершиной u» является отношением эквивалентности на множестве вершин графа, а компоненты связности графа представляют собой классы эквивалентности этого отношения.

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

Мостом в связном графе называется ребро, удаление которого делает граф несвязным. Например, ребро (3, 4) на рис. 3.37 является мостом.

Рис. 3.37

Теорема 3.4. Если ребро (u, v) графа G является мостом, тогда следующие утверждения эквивалентны:

(a) ребро (u, v) не принадлежит ни одному циклу,

(b) ребро (u, v) является единственной простой цепью, соединяющей вершину u с вершиной v,

(c) в графе G существуют вершины a, b такие, что каждая цепь, соединяющая их, содержит вершины u, v.

Доказательство (a). Докажем прямое утверждение. Дано: ребро (u, v) — мост, и надо доказать что оно не принадлежит ни одному простому циклу. Предположим противное, что оно принадлежит некоторому простому циклу. Тогда после удаления этого ребра между вершинами u, v должна остаться еще одна цепь, и поэтому граф должен быть связным. Однако это невозможно, поскольку это противоречит определению моста.

Докажем обратное утверждение. Дано: ребро (u, v) не принадлежит ни одному циклу, и надо доказать, что оно является мостом. Для доказательства рассмотрим любые две вершины a и b, которые соединены цепью, содержащей ребро (u, v). Если такая цепь единственна, то удаление ребра (u, v) разобьет граф на две компоненты связности: одна из них содержит вершины a, u и другая — вершины v и b. В этом случае ребро (u, v) удовлетворят определению моста. Если же между вершинами a, b есть еще одна цепь, не содержащая ребро (u, v), и все ее вершины, кроме вершин a, b, не совпадают с вершинами первой цепи, то это значит, что через вершины a, b проходит цикл, включающий ребро (u, v), что является противоречием. Если эта вторая цепь имеет какие-то вершины, общие с первой, например a’, b’, то тогда эти вершины будут соединять две цепи: одна — это оставшаяся часть первой цепи (включающей ребро (u, v)) и другая, состоящая из вершин, которые входят во вторую цепь. Но это значит, что вершины a’, b’ и ребро (u, v) являются частью цикла, что противоречит исходному утверждению.

Доказательство (b). Доказательство следует из утверждения (a), поскольку если вершины a, b соединяла бы еще одна простая цепь, то ребро) принадлежало бы циклу, что невозможно.

Доказательство (с). Удалим ребро (u, v). Граф G распадется на две компоненты связности. Выберем вершину a в той компоненте, где находится вершина u. Пусть вершина b находится в другой компоненте, которая содержит вершину v. Любая простая цепь из первой компоненты, начинающаяся в вершине a, должна будет содержать и вершину u, поскольку только эта вершина соединена со второй компонентой. Так же и для любой простой цепи во второй компоненте, которая заканчивается в вершине b. Она должна содержать вершину v. Поскольку в соответствии с утверждением (b) вершины u, v соединены единственной простой цепью, то и каждая простая цепь, соединяющая a, b, содержит и вершины u, v.

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

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

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

Рис. 3.38

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

На рис. 3.39(a) представлен граф G и три его блока (рис. 3.39(b), (c) и (d).

Рис. 3.39

Граф на рис. 3.39(e) не является блоком графа G, поскольку он не максимальный его подграф (нет ребра (2, 4)).

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

Рис. 3.40

На рис. 3.40 множества ребер {e1, e5}, {e3, e4, e5}, {e10, e9, e7, e3, e2} являются разделяющими, однако разрезами будут только первые два. Разделяющее множество ребер {e10, e9, e7, e3, e2} не разрез, потому что оно содержит разделяющее множество {e2, e3}.

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

Связностью графа χ называется наименьшее число вершин, удаление которых его несвязным. Связность несвязного графа равна нулю, а связность графа с точкой сочленения равна единице. Полный граф Кр нельзя сделать несвязным, поэтому принимается χ(Kp) = p – 1. Связность иногда называют также вершинной связностью.

Наука Казанский А.А. Дискретная математика. Краткий курс. Учебное пособие

Наука Казанский А.А. Дискретная математика. Краткий курс. Учебное пособие

В пособии изложены основные разделы современной дискретной математики. Рассматриваются вопросы, связанные с теорией множеств, теорией отношений, теорией графов и логикой. Материал построен на основе курса лекций, читаемого автором в технических вузах.<br /> В каждой главе рассмотрено большое число задач с подробными решениями и примерами, что позволяет эффективно и быстро осваивать изучаемую тему.<br /> Для студентов, обучающихся по специальности «Прикладная математика», а также для студентов технических и экономических факультетов, изучающих курс «Дискретная математика» и компьютерные технологии. Представляет интерес для тех, кто связан с использованием методов дискретной математики.

Внимание! Авторские права на книгу "Дискретная математика. Краткий курс. Учебное пособие" (Казанский А.А.) охраняются законодательством!