Математика для гуманитарных, экологических и экономико-юридических специальностей. Часть 1

151

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

Упражнения

1.(795). Укажите номера простых графов (рис. 5.14).

2.(РЦХ). Укажите степени вершин графа 2 (рис. 5.14) в порядке их нумерации.

3.(731). Укажите номера графов, являющихся частичными по отношению к графу 4 (рис. 5.14).

4.(153). Укажите номера псевдографов, представленных на рис. 5.14.

5.(В54). Укажите номера мультиграфов на рис. 5.14.

6.(АЙК). Укажите номера графов, являющихся частичными по отношению к графу 8 (рис. 5.14).

5.7.Маршруты. Цепи. Циклы

Пусть граф G содержит множество V вершин и множество Å ребер. Маршрутом длины n называется непустая последовательность n

ребер вида

где ребро ej (j = 1, 2, …, n) соединяет вершины vj è vj+1. Очевидно, что

в последовательности (5.1) одни и те же вершины могут повторяться. Примерами маршрутов являются следующие последовательности

вершин и ребер графа, приведенного на рис. 5.15:

152

4å8 1 å5 3 å6 3 å7 4 å7 3

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

Маршрут называется цепью, если в нем нет повторяющихся ребер. Примером может служить маршрут (5.3).

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

Число ребер, входящих в цепь, называется длиной цепи (цикла).

Упражнения

1. В нижеприведенном списке укажите (рис. 5.15) (600) маршруты, (794) циклы, (961) замкнутые маршруты, (627) простые цепи, (Г52) цепи, (569) простые циклы:

2.(В72). В упр. 1 укажите последовательности, не являющиеся маршрутами.

3.(885). В упр. 1 укажите простые цепи длины 1.

153

4.(196). В упр. 1 укажите цепи длины 2.

5.В нижеприведенном списке укажите (рис. 5.16) (РЕФ) маршруты, (УЗС) циклы, (УТК) простые циклы, (У92) замкнутые маршруты, (88Ш) простые цепи, (ОЖУ) цепи:

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

Две вершины v è w графа называются связными, если существует

соединяющая их цепь. Если же в графе нет цепи, соединяющей вершины v è w, то вершины v è w называются несвязными. Например,

не соединенных цепью, то граф называется несвязным (многокомпонентным). Согласно этим определениям граф на рис. 5.16 является связным, а граф, приведенный на рис. 5.17, — несвязным.

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

графа, приведенного на рис. 5.18, равна 9.

Упражнения

1.(ОЖФ). Укажите степень связности графа на рис. 5.19.

2.(ВРХ)! Определите степень связности подграфа, построенного на основе рис. 5.17 путем удаления из графа вершин 3 и 7; удаления вершин 2, 3, 6, 7.

154

3. Ниже дан список графов, заданных множествами их ребер. Каждый граф содержит 6 вершин. Укажите номера (ЭЕЕ) трехкомпонентных графов, (ФС9) четырехкомпонентных:

4. (К66). На какие вопросы Вы ответите «да»:

1)может ли нуль-граф быть однокомпонентным;

2)может ли граф быть однокомпонентным, если в нем 10 вершин и 8 ребер;

3)верно ли, что граф на n вершинах, не содержащий ни одного ребра, имеет степень связности, равную n;

4)относится ли пустой граф к однокомпонентным;

5)относится ли пустой граф к многокомпонентным;

6)может ли граф, содержащий n вершин и n ребер, иметь степень связности, равную n;

7)в графе 20 ребер, степень каждой вершины равна 2, может ли граф иметь степень связности, равную 15?

5. (335)! В графе 20 вершин. Степень каждой вершины равна 1. Сколько в графе компонент? Сколько ребер?

5.9.Эйлеровы цепи и циклы.

Уникурсальная линия

Леонард Эйлер (1707–1783), швейцарский математик, механик, физик и астроном, является звездой первой величины на небосклоне науки. Он много лет работал в Петербургской Академии наук. За свою жизнь он издал более 800 научных работ. Творческая активность Л. Эйлера оставалась на высочайшем уровне и в преклонном возрасте, хотя в последние 17 лет его жизнь была омрачена потерей зрения. Очень непросто перечислить даже основные результаты научной деятельности Л. Эйлера. Он доказал великую теорему Ферма для показателей 3 и 4, положил начало топологии, построил точную теорию движения Луны с учетом притяжения не только Земли, но и Солнца. У него много трудов по теории комплексных чисел, вариационному исчислению, гидравлике, кораблестроению, геометрической оптике, механике твердого тела, теории музыки, теории графов и др.

155

В первой работе Эйлера по теории графов, опубликованной в 1736 г., дано решение головоломки о Кенигсбергских мостах. Город Кенигсберг (на современных географических картах это город Калининград) расположен на берегах реки Преголи (ударение на букву «о») и двух ее островах. Острова и берега в те времена были связаны семью мостами (рис. 5.20). Горожане любили гулять по этим мостам и пытались найти такой путь, чтобы, выйдя из одной точки, пройти точно по одному разу по всем мостам и вернуться в исходную точку.

Å „

Ðèñ. 5.20

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

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

Приведем две теоремы об эйлеровых графах.

Теорема 1. Если в связном графе все вершины четны, то этот граф содержит эйлеров цикл.

Доказательство можно найти в [1, с. 37; 30, с. 61]. Верно и обратное утверждение: если граф содержит эйлеров цикл, то все его вершины четны.

Построим граф по рис. 5.20. Получим рис. 5.21. Вершины 1 и 4 этого графа обозначают берега, вершины 2 и 3 — острова на реке, а ребра — мосты. Степени всех вершин графа нечетны, следовательно, в графе нет эйлерова цикла и нет эйлеровой цепи.

На рис. 5.22 приведен граф, в котором степени всех вершин четны. Обход его ребер можно начать с любой вершины. Обозначим ребра буквами à, b, c, d, e, f, k, m, n. Тогда примером эйлерового цикла

может служить следующая последовательность:

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

5.10. Задача о коммивояжере

Коммивояжер (фр. commisvoyageur) — разъездной представитель

крупной торговой фирмы, предлагающий покупателям товары по образцам, каталогам, прейскурантам. В слове «коммивояжер» два ударения — на первый слог и на последний.

Задача о коммивояжере (о странствующем торговце согласно [24]) имеет две формулировки. В первой вопрос ставится следующим образом: «Коммивояжер желает посетить n определенных городов; как

он должен двигаться, чтобы заехать в каждый из них хотя бы один раз, проделав путь наименьшей общей длины?». Согласно этой формулировке коммивояжер может те или иные города посещать неоднократно. По второй же формулировке «он обязан побывать в каждом пункте в точности по одному разу и заинтересован затратить на поездку как можно меньше времени» [1, с. 47]. Мы в дальнейшем будем пользоваться второй формулировкой, но в предположении, что коммивояжер оптимизирует не время, а пройденный путь.

Öèêë 1-2-4-3-1: 120 + 180 + 110 + 70 = 480. Öèêë 1-2-3-4-1: 120 + 100 + 110 + 140 = 470. Öèêë 1-3-2-4-1: 70 + 100 + 180 + 140 = 490.

Таким образом, кратчайшим является путь 1-2-3-4-1.

5.11. Двудольные графы

Пусть множество V вершин некоторого графа G состоит из двух

непустых множеств V1 è V2 òàê, ÷òî V = V1 U V2 è V1 I V2 = Æ. Если каждое ребро графа G соединяет какую-либо вершину множества

V1 c одной из вершин множества V2, то такой граф называется дву-

дольным.

Пример двудольного графа приведен на рис. 5.28. В этом графе V = {1, 2, 3, 4, 5, 6, 7}; V1 = {1, 2, 3}; V2 = {4, 5, 6, 7}.

160

5.13. Деревья и лес

Термин «дерево» для особой разновидности графов ввел в 1857 г. английский математик Артур Кэли (1821–1895), с 1870 г. иностранный член-корреспондент Петербургской Академии наук.

Несвязный граф, не содержащий циклов, называется лесом. Связный граф, не содержащий циклов, называется деревом. На рис. 5.32 приведен трехкомпонентный лес. Первую компоненту образует дерево с вершинами 1, 2, 3, 4, вторую — 5, 6, 7, 8, 9, третью — 10, 11.

Приведем несколько теорем о деревьях.

Теорема 1. Всякое дерево содержит n − 1 ребер, где n — число

вершин.

Теорема 2. Всякий лес содержит n − k ребер, где k — число ком-

понент связности.

Теорема 3. Любые две вершины дерева соединены точно одной простой цепью.

Теорема 4. Если в дереве любые две вершины соединить ребром, то в графе появится один цикл.

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

Рассмотрим, например, граф, изображенный на рис. 5.33. Удалим из него ребра {1,4} и {3,4}. Получим остов, приведенный на рис. 5.34. Если из того же графа (рис. 5.33) удалить ребра {1,2} и {3,4}, то получим другой остов (рис. 5.35), и т.д.

Наименьшее число z, показывающее, сколько ребер необходимо

удалить из графа, чтобы получить его остов, называется цикломати- ческим числом графа. Если n — число вершин, m — число ребер, k — число компонент, то z = m − n + k.

В случае связного графа k = 1, следовательно, z = m − n + 1.