Основы дискретной математики В.А. Осипова (552659), страница 19

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 19)

При изображении неориентированного графа на плоскости элементам множества Ъ' соответствуют точки, а ребрам — линии без стрелок, соединяющие с<ютветствующие вершины. Пример 4.2. На рис. 4.2 изображен неориентированный граф с множеством вершин 1' = (и1) из, из, и41 и множеством ребер 1Е = ((и1, и21, (и1, изб, (из, изН. Неориентированные графы можно считать частными случаями ориентированных графов, соответствующих симметричным Рис.

4.2. бинарным отношениям, т. е. таким ориентированным графам, которые наряду с каждой дугой < и) у > содержат и дугу < у, и >. Ниже, каждый раз будем оговаривать, с каким типом графов — ориентированным или неориентировапным имеем дело в соответствующих рассмотрениях. Приведем примеры моделей и прикладных областей, в которых используются понятия и методы теории графов. 1. Модели организационных структур.

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

3. Модели обменных схем. Вершины графа — участники обменной схемы, дуги — потоки фшшнсовых или материальных ресурсов между ними. Обмелные схемы возникают при анализе и оптимизации таких явлений как взаимозачеты, бартер. 4. Транспортные задачи. Это класс задач, особенно часто встречающийся при планировании поставок, распределении товаров между потребителями и требующий оптимизации размещения пунктов производства и потребления, потоков грузов и др. Вершинами графа служат пункты размещения, дугами или ребрами — транспортные или 107 10б Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ 4Л, Ориентированные и иеориеитироваииые графы информационные маршруты. 5. Задачи сетевого планирования и управления.

Ориентированный граф является естественным средством описания и анализа сложных проектов, требующих выполнения большого числа взаимосвязанных операций (работ). Такие задачи календарно-сетевого планирования и управления заключаются в определении оптимальной последовательности выполнения операций и распределения ресурсов между ними. Критерием оптимальности являются время выполнения проекта, обьем затрат, степень риска и прочее. Рассмотрим ряд основных определений, связанных с понятием графа. Если < щ у > — дуга, то говорят, что она исходит из вершины и (ее начало) и заходит в вершину у 1ее конец).

Множество вершин, исходящих из вершины и обозначают Гщ т. е. Ги = 1у~ ( щ у >Е Г). Соответственно Г 1у = 1о~ < щ у >Е Е Г). Дуга называется инцидентной вершине и, если она заходит в и или исходит из нее. Дуга вида < щ и > называется петлей. Вершина, не имеющая инцидентных дуг называется изолированной. Две вершины называются амеэкными, если существует дуга, инцидентная им обоим. Степенью вершины называется число инцидентных ей дуг. В графе, изображенном на рис. 4.1 дуга < и1, иг > исходит из и1 и заходит в из, Ги1 = 1из, из), Гиз = Ф, дуга < и1, иг > инцидентна вершинам и1 и иг, вершина и4 — изолированная и степень ее равна нулю, степень вершины иг равна четырем, петель в этом графе нет. Подграфом называется часть графа, образованная подмножеством вершин вместе со всеми дугами, соединяющими веригины из этого л4ножества (только те, оба конца которых входят в подграф).

Подграф называется собствеыпым, если он отличен от самого графа. Два графа С =( Ъ", Г > и С' =< 1", Г > называются иэомор4нь ми, если существует биекция 7": "к' — Ро между множеством вершин, сохраняющая смежность, т. е. < щ у >Е Г 4=~ 4='г<,1'1и), 7'1у) >е Г. Заметим, что отношение изоморфизма на множестве ориентированных графов есть отношение эквивалентности. Последовательность дуг графа такая, что начало каждой последующей дуги совпадает с концом предыдущей называется путем. Длиной пути называется число входящих в него дуг, при- чем каждая дуга считается столько раз, сколько она встречалась в пути.

Путь обозначается упорядоченной последовательностью входящих в него вершин или дуг. Пример 4.3. Путь, изображенный на рис. 4.3 можно обозначить как < и1, иг >, < иг, из >, ( иг, и4 > или и1, из, из и4. Рис. 4.4. Рис. 4.3. Путь, у которого начало первой дуги совпадает с концом предпоследней, называется контуром. Путь 1контур) называется простым, если все его дуги различны. Путь 1контур) называется элементпарным, если все его вершины различны 1за исключением первой и последней). Пример 4.4.

В графе, изображенном на рис. 4.4 последовательность дуг < и1, иг >, < иг, из >, < из, и4 >, < и4, иг >, < из, и1 > — простой, но не элементарный контур. В дальнейшем часто будем использовать следующее утверждение. 'Утверждение 4.1. Иэ каждого пути, соединяющего вершины и и у моэюпо выделить простой путь, соединяющий эти вершинъи Доказательство проведем индукцией по числу и дуг пути.

При п = 1 утверждение очевидно. Пусть для всех путей, содержащих менее чем п дуг утверждение верно. Докажем его для путей с п дугами. Пусть последовательность вершин и1, иг, ..., и„+1, где и1 = щ и„.ъ1 = у — один из таких путей. Если все вершины этого пути различны, то он простой. В противном случае, некоторые две его вершины иг и ид совпадают. Если 4 = 1, то и1, и.ъ1, ..., и„.ъ1 — путь, соединяющий вершины и и у и содержащий и — 1 дугу; если ъ > 2, то таким путем 1ОО 108 Глава 4.

ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ 4.1. Ориентированные н неориентированные графы является путь ом оо, ..., оп ы о, ..., о„»ы По индуктивному предположению, из каждого из этих путей можно выделить простой путь, соединяющий вершину о и у. Для неориентированных графов используют те же термины «смежность», «изолированность», «инцидентность», «петля», «подграф», что и для неориентированных графов, и некоторые новые термины. Цепью в неориентированном графе С =< г', ч' > называется последовательность ребер, которая может быть превращена в путь введением соответствующей ориентации на ребра.

Длиной цепи называется число входящих в нее ребер, причем каждое ребро считается столько раз, сколько оно встречалось в цени. Цепь, у которой первая вершина совпадает с последней называется циклом. Цепь (цикл) называется простой, если в ней никакое ребро не встречается дважды. Цепь (цикл) называется элементарной, если все ее вершины (за исключением первой и последней) различны. По аналогии с утверждением 4.1 можно доказать, что из каждой цепи, соединяющей вершины о и у можно выделить простую цепь, соединяюшую эти вершины. Неориентированный граф С =< Ъ; Я > называется связным, если любая пара его вершин соединена цепью.

Компонентой связности графа С =< Ъ; Я > называется максимальный связный подграф (т. е. не являющийся собственным подграфом никакого другого связного подграфа С =< 1', Я >). Пример 4.5. На рис. 4.5, а,) изображен граф с тремя компонентами связности, указанными на рис.

4.5, б), в), г). 7 з и« 6 о! б) Рис. 4,5. в) г) Пусть С = (Ъ; «г) неориентированный граф с п вершинами т ребрами и р компонентами связности. Тогда число у(С) = = тп — и+р называется цикломатическим числом графи С. Если С связный граф, то р = 1 и у(С) = т — и + 1.

В неориентированном графе можно определить понятие расстояния д(о, у) между вершинами о и у, считая его равным числу ребер в кратчайшей простой цепи, соединяющей вершины о и у, и положив й(о, у) = со, если такой цепи пет. Расстояние и(о, у) удовлетворяет аксиомам метрики: 1, д(о, у) > О и д(о, у) = О тогда и только тогда, когда вершины о и у совпадают. 2. д(о, у) = д(у, о). 3. д(о у) + д(у и) > д(о, г). Заметим, что если попытаться аналогично определить гюнятие расстояния в ориентированном графе, то не вьшолнится аксиома 2. В ориентированном графе С =( 1г, Г > с множеством вершин Ъ' = (о~., ог, ..., о„) вершина оу называется достижимой из вершины о;, если существует путь из о; в о .

Граф называется односторонне связным, если для любых двух его вершин по крайней мере одна достижима нз другой. Если одновременно каждая вершина о; достижима из о и о достижима нз о;, то граф называется сильно связным. Компонентой односторонней связности (сильной связности) называется максимальный односторонне связный (сильно связный) подграф данного графа.

Для иллюстрации понятия сильной связности рассмотрим следующую задачу. Пусть граф С =( 1г, Г > представляет структуру руководства или «влияний» в некоторой организации. Требуется выделить множество сотрудников, которые имеют равную власть или оказывают равное влияние друг на друга (например, составляют комитет). Если множество 1' вершин графа — это множество сотрудников данной организации, и две верши~ы о и у соединены дугой < о, у > тогда и только тогда, когда о имеет влияние на у, то множество сотрудников, имеющих равное влияние — это элементы одной компоненты сильной связности.

Характеристики

Список файлов книги