Введение в прикладную комбинаторику, Кофман А. (984071), страница 22
Текст из файла (страница 22)
Описание Бержа. В книге Б е р ж а [8[ граф описывается соответствием Г между подмножествами множества Е. Например, для графа на рис. 74 — 78 образованную множеством Е и многозначным') отображением Г множества Е в себя. Отображение Г можно определить для любого подмножества из Е. Например, Г(В, О, Е) =ГВ() ГОЦ ГЕ= (А, С) () (С, О) () (А, В, О) = = — 1А, В, С, О).
(25.9) Определим граф 6 ' с помошью обратного отображения 1 6 =(Е, Г '). (25. 10) Например, из (25.7) Г А=(А,В,С,Е), Г 'С=(В, О), 1 Е=(А), Г В=(А, Е), Г О=(С, О,Е), Г Р=(Л,Г), (25. 11) и соответствуюшие представления графа 6-' получаются, если на рис. 74 и 75 переставить строки со столбцами, на рис. 77, 78 А и с и и р Е Е Рис. 77. Риг 78. Рис 76. изменить направление всех стрелок, а на рис.
76 переставить строки со столбцами и изменить порядок букв в каждой клетке. Граф 6 = (Е, Г) имеет порядок и, если (Е(= п. На языке теории графов элемент Х; еп Е называют вершиной, а пару (Х„Х;), где Х, е= ГХь дугой. Если обозначить через 11 множество всех дуг графа (в на. шем примере 33 = ((А, А), (А, В), (Л, Е), (А, Р), (В, А), (В, С), (С, А), (С, О), (О, С) (О, О), (Е, А), (Е, В), (Е, .О), (Г, Р)) ), (2оЛ2) ') В современной математике термин «отображение» означает однозначное соответствие, а для многозначного отображения употребляется термин «многозначное соответствие», 1б7 то граф можно определить так: 6=(Е, 11). (25.13) Для удобства дуги обозначают также одной буквой; ил=(Хг, Х;), или и,, =(Хо Х1), или и=(Хг, Хг). Концевые точки.
Для дуги и =(ХьХ,) назовем Х; началом, а Х; — концом. Петля. Дуга, начало и конец которой совпадают, называется петлей. На рис. 78 дуги (А, А), (О, 0), (Р, Р) — петли, а на рис. 74, 75 и 76 петли расположены на главных диагоналях. Смежные дуги. Дуги называются смежными, если они различны и имеют общую концевую точку. Например, на рис. 78 дуги <' Е (АР) и (А,В), (А,В) и (В,А), (В,А) и (А, Р) смежные, межные верннцгьг Две ве(ншппя Х; смежны, если они различны и существует дуга, идущая от одной из них к другой.
Например, на рис. 78 вершины А и Р, А и В смежны, а С и Р не смежны. Дуги, инцидентные подмножеству вершин. Пусть задан граф 6=(Е, О) и не- пустое подмножество Е, множества Е. Говорят, что дуга и=(Х„Х ) заходит в Ео если Хг ~ Е„ а Хг ~ Ео Если же Хг ~ Е„а Хг ггн Ео то говорят, что и исходит из Ео В оооих случаях дугу и называют инцидентной подмножеству Ео Обогначим соответственно через $3е, и 1)е, множества дуг, заходящих в Е, и исходящих из него. Например, на рис. 79 1)е, = ',(Л, В), (А, Е), (С, В)1, Бек, = ((Е, А), (В, С)). (25.14) Если подмножество сводится к одной вершине, то дугу называют инцидентной этой вершине (заходящей в нее или исходящей из нее). Полустепень подмножества. Внутренней полустепенью называется число ~ 1)е,~ дуг, заходящих в Ег, а внешней полустепенью — число ~ 0а, ~ дуг, исходящих из Ег Например, на рис.
79 !1.).,1=8, !М,1=2. (25.! 5) Частичный граф. Подграф. Рассмотрим два графа: 6 = (Е, Г) и 6г = (Е, Гг). Если (ЧХг ~ Е) (ГгХ, с: ГХг), (25. 16) 156 то О, называют частичным графом графа О. Иначе говоря, 6, =(Е, П,) есть частичный граф графа 0=(Е, 13), если 1),с: Ю. Граф на рис. 81 — частичный граф графа на рис.
80. Подграфом графа 6=(Е, Г) называется граф бэ=(А, Гг), если А с: Е и (УХс еи А) Г,Х, = А () ГХ,. (25. 17) Граф на рис 82 — подграф графа иа рнс. 80. Подграф строится Рис. 80. Рис. 80 Рис. 82. Рис. 83. на подмножестве множества вершин графа и включает все дуги, инцидентные вершинам этого подмножества. Можно определить частичные подграфы (прнмер на рис. 83). С е Рис. 84. Рис. 88.
Рис. 86. Симметрический граф. Антисимметрический граф. Полный граф. Граф 6=(Е, 1)) называется симметрическим, если (чХ,еи Е тГХ(еи Е) (Хо Х()еи 1) =,='«(Хп Х,)я 13 (25.18) (любые две вершины Х; и Хг соединены двумя противоположно направленными дугами). Пример такого графа приведен на рис. 84. Граф 6=(Е, П) называется антигимметричегким, если (УХс еи Е 7Х( ен Е) (Хо Хг) еи П =Р(ХР Х~) Ф 1) (25.19) (каждая пара смежных вершин соединена лишь в одном направлении, петли отсутствуют). Пример такого графа приведен на рис.
85. Граф 0=(Е, П) называется полным, если (ЧХ;~ Е УХА~ Е) (Хо Х~) Ф 1) =Р(ХР Хс) еи П (1 ~ 1) (25.20) 169 (любые две вершины соединены по кранней мере в одном направлении). Пример полного графа дан на рис. 85. Полный граф с петлями. Граф 0 = (Е, Г) называется полным графом с петлями, если (нХ; ~ Е) ГХ; = Е (25.21) (каждая пара вершин, различных или нет, соединяется дугой; см. рнс. 87).
Очевидно, что каждому графу можно сопоставить полный граф с петлями. Рис. 89. Рис. 88. Рис 87. Дополнительный граф. Пусть заданы граф 6 = (Е, Г) = (Е, 1)) и соответствуюгций ему полный граф с петлями 6,=(Е, Г )= =(Е, 13р). Граф 0*=(Е, Г") =(Е, 1) р — 1)) называется дополнительным к графу 6. Очевидно, (25.22) (6')' = 6. Графы на рис. 88 и 89 дополнительные друг к другу. Можно описать дополнительный граф по-другому: (ЧХ ~ Е) Г'Х = Š— ГХР (25.23) УПРАЖНЕНИЯ 28А. Дать другие представления (в тон числе и описание Бержа) для графов 25Б.
То же для графов Х| Хг Хз Х4 Хз Хе А В С Р В Х Х в) в) 25В. Привести описание Бер>ка графов 0 ' = (Е, Г ~), соответствующих графам 0 в упражнениях 25А, а) и в) и 25Б, б). 25Г. Выписать множества () дуг дая графов из упражнений 25А, а) и б). 25Д. Найти мяожества ))и и ()+ для следующих множеств Еб а) упражнение 25А, а): Е1 = (А, В): б) упражнение 25А, а): Е~ = (С); в) упражнение 25А. б): Е, = (Хв, Хо Хз); г) упражнение 25Б, б); Е~ = (О, Е). 25Е. Вычислить полустепени для каждого из случаев упражнения 25Д. 25Ж.
Какие из приведенных ниже графов являются симметрическими, антисимметрическими, полными, полными с петлями: а) б) е) е) 253. С помощью стрелок изобразить дополнительные графы О' (Е, Г') к графам Р = (Е, Г) из упражнений 25А, б); 25А, з). 2 26. Понятие пути В комбинаторике понятие пути играет существенную роль, и мы рассмотрим его, а также понятия, тесно связанные с ним. Путем называется такая последовательность (иь иг, ...) дуг, что конец каждой предыдущей дуги совпадает с началом следующей.
Путь может быть конечным или бесконечным. Например, (а, с, т, (), (), пг, г(, Ь, а), (д, А, л, ), Л, д) (26.1) )5! — пути графа на рис. 90. Путь можно обозначить также после- довательностью вершин, которые он содержит: (С, А, В, Е, с)), (С, В, Е, А, С, А), (С, О, Е, Р, й, Е, 6). (26.2) р=(а, с, т, г): ((р) =4; р = (и, й, п, 1, й, 9): ((н) = 6. (26.3) Для удобства вводят понятие пути нулевой длины (изолированная вершина). Замечание к понятию контура. Контуры, которые образованы одними и теми же дугами, взятыми в одинаковом порядке, и записи которых получаются одна из другой циклическим сдвигом, можно считать либо эквивалентными, либо неэквивалентными. Например, контуры (рис.
90) (й пэ !) (нэ П Ь)~ (3> й1 и) (26.4) 162 Простой путь. Путь называется простым, если никакая дуга не встречается в нем дважды, и составным в противном случае. Например, на рис. 90 (а, с, т, ~) — простой путь, а (и, Ь, и, /, Й, д) — составной. Элементарный путь. Путь называется элементарным, если в нем никакая вершина не встречается дважды, и неэлементарным в противном случае. Например, на рис. 90 (а, с, т, ~)— А элементарный и простой путь, с (Ь, а, с, т, 4) — неэлементар- ный и простой, (ь, Ь, п, 1, й, а)— В пеэлементарный и составной.
е Контур. Контур — это ко- д нечный путь, у которого на- Я Е чальная вершина дуги и~ сову падает с конечной вершиной и дуги им Контур можно обозна- Г чать как дугами, так и вершие р нами, которые он содержит. Примерами контуров графа на рис. 90 являются (п,),Ь), (Ь, и, Ь, и, /, Ь, й) . Контур называется элементарным, если все вершины, через которые он проходит, различны (за исключением начальной и конечной, которые совпадают). На рис.
90 (с(, Ь, а, Ь) — элементарный контур. Контур называется простыл, если все его дуги различны. На рис. 90 (и,), Ь) и (Ь, а, е, а) — простые контуры. Длина пути. Длиной пути р = (иь иь ..., и,) называют число его дуг и обозначают через ~(р). Например (рис. 90), можно считать либо эквивалентными, либо неэквнвалентны. ми. То же самое относится и к представлению с помощью вершин: (О, Е, Р, 0), (Е, Р, О, Е), (Р, О, Е, Р), (26.5) В случае надобности указывают начало контура, При изучении подстановок (5 16) мы представляли их с помощью графов, прн этом циклы подстановок представлялись контурами. При изучении неориентнрованных графов используется термин «цикл». Понятий в математике больше, чем слов, которыми мы располагаем для их обозначения.
Внимательный читатель избежит возможных недоразумений. Гамильтонов путь, Элементарный В путь, в котором число дуг на единицу меньше числа вершин графа, пазы- Е с вается гамильтоновым путем' ). Иначе говоря, такой путь проходит через все А вершины в точности по одному разу. При записи с помощью вершин гамильтонов путь — перестановка вершин графа. Е Например, путь (Р, В, А, С, О, Е) Рис. 91. на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
