ivanstudent

Путь к Файлу: /Дискретная математика. Часть 2 / 189 / 4.DOC

Ознакомиться или скачать весь учебный материал данного пользователя
Скачиваний:   1
Пользователь:   ivanstudent
Добавлен:   24.12.2014
Размер:   753.0 КБ
СКАЧАТЬ

Метрика однозначно определяет обыкновенный граф  и соответственно скелет графа общего вида. Вершина х0 называется центральной, если

"xÎx[maxyÎx r(x,y)³ maxyÎx r(x0,y)],

 

и переферийной, если

 

"xÎx[maxyÎx r(x,y)£ maxyÎx r(x0,y)].

Величина

4

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

4

диаметром графа.

 

 

Пример 3.2.1.  У графа, изображённого на рисунке 3.3.1 вершины Х4 и

Х10 - центральные, вершины Х17813 - периферийные, r(L)=4; d(L)=7

 

              X1                        X9   X8    X7   X6   X5                          X13

4

               X                       X3           X4             X10         X11      X12          

 

Рис. 3.3.1   

 

3.4. Обходы графа

 

Рассматривается класс задач связанных с определением маршрутов специального вида.

Цепь  X0U1X1U2X2...Xl-1UlXl  в графе L=(X,U,P) называется эйлеровой цепью, если множество её рёбер совпадает с U; при Х0l имеем эйлеров цикл.

Пример 3.4.1. Можно ли нарисовать графы, изображённые на рисунке 3.3.1.не отрывая пера от бумаги и не проходя по уже нарисованным линиям вторично?

 

 

 

4

 

  а)                                                                б)

Рис. 3.4.1

 

Пример 3.4.2. Через город Калининград протекает река, омывающая острова. Имеется семь мостов (рис. 3.4.2). Можно ли обойти все мосты, проходя по каждому из них только один раз?

                                

4              4

 

 

Рис. 3.4.2

 

4Теорема Эйлера (критерий существования эйлеровой цепи). Пусть X и Y- две вершины (не обязательно различные) связного графа L=(X,U,P). Для существования в L эйлеровой цепи, ведущей из X  в Y необходимо и достаточно, чтобы все отличные от X и Y  вершины L обладали чётными валентностями (число усиков при вершине), а валентности вершины X и Y в случае X=Y были не чётными.

Доказательство.  

Необходимость условий теоремы очевидна, так как если в графе существует эйлерова цепь, то нечётной валентностью могут обладать только начальная и конечная вершина (если они не совпадают), поэтому число вершин нечётной валентности равно 0 или 2.

Доказательство достаточности проводим по индукции по числу рёбер графа m(L).

Теперь легко убедиться, что решением примера 3.4.1 для графа на рисунке 3.4.1б) является цепь 4, а для графов на рисунке 3.4.1.а) и рисунке 3.4.2. задача не разрешима.

Простая цепь 4xc графа L=(x,U,p), содержащая все его вершины и только по одному разу, называется  гамильтоновой цепью; при Хо=Хс имеем гамильтоновый цикл.

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

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

Известны следующие достаточные условия существования гамильтоновой цепи и гамильтонового цикла:

1. Если для любых двух несмежных различных вершин Х и Y связного обыкновенного графа L4

4,

то существует гамильтонов цикл;

2. Если

4,

то существует гамильтоновая цепь;

3. Если                                              

4,

то существует гамильтонов цикл.

3.4.1. Алгоритм Флёри нахождения эйлерова цикла

Рассматривая связный граф, все вершины которого удовлетворяют условиям теоремы  Эйлера.

Строим эйлеровый цикл одним росчерком, придерживаясь следующих правил:

1.Отправляемся из произвольной вершины 4; каждое пройденное ребро      зачёркиваем;

2. В процессе построения не прибегаем к исправлению уже построенной части траектории;

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

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

Действительно, если  построен маршрут до вершины Х, то в оставшемся суграфе (из не зачёркнутых рёбер) имеются две вершины нечётной валентности; Х и 4 и в силу теоремы Эйлера имеется эйлеровая цепь, начинающаяся из Х.

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

3.4.2.  Цикломатическое число

Цикломатическое число 4 графа L(X,U,P) равно 4, где n(L)=|X|,   m(L)=U,  а  4(L) - число компонент связности.

Пример 3.1.4.

4                                                                         n = 4 ; m = 3,

 

                                                                           4 = 1; 4.  

 

 

 

Рис. 3.4.3

Рассмотрим ряд свойств цикломатического числа.

Пусть L’=(X,U\{U},P)  -суграф, полученный из L удалением ребра U , то

4.

Так как n(L’)=n(L) и m(L’)=m(L)-1 , то

4.

 

Пусть Е = L = (X,4,P)  т.е. пустой граф;

n(L) = n , m(L) = 0 , 4(E) = n , то 4(E) = 0.

Следовательно4(L)40 , где L произвольный граф т.к. при удалении m(L) рёбер 4(L) = 0 может только уменьшиться у произвольного графа 4(L) = 0 тогда и только тогда, когда все удаляемые рёбра перешейки, т.е. L  не содержат циклов.

Теорема. Если 4компоненты связности графа L , то     4.

 Доказательство.

4

3.5. Графы без циклов

 

Рассматриваются графы с нулевым хроматическим числом.

Теорема.  Следующие высказывания равносильны:

- граф L не содержит циклов;

- граф L не содержит простых циклов;

- никакие две вершины X и Y  в указанном порядке не могут соединяться более чем одной цепью.

Связаный граф, не содержащий циклов, называется  деревом.

Дерево обладает следующими свойствами:

1. 4

2. 4

3. Для любой пары вершин X и Y в указанном порядке существует не более чем одна соединяющая их цепь;

4. 4, но если из L удалить любое ребро, то для полученного графа L- 4

5. 4, но если к L добавить хоть одно ребро, то для полученного графа L+ 4.

Теорема. Из любого графа L можно удалить 4 рёбер, чтобы полученный суграф T не имел циклов и обладал тем же числом компонент связности, что и  L. Всякий же суграф, получаемый удалением менее чем 4 рёбер, содержит циклы.

Доказательство.  Первое утверждение при 4 тривиально. Пусть теорема доказана для всех графов с цикломатическим числом 4 и рассмотрим произвольный граф L, у которого 4, так как 4, то граф заведомо содержит цикловые рёбра; удалив любое из них получим L’ с 4. Согласно предположению индукции можно удалить 4 рёбер так, чтобы остался граф T  без циклов с 4тот же T получен из исходного графа L  удалением 4 ребра, причём 4, что и требовалось доказать.

Второе утверждение справедливо потому, что при удалении любого ребра 4 не может уменьшиться более чем на единицу.

Всякий суграф T  графа L удовлетворяющий условиям 4, 4, 4 называется каркасом графа. Рёбра графа L, не принадлежащие его каркасу T  называются хордами каркаса T и L. Число рёбер каждого из каркасов графа L называется рангом 4 этого графа и обозначается через  4.

Если граф связан, то всякий его каркас является деревом.

Теорема. Каковы бы ни были каркас T  графа  4 и хорда U этого каркаса,  в L существует цикл, содержащий и не содержащий других хорд каркаса T; причём этот цикл простой и только один.

Доказательство.  Пусть X и Y  вершины графа L, соединённые ребром U, а T ‘ - та компонента каркаса T , что содержит эти вершины. Так как T ‘ - дерево,  то в нём имеется одна и только одна простая цепь, соединяющая X с Y, и эта цепь вместе с ребром U образует искомый цикл, который называется простым и единственным.

Эта теорема позволяет получать одни каркасы из других. Пусть T  - искомый каркас L,  а U - какая-то хорда этого каркаса (не петля). Добавить в T  ребро U,  выявим цикл, содержащий U, и исключим из него какое-то другое ребро (не U).

Таким образом, можно получить все каркасы графа.

3.5.1. Алгоритм Степанеца, Влэдуца нахождения каркаса графа

Алгоритм основан на использовании разметки вершин, применяемой при нахождении кратчайшей цепи.

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

Окончив разметку, просматриваем вершины графа и удаляем рёбра по следующему правилу. Если мы находимся в вершине X с меткой 4, то удаляем рёбра, которые соединяют X с вершинами, имеющими метку 4, а из рёбер, соединяющих X с вершинами с меткой 4-1 сохраняем одно, удаляя все остальные.

Пример 3.5.1. На примере графа на рисунок 3.4.1. рёбра каркаса T изображены жирными линиями; вершины просматривались в алфавитном порядке.

4

3.5.2. Анализ цикломатических свойств графа по матрице

          инциденций

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

Пример 3.5.2.

44        a                 2                   b

                  5               6        

     1                                           3

                 8                7

                           4   

             d                                            c

 

Теорема.  Система S некоторых столбцов матрицы инциденций AL  графа L линейно независима тогда и только тогда, когда суграф T S , порождённый множеством тех рёбер графа L, которые соответствуют столбцам S, не содержит циклов.

Следствие 1. Ранг 4 матрицы инциденций AL равен рангу графа L.

Действительно, из графа L всегда можно удалить 4 рёбер, чтобы оставшемуся суграфу L’  отвечали линейно независимые столбцы матрицы AL, поэтому 4. С другой стороны, всякий суграф, получаемый из L  удалением менее чем 4 рёбер, обладает циклами, поэтому система более чем из 4 столбцов матрицы AL всегда линейно зависима, откуда  4.

Следствие.  Система S из 4 столбцов матрицы AL линейно независима тогда и только тогда, когда соответствующий суграф T S является каркасом графа L.

Действительно, высказывание о линейной независимости в данном случае равносильно высказыванию 4, т.е. вместе с 4, высказыванию 4, означающему, что T S  - каркас графа L.

3.5.3. Определение числа каркасов

Пусть дан граф 4, где 4

Образуем квадратную матрицу

44                    2S(X1)-V(X1)-S(X1X2)- ....-S(X1Xn)

Sn=4=    -S(X1X2)+2S(X2)-V(X2) - .... - S(X2Xn)

                    ........             .........               ........

                    -S(XnX2)-S(XnX2) - .... - 2S(Xn)-V(Xn)

в которой каждый диагональный элемент Sij выражает количество петель графа L  инцидентных вершине Xi, а элемент Sij при 4 равен взятому со знаком минус числу рёбер, соединяющих вершины Xi и Xj .

Теорема Лантьера-Трента.  Пусть 4 - некоторый главный минор порядка 4  матрицы SL , полученный вычёркиванием 4 строк и такого же количества одноимённых столбцов. Если вычеркнутые ряды соответствуют вершинам графа L, взятым по одной из каждой его компоненты связности, то  4 равен числу различных каркасов графа L; в остальных случаях 4=0.

Если граф L связан, то 4 и искомое число каркасов равно любому из главных миноров n-1 -го порядка матрицы SL (т.е. вычеркнута может быть любая строка и столбец матрицы SL).

 

 

 

4. ОРИЕНТИРОВАННЫЕ ГРАФЫ

 

4.1. Маршруты на ориентированном графе

Если в определении маршрута X0U1X1U2X2...Xl-1UlXl  графа 4 заменить требование истинности высказывания   4 более жёстким требованиям истинности4, то получится определение  частично ориентированного маршрута из вершины Х0 в вершину ХL понятия частично ориентируемого цикла возникают автоматически.

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

9

 
4Пример 4.1.1. В графе на рисунке.4.1.1  маршруты а1 а4 в9 с1 а3 в9 с6 а  (циклический) являются частично         ориентированным, но не маршрутами,  а    в9 с8 в9 с (циклический) суть   ормаршрут; маршрут  а3 в9 с8 в есть орцепь (не простая), а   а3 в9 с6 -простая орцепь;  маршрут в9 с8 в -простой орцикл.

                          Рис .4.1.1

Для нахождения количества частично ориентированных маршрутов заданной длины l из i-ой в j-ую вершину графа L  по его матрице смежности R достаточно на образующие полукольца K наложить соотношения

4            

тогда искомое количество маршрутов будет равно элементу 4матрицы 4.

Аналогично подсчитываются маршруты, если К подчинить условиям

4,                                                                             

а чтобы посчитать частично ориентированные маршруты без звеньев надо положить

4   

Так, для графа на рис. 4.1.1 в первом случае имеем:

 

4

во втором:

4

в третьем:

           4 

Если мы интересуемся лишь наличием или отсутствием маршрутов данной длины, а не их количеством, мы можем наложить на полу кольцо К дополнительное соотношение  2=1.

Для нахождения кратчайших орцепей из вершины Х в вершину модифицируем алгоритм разметки вершин с целью учёта ориентации: очередной значок получает не просто смежные с рассматриваемой вершины, а лишь те, в которые из неё идут дуги.

Пусть X0U1X1U2X2...Xl-1UlXl  в орграфе L=(X,U,P), содержащий все рёбра, называется эйлеровым путём; при Х0l имеем эйлеровый циклический путь.

Вводя числа 

V+(X)=S+(X)+S0(X)

                                                    V-(X)=S-(X)+S0(X),                                                                                                                            называемые соответственно полувалентностью исхода и полувалентностью захода вершины Х , можно сформулировать следующий критерий.

Теорема.  Для существования эйлерова пути из вершины Х0 в вершину Y0 связного орграфа L необходимо и достаточно выполнение условий

4

Гамильтоновым путём (гамильтоновым орциклом) орграфа L называется простой путь (простой орцикл), содержащий все вершины L .

4.1.1. Транзитивные и квазитранзитивные графы

Граф L=(X,U,P) называется транзитивным, если

 

4

 и квазитранзитивным, если

4.

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

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

Из определения имеем:

- всякий подграф (не суграф!) транзитивного (квазитранзитивного) графа является транзитивным (квазитранзитивным);

- если квазитранзитивный граф содержит звено или пару противоположных дуг, то при каждой из двух вершин, инцидентных этому звену (этой паре дуг), имеется хотя бы одна петля;

- если транзитивный граф содержит циклический частично ориентированный маршрут длины 42, то при каждой вершине этого маршрута есть хотя бы одна петля. Из определения подграфа для доказательства второго достаточно в определении квазитранзитивности положить Х=Z, последовательное применение определения транзитивности даёт третье утверждение.

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

4

т.е. элементы матрицы смежности графа принадлежат В{0,1}.

Теорема. Пусть L=(X,U,P)- граф с упорядоченным множеством вершин Х, а  R его матрица смежности  В. Тогда необходимым и достаточным условием транзитивности графа является R=R2=R , а условием квазитранзитивности  R+RT+R2=R+RT

Доказательство.  Если rij=1, т.е. хоть одна дуга или звено, соединяющие Хi и Xj, а при Хi и Xj - петля, то истинно4.Элемент  4 в том и только в том случае, если из Xi в Xj ведёт некоторый частично ориентированный маршрут длины 2, т.е. есть ХК, что истинно 4; но при транзитивности графа и только тогда это и только это высказывание влечёт за собой истинность 4, т.е. равенство rij=1, какими бы не были Хi и Xj. Значит L транзитивен в том и только в том случае, если матрица R2 поглощается матрицей R , т.е. если R+R2=R.

Аналогично доказывается второе утверждение теоремы.

4.1.2. Транзитивное замыкание

Транзитивным замыканием графа L=(X,U,P) называется его минимальный транзитивный сверхграф, т.е. такой граф N=(X,V,P), что

N - есть сверхграф для  L;

N - транзитивный граф;

P - не существует транзитивного сверхграфа N’=(X’,V’,P) графа L, у которого4

Транзитивное замыкание N=(X,V,P) графа L называется  экономным, если множество V\U не содержит звеньев.

Пример 4.1.3.

4

                L                              N1                                     N2

Рис. 4.1.2

Транзитивное замыкание N1, графа L экономное N2-не экономное (перестраховка).

Теорема. Всякий граф обладает одним и только одним экономным транзитивным.

Экономное транзитивное замыкание графа может быть построено по его матрице смежности R на В{0,1}.

Пусть матрица смежности над В{0,1} экономного транзитивного замыканий. В любом транзитивном замыкании N=(X,V,P) вместе с каждым частично ориентированным маршрутом X0V1X1... Xi-1VlXl(S) - должна быть дуга из X0BKl. Следовательно, матрица S должна поглощать все степени матрицы R, т.е. поглощать сумму 

R+R2+...+Rl+1=R(E+R)l.

При некотором l

Наверх страницы

Внимание! Не забудьте ознакомиться с остальными документами данного пользователя!

Соседние файлы в текущем каталоге:

На сайте уже 21970 файлов общим размером 9.9 ГБ.

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

Не нашли нужный документ? Воспользуйтесь поиском по содержимому всех файлов сайта:



Каждый день, проснувшись по утру, заходи на obmendoc.ru

Товарищ, не ленись - делись файлами и новому учись!

Яндекс.Метрика