Вершинная и реберная связность

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

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

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

Рис. 1. Пример графов для иллюстрации понятия связности

Вершинную связность графа k(G)определяют как наименьшее ко­личество вершин, удаление которых нарушает связность графа. Для пол­ных графов k(К_n )= n – 1, для несвязных графов - k(G) = 0 .

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

Блок - это связный граф, не имеющий точек сочленения.

Реберную связность λ(G) определяют как наименьшее число ребер, удаление которых нарушает связность. Несвязный граф имеет λ(G) = 0 , для полных графов λ(К_п) = п – 1.

Мост - это ребро, удаление которого приводит к увеличению числа компонент связности. Для графа, имеющего мост λ(G) = 1.

Граф G называют k-связным, если k(G) > k, и реберно k-связным, если λ(G)>k.

Теорема 1.Для любого графа G верны неравенства k(G) < λ(G) < d(G), где d(G) - минимальное значение степени вершин графа.

Например, на рис. 2 приведены граф и его блоки.

Рис. 2. Пример графа и его блоков

Таким образом, точками сочленения являются вершины с номерами 4, 5 и 7. Последние два блока являются полными графами К₂. Это един­ственные блоки, не являющиеся 2-связными. Заметим, что точка сочлене­ния входит во все блоки, с которыми она связана.

Пути и маршруты в графах

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

Рассмотрим задачу пересчета путей и маршрутов.

Следует отметить, что задача определения числа путей (маршру­тов) длины 2 между всеми парами вершин графа может быть решена простым возведением в квадрат его матрицы смежности. Аналогично, количество маршрутов длины 3 может быть получено из матрицы A³ и вообще количество маршрутов длины l между вершинами v_i и v_j равно соответствующему элементу матриц A^l. Наконец количество маршрутов длиной не более p между всеми парами вершин определяется как сумма

Пример. В качестве примера приведем решение задачи пересчета маршрутов графа, приведенного ниже при l=1,2,3,4.

Рис. 1.

Информацию о путях в одну дугу для графа изображенного на рис. 1 несет матрица смежности А, остальные матрица получаем простым умножением:

Непосредственной проверкой по изображению графа убеждаемся, что, например, между cиe есть

1 маршрут (путь) длины 2: c→b→e;

1 маршрут длины 3: c→e→c→e;

4 маршрута длины 4: c→b→e→c→e, c→b→d→c→e, e→a→b→e→c,

e→c→b→d→c.

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

1. Отличные от нуля диагональные элементы матриц указывают на присутствие в графе соответствующего количества циклов длины l. Например, в матрице A³ диагональный элемент . Это значит, что в графе есть три цикла длины 3, включающие вершину b. Непосредственно по рисунку находим: b→d→c→b, b→e→c→b и b→e→a→b.

2. Поскольку длина пути в графе не может превышать
n—1,не имеет смысла возводить A в более высокую степень

Перечисление маршрутов и путей

Матричный подход, использованный в предыдущих разделах, легко адаптируется к задаче о перечислении маршрутов

Пусть - матрица всех маршрутов с l промежуточны­ми вершинами (длины l+1), элементы которой определяются как

где v_kl это l-япо порядку промежуточная вершина маршрута связывающего v_i и v_j, a q - ко­личество таких маршрутов. Если маршрутов длины l+1 меж­ду v_i и v_j нет, то . Слагаемые v_k1 v_k2 … v_kl представляют собой "произведения" вершин, лежащих на некотором маршруте между v_i и v_j. Их можно рассматривать как размещения без повторений или с повторениями из n элементов по l в зависимости от того, является маршрут путем или нет

Например, для графа на рис. 4. и значит из v_i в v_j есть три маршрута: c→b→e→a→d, c→e→a→b→d и c→e→c→b→d, два из которых являются путями, так как не содержат повторяющихся вершин. В наличии указанных маршрутов легко убедиться непосредственно по графу, а их количество равно значению элемента в матриц A⁴. Кроме P^(l), используем вспомогательную матриц , в которой элемент равен v_j, если в графе есть дуга v_iv_j, и 0, еcли дуга отсутствует. Поскольку j-столбец P^(l-1) отражает все маршруты длины l, с началом в v_k (k=1,2,…,n)и концом в v_j, а i-строка - концы всех дуг вида v_iv_k (k=1,2,…,n), то сумма

,

отражает все маршруты из v_i в v_j длины l+1. Следовательно, матрица маршрутов P^(l)может быть получе­на как х P^(l-1), при этом сомножители в произведениях не переупорядочиваются и не используется степенная запись повторяющихся сомножителей, чтобы не потерять инфор­мацию о порядке следования вершин. Таким образом, может быть сформирован ряд матриц P⁽¹⁾, P⁽²⁾, P⁽³⁾, ..., P^(q-1), в совокупности определяющих все маршруты длины не больше q для любой пары вершин.

В качестве примера выполним расчеты для графа, предс­тавленного на рис. 1 используя соотношения:

P⁽¹⁾= P⁽⁰⁾, P⁽²⁾= P⁽¹⁾, P⁽³⁾ = P⁽²⁾.

За матрицу P⁽⁰⁾ (пути без промежуточных вершин), необхо­димую для получения P⁽¹⁾, примем матрицу смежности.

Наконец для P⁽³⁾ = P⁽²⁾ матрица принимает вид

	a	b	c	d	e
a	dce	bea+bdc+bec	dce	bea+dcb	dcb+bdc+bec
b	dce+ece	0	ead+dce+ece	eab+dcb+ecb	eab+dcb+ecb
c	ece	bea+bdc+bec	ead+ece	bea+eab+ecb	eab+ecb+ +bdc+bec
d	cbe	cea+cec	cbd+cbe	cea	cec
e	abe+cbe	cea+adc+cec	abd+cbd+ +abe+cbe	cea	adc+cec

К видно из примера, уже при небольших значениях l матрицы могут быть весьма громоздкими. Однако, если цель поиска - пути, объем вычислений можно существенно умень­шить, отбрасывая произведения с повторяющимися вершина­ми. Очевидно также, что в этом случае l ≤ (n—2), так как путь в графе не может содержать более чем n—2 промежуточных вершин. Кроме того, с увеличением длины количество путей в общем случае должно сокращаться.

Задача Гамильтона

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

Владелец фабрики принял предложение Гамильтона и выплатил ему 25 гиней.

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

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

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

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

С этой задачей тесно связана проблема моряка, часто называемая так­же задачей о странствующем торговце (коммивояжере), который должен посетить определенный набор городов и вернуться домой как можно скорее. Довольно большой пример определения замкнутой воздушной линии, соединяющей столицы 48 штатов США и имеющей наименьшую возможную длину, был просчитан до конца.

Интересно отметить, что обе эти разделенные более чем столетием задачи являются оптимизационными.

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

Примеры приложений теории графов

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

1. «Транспортные» задачи, в которых вершинами графа являются пункты, а ребрами – дороги (автомобильные, железные и др.) и/или другие транспортные (например, авиационные) маршруты. Другой пример – сети снабжения (энергоснабжения, газоснабжения, снабжения товарами и т.д.), в которых вершинами являются пункты производства и потребления, а ребрами – возможные маршруты перемещения (линии электропередач, газопроводы, дороги и т.д.). Соответствующий класс задач оптимизации потоков грузов, размещения пунктов производства и потребления и т.д., иногда называется задачами обеспечения или задачами о размещении. Их подклассом являются задачи о грузоперевозках [5, 8, 20].

2. Задача о спросе и предложении. Оптовый торговец в каждый из N последо­вательных интервалов может покупать, продавать и хранить (чтобы продать позже) некоторый товар. Причем в каждый i период задаются: верхняя граница а_i- коли­чества товара, больше которого торговец купить не может: верхняя граница С_j-количества товара, которое он может хранить, и нижняя граница b_i количества товара, которое он может продать. Заданы стоимости покупки, продажи и храпе­ния is каждый 1-й период. Требуется определить оптимальную стратегию торговца, при которой он получит максимальную прибыль за N периодов.

3. Задача об оптимальном использовании дорог. Из различных городов Xi (i= 1, 2, ..., n) в пункт назначения у отправляются машины (при заданном начальном количестве a_i- машин в пункте x_i). Заданы продолжительности t_ijдвижения автомобплей по дорогам между пунктами x_iи х_j, максимальное ко­личество машин Cij, которое может пропустить эта дорога; максимальное коли­честв) машин Сii, которое может находиться в пункте хi. Требуется составить оптимальный план движения автомобилей таким образом, чтобы в течение вре­мен Т в пункт назначения у прибыло максимальное число автомашин.

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

Требуется найти путь, соединяющий начальною и конечную точки, суммар­ная стоимость проезда, по которому была бы минимальна.

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

6. Задача о складе. Пусть задана емкость склада: количество товара, помещен­ное вначале; цены на товары, покупаемые и продаваемые в каждый i-й период времени, и расходы в этот период, связанные с храпением единицы товара. Тре­буется определить оптимальные количества товара, которые должны быть куп-лены и проданы в разные периоды времени таким образом, чтобы суммарная прибыль за N периодов была максимальна. Причем считается, что количества товара па складе в начале и в конце процесса купли — продажи равны между собой.

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

8. Задача об оптимальном по стоимости сетевом графике. Задай сетевой график работы с общей продолжительностью t_n. Считаем, что для каждой работы, которая представляется дугой, зависимость ее стоимости от продолжительности линейна. Требуется минимизировать полную стоимость проекта при заданной общей про­должительности работ.

9. «Технологические задачи», в которых вершины отражают производственные элементы (заводы, цеха, станки и т.д.), а дуги – потоки сырья, материалов и продукции между ними, заключаются в определении оптимальной загрузки производственных элементов и обеспечивающих эту загрузку потоков [15, 20, 24].

10. Обменные схемы, являющиеся моделями таких явлений как бартер, взаимозачеты и т.д. Вершины графа при этом описывают участников обменной схемы (цепочки), а дуги – потоки материальных и финансовых ресурсов между ними. Задача заключается в определении цепочки обменов, оптимальной с точки зрения, например, организатора обмена и согласованной с интересами участников цепочки и существующими ограничениями [7, 12, 18].

11. Управление проектамиУправление проектами – раздел теории управления, изучающий методы и механизмы управления изменениями (проектом называется целенаправленное изменение некоторой системы, осуществляемое в рамках ограничений на время и используемые ресурсы; характерной чертой любого проекта является его уникальность, то есть нерегулярность соответствующих изменений). С точки зрения теории графов проект – совокупность операций и зависимостей между ними (сетевой график - см. ниже). Хрестоматийным примером является проект строительства некоторого объекта. Совокупность моделей и методов, использующих язык и результаты теории графов и ориентированных на решение задач управления проектами, получила название календарно-сетевого планирования и управления (КСПУ). В рамках КСПУ решаются задачи определения последовательности выполнения операций и распределения ресурсов между ними, оптимальных с точки зрения тех или иных критериев (времени выполнения проекта, затрат, риска и др.).

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

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

Понятие дерева

Важный класс графов составляют графы, называемые деревьями. Дерево — это связный граф, который вовсе не имеет замкнутых путей (рис. 7).

Этот граф обладает следующим оптимальным свойством: среди всех связных графов с данным числом вершин дерево имеет наименьшее число ребер, а именно: число n вершин дерева и число m его ребер различаются на единицу

m = n - 1. (3)

Рис. 7

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

Это можно сделать, например, так. Пометим произвольную вершину графа, выберем какое-нибудь исходящее из нее ребро графа и пометим вершину, в которую это выбранное ребро входит. Если пара помеченных вершин не исчерпывает множества всех вершин графа, выбираем ребро графа, выходящее из одной из двух этих вершин в какую-нибудь третью непомеченную вершину этого графа, и помечаем ее. В случае если полу­ченная тройка помеченных вершин не исчерпывает множества всех вер­шин графа, выбираем ребро графа, выходящее из одной из трех этих вершин в какую-нибудь четвертую непомеченную вершину этого графа, и помечаем ее. Продолжая описанную процедуру далее, мы неизбежно придем к ситуации, когда все вершины заданного графа окажутся помеченными. Напомним, что число вершин графа конечно, и если оно равно п, то потребуется ровно п — 1 шаг, на каждом из которых (кроме первого) помечается ровно одна новая (непомеченная) вершина графа. Множество выбранных ребер и помеченных вершин будет искомым де­ревом.

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

На рис. 8 последовательно (шаг за шагом) показано построение по­рождающего дерева для графа с семью вершинами.

Рис.8

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

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

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