Введение в прикладную комбинаторику, Кофман А. (984071), страница 23
Текст из файла (страница 23)
91 гамильтонов, а в графе на рис. 90 нет гамнльтонова пути. Аналогично гамильтонов контур — контур, проходящий через все вершины в точности по одному разу (исключая произвольно выбранное начало). Задача перечисления гамильтоновых путей и контуров графа будет разбираться в главе 1ьг. УПРАЖНЕНИЯ 26А. Какие из последовательностей (А, В, Е, О, С); (А, В, Е, А, С, В); (А, В, О, Е, С, В); (А, А); (С, С); (А, В, Е, 6); (О, Е, Р, О, Е, Р, О); (Е, Р, Р, О, Е); (О, Р, Е, В, А, С); (В, Е, Р, О, Е, б] для графа на рис. 90 являются. а) путем, б) простым путем, в) элементарным путем, г) контуром, д) простым контуром, е) элементарным контуром.
26Б. Указать длины путей из упражнения 26А. 26В. Рассматравая непосредственно граф па рис. 90, показать, что он не обладает гамильтоновым путем. 26Г. Перечислить элементарные пути соответственно длин 1, 2, 3, 4, 5 графа на рпс. 91. (Систематический метод будет дан в $44.) 26Д Перечислить гамильтоновы контуры графа на рис. 91 (считая одинаковыми контуры, получающиеся один из другого циклическим сдвигом). ') По имени известного английского математика Гамильтона. 163 5 27. Сильно связный граф. Разложение на максимальные сильно связные подграфы. Транзитивное замыкание и пересчет путей Транзитивное замыкание. Пусть задан граф 6 =(Е, Г).
Определим многозначные отображения Г', Г',... по формулам Г'Х, = Г (ГХ,), (27 А) Гах! — — Г (Г'Х;) = Г )Г (ГХ!) ), (27.2) а обратные многозначные отображения Г ', Г, ... — по формулам Г еХ,-1 '(Г 'Х), (27.3) Г Х,=Г (Г Х~)=Г '(Г '(Г 'Х!)), (274) Например, для графа на рис. 92 имеем ГА=)В, Р,6), ГВ=)А, В, С), ГС=)0, Е), ГВ=)С), ГЕ= Я, ГР=)В, Р), Г6= )А, Е); (2?5) Г Л= Г (В, Р, 6) = ГВ() ГР() Г6 = = )А, В, С) Ц )В, Р) Ц )А, Е) = )А, В, С, Е, Р), Г'В Г (А, В, С) = ГЛ Ц ГВ () ГС = ) А, В, С, В, Е, Р, 6); (27.6) Г А = Г (А, В, С, Е, Р) = )А, В, С, О, Е, Р, 6). (27 1) Читателю предлагается продолжить дальше и выписать обратные преобразования. Очевидно, что Г"Х; и Г-"Х; являются соответственно подмножествами тех вершин, в которые можно прийти из Хи используя пути длины и (или, быль может, меныпей), и тех вершин, из кое с торых можно прийти в Хь используя пути длины п (или, быть может, меньшей). я Р Транзитиеным замыканием ГХ; называется многозначное отображение, определяемое формулой ГХ,= )Х,) () ГХ,Ц ГеХ.Ц ГаХ () ~) Рис, 92 (2?.8) Другими словами ГХ; является множеством вершин, в которые можно прийти нз Х; по некоторому пути.
') Некоторые авторы ооределкгот ГХ~ к Г Х! так: ГХ, =ГХ,ЦГ Х,Ц ..., Г Х; =Г 'Х,ЦГ 'Х,Ц !бч Аналогично определяется обратное транзитивное замыканиег Г Хг= (Хг) () Г Х,() [' Хг() ...'), (27.9) т. е. множество вершин, из которых попадают в Хг по некоторому пути. Например (рис. 92), ГА= Е, ГВ= Е, ГС = (С, О. Е), Г.О= (С, О, Е), ГЕ=(Е), 1чР=Е, ГО=Е. Предоставим читателю в качестве упражнения найти соответствующие Г-'). Сильно связный граф а). Граф б = (Е, Г) называют сильно связным, если (ЧХ1 ~ Е) ГХг — — Е, (27.10) т.
е. для любых двух вершин Хь Х; такого графа существует путь, идущий из Хг в Хь Граф на рис. 93 сильно связный, а граф на рис. 92 не является таковым. Легко показать, что (27.10) эквивалентно условию (УХс ~ Е) 1 Хг = Е (27 11) Бинарное отношение «существует путь из Х; в Х1» является отношением частичного порядка на множестве вершин Е, так как оно транзитивно и рефлексивно. Бинарное Рис. 93. отношение «существует путь из Хг в Х; и путь из Х; в Х㻠— отношение эквивалентности Я, так как оно, кроме того, симметрично. Разложение графа на максимальные сильно связные подграфы. Подграф 6' графа б =(Е, Г) называют макспмальньгм сильно связным, если не существует сильно связного графа сг'", строго содержащего 6'. П р и м е р.
Максимальные сильно связные подграфы графа на рис. 95 обведены пунктиром. Фактормножество Е)Я состоит из классов Сг, Са, ..., С„, каждый из которых есть максимальный сильно связный подграф. Пример. Рассмотрим граф на рис. 94. Из его представления на рис. 95 видно, что Е/Я состоит из шести классов. Легко показать, что множество классов упорядочивается отношением Я'. существует путь из класса С, в С, Отношение Я' рефлексивно и транзитнвно. Оно также антиснмметрично, так как если бы существовали пути как из С„в С„так и из С, в С„, ') См.
сноску на стр. 164. ') Более слабое понятие связного графа будет определено в й 39. 163 то С, и С, следовало бы объединить в один класс, что противоречит их максимальности. П р и м е р. Рис. 96 показывает, как можно упорядочить Сг, Са, ..., С, из рис. 95. Этот порядок, очевидно, частичный. '6„ 1 т Рнс. 94. Рнс. 95. Метод' ) разложения графа на максимальные сильно связные подграфы. Если С(Х,) — класс, содержащий Хг, то С (Х;) = ГХг Д 1' Хь (27.12) Метод состоит в следующем. Берем произвольную вершину Хг и находим ГХь Г Х; и ГХг П Г Х!. Затем берем вершину Х! Ф С(Хг) и действуем аналогично. Продолжаем процесс до тех пор, пока это возможно.
С! П р и м е р. Рассмотрим представление графа на рис. 94 в виде булевой матрицы (см. рис. 97, нули опущены). Справа от маса трицы поместим столбец, а внизу — строку, которые будем заполнять следуюгцим образом. 5 В клетку столбца напротив строСа ба ки А ставим нуль.
В клетку столб- ца напротив строки гг ставим 1, Рнс. 96. так как строка А содержит 1 на месте 6. Строка 6 матрицы содержит 1 на месте К, поэтому напротив К помещаем 2 (это показывает, что кратчайший путь из А в К длины 2). Строка К матрицы содержит 1 на местах А, Е, Е, К Ставим 3 напротив Е и Г (клетки напротив А и К уже заполнены). В стро- ') Метод предложен М а л ь г р а н ж е м (У, М а 1 я г а и я е).
См. также Томе ску (Т огне а сп), Мейойе ропг !а де1егпппаиоп ае 1а 1еппе)пге 1гапа!Нте й'пп игарке Нп), Кетпе АНКО, Бег!е гонке, № 3, 1967, 166 ГА Рас. 97. строке внизу дают минимальные длины путей графа, получаю- щегося из исходного изменением направления дуг. Имеем Г А=(А,В,С,О,7,7,К), (27.14) С(А) = ГАД Г А=(А, О, К). (27.
15) Удаляя из графа вершины А, О, К, получаем подграф, пред- ставленный на рис. 98. Берем произвольную вершину, напри- мер О, и, поступая с ней точно так же, находим Г~0=(0, Е), Г~ 0=(С, О, Е, Н 7), С(0)= Г,0ДГГ0= (О, Е). (27.16) (27. 17) (27.18) 161 ке Е на месте 0 стоит 1 и напротив 0 ставим 4. В строке Р 1 стоит на местах Р и Н. Клетка напротив Р уже заполнена, и мы ставим 4 напротив Н. Рассмотрение строк 0 и Н приводит к уже заполненным клеткам. В оставшиеся клетки столбца ставим «Х».
Числа в клетках этого столбца — длины кратчайших путей из А в соответствующие вершины; «К» означает, что пути не существует. Таким образом, ГА=(А, О, Е, Р, О, Н, К). (27. 13) Аналогично действуем для получения Г-А, но при этом меняем ролями строки и столбцы матрицы. Полученные числа в в А В С В Е К С Н 1 1 Н ГА Удаляя из графа на рис. 98 вершины 0 и Е, получаем граф, представленный па рис. 99.
Для произвольной его вершины, л в с и и Р и 1 т г,о гр Рис. 98. л В с К Н г 7 Г ВРНг зн гр Рис. 99. Рис. 100. например С, получаем Г,С = (С, 1, 1), ГсС=(С, 1, 1), С(С) (С, 1, 1). Продолжая, легко находим (рис, 100) С (В) = (В), С (Р) = (Р), С (Н) = (Н). (27.22) Таким образом, приходим к шести классам, показанным на рис, 95. 168 (27. 19) (27.20) (27.21) Существование и пересчет путей. Путь положительной длины из Х; в Х; существует, если (~р и 14о) Х, ен Г'Х,. (27.23) Если рассматривать пути длины нуль, то (27.23) можно записать так: Х1 ен ГХ;. (27.24) Булеза матрица ~~Вс графа показывает, какие существуют пути длины 1. Пусть (( В!(с = ~~ В 1! ~~ В )(, (27.25) А (! В У = )! В ~(' )1 В 1~, (27.26) !)В!~с =~~ В11' )1 Вф(с ~; (27.27) тогда и" 2" ~ сс ~ 2" ~ сс В'„= Вп Вм -(- В;, В„ -1- ° ° ° .+ Вь В 1, (27.28) Э где .+ означает булево сложение.
Рис. 1О1. Если )1 В 1(' + = 11 В У", (27. 29) то матрица 1!В11с показывает, какие вершины в графе связаны путями. Пример (рис. 101). Рассмотрим матрицу ~1 В1г', изображенную на рис. 102. А В С Р и Р А В С р К Р 1В11 11В1с Рис 103, Рис. 102. Матрица 11В11и (рис. 103) показывает, какие существуют пути длины 2. Замечаем, что ~!В04 = 1~ВР (см.
рис, 104, 105). Следовательно, 1!В11' показывает, какие вершины в графе связаны путями. 169 Чтобы пересчитать различные пути длины г, рассмотрим степени булевой матрицы йЛН: Н АНс=Н АН Н АН, НАНз=Н АНс ° Н АН, (27.30) (27.31) Н А Н' = Н А Н' ' Н А Н, (27.32) Ас»= А7~ ~Ан+ Лсм ~Ам+ ° ° + Ао А 1 (27 33) А В С В Е и А В С П Е и нвн нвнз Рис. 105. Рис. 104. А В С В Е Г А В С П Е Е НАН' НАН Рис. 107.
Рис. 106. Н А Н дает число путей длины 1 между каждой парой вершин (Хо Х1), Н А Нс дает число путей длины 2 между каждой парой вершин (Хо Х ), Н АН' дает число путей длины и между каждой парой вершин (Хс, Х;). Пример (рис. 101). Матрицы на рис. 106 — 109 дают число путей длин соответственно 1, 2, 3, 4 в графе. Видим, что имеется 170 пять путей длины 3 от В к В (см. ((А((з), девять путей длины 4 от В к В (см, ((А((4). А В С 11 Е и П А(ь ((А!! з Рис. 109. Рис. 108.
УПРАЖНЕНИЯ 27д. для графа на рис, 92 выписать: а) ГзА, б) Г'(С, 0), в) Г'(А, В), г)ГзА,д)Г ~(С,С),е)Г зА,ж)Г зЕ. 27П. Для указанного ниже графа найти: а) Г11, б) Г 1), в) Г(А, С), г) Г (А, С), д) ГЕ, е) Г Е. Е 27и. Разложить графы а), б), а) на максимальные сильно связные подграфы. 171 Х! Хз Хз Х4 Хз Хз Хт Хз ' Хз Х10 ! 2 3 4 Б 6 7 3 9 Х Х з Х4 Х, Хг х, Х!о б) 27Г. Для графа а) пересчитать пути длины 1, 2, ... 7, а для графа д)— пути длины 1, 2,..., 9. и Ь 0 б з С зт) 27Д.
Используя метод булевых матриц, указать способ пересчета контуров в графе. 5 28. Порядковая функция графа беа контуров Рассмотрим граф без контуров 6=(Е, Г) и определим под- множества Хо, Х„..., Х, '): Хо — — (Х1)хгеБЕ, Г Х1 0), Х, = (Х1 ) Х1 он Š— Хо, Г 'Х1 с Хо), (28. 1) 172 ') Иногда порядковая функция вводится с помощью Г (а не Г как ниже). Это приводит к другому порядку уровней. й),=(Х,(Х, =Š— (й(,() й),), Г-'Х, й(,() й(,), (28.1) г-1 и 1 н,-(х,,х, в 1!и.. г-'т, 11 и,(.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
