Дискретная Математика. Учебное пособие Допущено научнометодическим советом по математике вузов СевероЗапада в качестве учебного пособия для студентов вузов, обучающихся по специальностям 220200
 Скачать 6.37 Mb.
|
|
3.6. Упорядочивание дуг и вершин орграфа Расчеты в задачах, связанных с графами, заметно упрощаются, если их элементы упорядочены. Под упорядочиванием вершин связного орграфа без контуров, то есть циклических цепей понимают такое разбиение его вершин на группы, при котором: 1) вершины первой группы не имеют предшествующих вершин, а вершины последней группы последующих; 2) вершины любой другой группы не имеют предшествующих в следующей группе; 3) вершины одной и той же группы дугами не соединяются. Такое разбиение всегда возможно. В результате подобного упорядочивания получается граф, изоморфный исходному графу. Упорядочивание элементов выполняется графическим или матричным способом. Графический способ носит название алгоритма Фалкерсона и состоит из следующих шагов. 1. Находят вершины графа, в которые не входит ни одна дуга. Они образуют первую группу. Нумеруют вершины группы в произвольном порядке. Рей Фалкерсон (???? - ????) – американский математик. 60 2. Вычеркивают все пронумерованные вершины и дуги, из них исходящие. В получившемся графе найдется, по крайней мере, одна вершина, в которую не входит ни одна дуга. Этой вершине, входящей во вторую группу, присваивают очередной номер и так далее. Второй шаг повторяется до тех пор, пока не будут упорядочены все вершины. Аналогичным образом упорядочиваются дуги орграфа. Рассмотрим несколько примеров. Упорядочим вершины графа изображенного слева. На рисунке графа вершина B не со- держит входящих дуг, отнесем ее к первой группе. Вычер- B киваем все дуги, исходящие из B . Получим следующий D граф ( см. рис. 3.16). В нем опять находим одну вершину, C в которую не заходит ни одна дуга. Это вершина D . Вы- A A черкиваем дуги, исходящие из D . Появится еще одна E вершина – вершина E , в которую не заходит ни одна ду- га. После вычеркивания дуг EC и EA получим вершину Рис. 3.16 а) A , которая входит, таким образом, в четвертую группу, а вершина C - в пятую. Изоморфный граф с упорядочен- B B D C D C A A E E Рис. 3.16 б). ными вершинами изображен на рисунке 3.17. В данном примере в каждую группу входит то- E лько по одной вершине. Однако в общем случае в каждую такую группу могут входить несколько B D C вершин, если граф большой и содержит много вершин. A Упорядочим теперь вершины этого графа матричным способом. Для этого составим матри- цу смежности вершин P . Вычислим компоненты 1-я 2-я 3-я 4-я 5-я группа вектора 5 1 1 i i x P v , представляющие собой по- Рис. 3.17. лустепени захода вершин графа. Для орграфов различают полустепень захода i x P вершины i x (количество дуг, заходящих в i x ) и полустепень выхода i x P (количество дуг, исходящих из i x ). Полустепень захода вершины B 0 0 1 0 1 1 0 1 0 0 0 0 0 0 0 1 1 1 0 1 0 0 1 0 0 E D C B A E D C B A P оказалась равной нулю. Это значит, что в эту вершину не заходит ни одна дуга, и вершина B образует первую группу. Исключим из рассмотрения вершину B и дуги, из нее исходящие, вычеркнув соответствующую строку матрицы P . Затем вычислим компоненты вектора A B C D E 1 v 2 0 4 1 2 2 v 1 - 3 0 1 3 v 1 - 2 - 0 4 v 0 - 1 - - 5 v - - 0 - - Группа 4 1 5 2 3 61 B v v v 1 2 . Нулевая компонента теперь будет соответствовать вершине D , т. е. вершина D образует вторую группу. Так продолжается до получения вектора i v , у которого будет часть только нулевых компонент, а остальные вычеркнуты. В нашем случае это вектор 5 v и вершина C , которая образует последнюю пятую группу. При упорядочивании дуг получается та же картина, а сами дуги нумеруются подобным же образом. Используем опять граф, изображенный на рис. 3.16 а). 1. Найдем дуги, не имеющие непосредственно предшествующих дуг (они образуют первую группу). 2. Вычеркнем найденные дуги. После этого найдется, по крайней мере, одна новая дуга, не имеющая непосредственно предшествующей (в графе без дуг первой группы). Эти дуги составят вторую группу. Второй шаг повторяется до тех пор, пока все дуги не будут разбиты на группы. На рисунке 3.18 изображен граф с упорядоченными по описанному алгоритму дугами. Штрихованными линиями показаны связи между дугами, существующие в исходном орграфе. B C D C B D E C D E A C B E E A B A Рис. 3.18. 3.7. Выявление маршрутов с заданным количеством ребер С помощью матрицы смежности вершин можно найти все маршруты, содержащие заданное количество ребер (дуг). Справедлива следующая теорема. Теорема 3.7. Для определения количества маршрутов, состоящих из k ребер (дуг), необходимо возвести в k -ю степень матрицу смежности вершин. Тогда элемент k ij p даст количество маршрутов длины k (состоящих из k ребер) из вершины i x в вершину j x . Пример 1. Рассмотрим неориентированный граф, изображенный на рис. 3.19. Соста- B вим матрицу смежности вершин и возведем ее в квадрат. Результат возведения изображен прямо под графом. Рассмотрим первую 1 u 5 u строку. Элемент 3 2 11 p Это значит, что существуют три марш- A 2 u рута из A в A длиной два ребра. Действительно, это маршруты 3 u 4 u C , , 3 3 2 2 1 1 A Du Au A Cu Au A Bu Au Из A в B существуют два маршру- D 6 u та: , 4 3 5 2 B Du Au B Cu Au Если использовать числовую матрицу сме- Рис. 3.19. 3 2 2 2 2 3 2 2 2 2 3 2 2 2 2 3 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 жности вершин, то для нахождения самих маршрутов необходимо работать с графом. Если же воспользоваться модифицированной матрицей смежности, в ячейки которой записаны названия ребер, то можно получить не только количество маршрутов, но и сами маршруты. Действительно, для данного примера имеем 62 0 0 0 0 0 0 0 0 6 4 3 6 5 2 4 5 1 3 2 1 6 4 3 6 5 2 4 5 1 3 2 1 u u u u u u u u u u u u u u u u u u u u u u u u 6 6 4 4 3 3 5 4 2 3 6 5 1 3 6 2 1 4 4 5 3 2 6 6 5 5 2 2 4 6 2 1 3 6 1 5 6 5 3 1 6 4 2 1 4 4 5 5 1 1 3 4 2 5 6 2 4 1 6 3 5 1 4 3 5 2 3 3 2 2 1 1 u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u Аналогично обстоит дело и с орграфом. У него матрица смежности вершин несимметрическая. Рассмотрим следующий орграф (см. рис. 3.20) и определим все маршруты с тремя ребрами. Матрица смежности и результаты ее возведения в квадрат и куб находятся 1 u 3 u ниже. Рассмотрим элемент 2 22 p после возве- A B C D дения матрицы смежности вершин в квадрат. 2 2 22 p , т. е. из вершины B в вершину B 2 u 4 u есть два маршрута длиной две дуги. Это ма- 5 u ршруты B Cu Bu 4 3 и 1 2 B Au Bu После возве- Рис. 3.20. дения матрицы в куб сохраняется та же кар- тина. Например, 2 3 12 p ; это значит, что есть два маршрута длиной три дуги из вершины A в вершину B . Это маршруты и 4 3 1 1 2 1 B Cu Bu Au B Au Bu Au Для получения цепей (маршрутов, в которых каждое ребро встречается один раз) нужно в модифицированной матрице 3 P вычеркнуть те слагаемые, в которых какой-либо сомножитель встречается более одного раза. 0 0 0 0 1 1 2 0 1 2 1 2 1 2 2 1 0 0 0 0 1 0 1 0 0 1 0 1 0 1 1 0 0 0 0 0 0 1 0 1 1 1 2 0 1 1 1 1 , 0 0 0 0 0 1 0 1 1 1 2 0 1 1 1 1 0 0 0 0 1 0 1 0 0 1 0 1 0 1 1 0 0 0 0 0 1 0 1 0 0 1 0 1 0 1 1 0 3 2 P P Из теоремы 3.7 следуют да важных следствия, позволяющие определять наличие маршрутов и циклов в графе. Следствие 1. В графе G мощности n тогда и только тогда существует j i x x , - маршрут j i x x , когда j i, -й элемент матрицы 1 2 n P P P не равен нулю. Следствие 2. В графе G мощности n тогда и только тогда существует цикл, содержащий вершину i x , когда i i, -й элемент матрицы n P P P 2 не равен нулю. 63 В рассмотренном примере 1 имеем 4 n , 0 0 0 0 1 2 1 2 2 3 4 1 2 3 3 2 4 P , 3 2 P P P A 0 0 0 0 2 2 3 1 2 4 3 3 2 4 4 2 , 0 0 0 0 3 4 4 3 4 7 7 4 4 7 7 4 4 3 2 P P P P B Рассмотрим элементы матрицы A . Например, 0 2 24 a . Это значит, что в исходном графе (см. рис. 3.20) существуют маршруты из вершины B в вершину D . Это маршруты: BCBACD BACD BCD , , . Аналогично, 0 7 22 b . Таким образом, существуют циклы, проходящие через вершину B . Это, например, циклы BAB BACB , и BCB . Так как 0 44 b , то через вершину D не приходит ни один цикл. Это хорошо видно на рис. 3.20. 3.8. Определение экстремальных путей на графах. Метод Шимбелла Введем, следуя Шимбеллу, специальные операции над элементами матрицы смежности вершин, позволяющие находить кратчайшие или максимальные пути между вершинами, состоящие из заданного количества ребер. Эти операции таковы. 1) Операция умножения двух величин b a и при возведении матрицы в степень соответствует их алгебраической сумме, то есть 0 0 0 0 0 , a a a a b b a a b b a (3.8.1) 2) Операция сложения двух величин b a и заменяется выбором из этих величин минимального (максимального) элемента, то есть , , min(max) b a a b b a (3.8.2) нули при этом игнорируются. Минимальный или максимальный элемент выбирается из ненулевых элементов. Нуль в результате операции (3.8.2) может быть получен лишь тогда, когда все элементы из выбираемых – нулевые. С помощью этих операций длины кратчайших или максимальных путей между всеми вершинами определяется возведением в степень весовой матрицы , содержащей веса ребер. Например, элементы матрицы 2 определяются следующим образом ω ω ,..., ω ω , ω ω min(max) ω 1 1 1 2 1 2 1 1 1 1 2 nj in j i j i ij Аналогично определяются элементы k - 1 B 2 й степени матрицы Рассмотрим пример. Составим для A указанного на рис. 3.21 графа матрицу весов. Она опре- 2 2 C деляет все маршруты, состоящие из одного ребра. Най- 3 дем кратчайшие пути из двух ребер, для этого возведем 2 D эту матрицу в квадрат с учетом операций Шимбелла 1 (min – кратчайшие пути). Рис. 3.21. 0 4 0 4 0 0 0 0 4 5 2 0 0 3 4 3 0 1 2 0 0 0 0 0 0 2 0 2 2 3 1 0 0 1 2 0 0 0 0 0 0 2 0 2 2 3 1 0 2 P Шимбелл (???? - ????) – американский математик. 64 Например, 3 0 , 0 , 3 , 0 min 0 2 , 0 3 , 2 1 , 0 0 min ω ω , ω ω , ω ω , ω ω min ω 1 41 1 14 1 31 1 13 1 21 1 12 1 11 1 11 2 11 Аналогично, кратчайшие пути из трех ребер будут 6 7 5 0 0 0 0 0 0 4 6 4 5 6 4 6 0 1 2 0 0 0 0 0 0 2 0 2 2 3 1 0 0 4 0 4 0 0 0 0 4 5 2 0 0 2 4 3 3 P и так далее. Например, длина кратчайшего пути из трех ребер из вершины D в вершину C равна семи. Это путь DBAC . 3.9. Практическое занятие № 6. Способы задания графов. Операции над графами. Метрические характеристики графов. Упорядочение элементов орграфов 3.9.1 Показать, что для произвольного графа U S G , справедливо равенство U x P S x 2 3.9.2. Для данных графов (см. рис. 3.22) составить матрицы смежности вершин, смежности дуг и инциденций: а) 4 x 6 u 2 x б) 3 x в) 4 x 8 u 3 u 1 u 3 u 4 u 7 u 2 x 7 u 5 u 5 x 9 u 2 x 1 x 6 x 1 u 4 u 6 u 4 u 5 x 6 u 1 u 2 u 5 u 9 u 2 u 1 x 2 u 5 u 8 u 1 x 3 x 7 u 5 x 4 x 3 x 3 u Рис. 3.22. 3.9.3. По матрице смежности вершин построить наглядные изображения графов: а) 0 1 2 0 0 1 1 0 3 0 2 0 1 1 2 0 3 1 0 1 0 0 2 1 1 ; б) 0 2 1 1 0 2 2 1 1 2 0 0 1 1 0 0 1 0 1 2 0 1 1 1 0 0 1 1 0 2 2 0 0 1 2 0 ; в) 1 1 1 0 1 0 1 1 0 0 1 0 0 0 0 0 1 1 0 0 1 1 0 0 1 ; г) 0 1 1 0 0 1 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 1 0 0 1 0 3.9.4. На рисунке 3.23 даны графы 1 G и 2 G . Найти 2 1 G G и 2 1 G G если: а) б) 1 x 2 x 1 x 2 x 1 x 1 x : 1 G : 2 G : 1 G : 2 G 4 x 3 x 4 x 3 x 3 x 2 x 3 x 2 x 65 в) 1 x 2 x 1 x : 1 G : 2 G 4 x 3 x 2 x 3 x Рис. 3.23. 3.9.5. Найти матрицы сильных компонент и маршрутов длины три, исходящих из вершины 1 x для графов, изображенных на рисунке 3.24: а) 2 x 4 x б) 1 x 2 x в) 1 x 2 x 1 x 3 x 5 x 4 x 3 x 4 x 3 x Рис. 3.24. 3.9.6. Найти эксцентриситеты вершин, радиусы и диаметры графов, периферийные, центральные вершины и диаметральные цепи следующих графов (см. рис. 3.25): а) 1 x 2 x 3 x 4 x б) 1 x 2 x 3 x 4 x в) 3 x 4 x 7 x 2 x 5 x 6 x 8 x 7 x 6 x 5 x 8 x 7 x 6 x 5 x 1 x 8 x Рис. 3.25. 12 x 11 x 9 x 10 x 3.9.7. Упорядочить вершины и дуги орграфов, изображенных на рисунке 3.26, графическим и матричным способом (дуги – только графическим способом). а) 2 x 9 u 3 x б) 2 x 7 u 3 x в) 2 x 3 x 2 u 6 u 8 u 5 u 7 u 5 u 6 u 1 u 4 u 10 u 6 x 1 x 2 u 6 x 1 x 3 u 4 u 6 x 1 x 3 u 11 u 5 u 7 u 4 u 1 u 3 u 9 u 8 u 1 u 2 u 10 u 6 u 4 x 8 u 5 x 4 x 5 x 4 x 5 x Рис. 3.26. 3.9.8. Доказать, что три графа, изображенных на рисунке 3.27, изоморфны, а графы на рисунке 3.28 не изоморфны. 1 x 2 x 3 x 2 x 3 x 1 x 4 x 2 x 3 x 2 x 3 x 1 x 4 x 2 x 3 x 1 x 4 x 1 x 4 x 6 x 5 x 4 x 6 x 5 x 6 x 5 x 6 x 5 x 6 x 5 x Рис. 3.27. Рис. 3.28. 3.9.9. Построить граф, центр которого: 66 а) состоит ровно из одной вершины; б) состоит ровно из трех вершин и не совпадает с множеством всех вершин; в) совпадает с множеством всех вершин. 3.9.10. Показать, что в любом графе без петель и кратных ребер, содержащем не менее двух вершин, найдутся две вершины с одинаковыми степенями. |