Дискретная математика (998286), страница 35
Текст из файла (страница 35)
В этом случае элементы множества Ъ' называются узлами, а элементы множества Š— дугами. 2. Если элементом множества Е может быть пара оглгнаковых (не различных) элементов»г, то такой элемент множества Е называется пегплей, а граф называется графом с петлями (или псевдографом). 3. Если Е является не множеством, а набором, содержащим несколько одинаковых элементов, то эти элементы называются кратными ребрами, а граф называется мультиграфом.
4. Если элементами множества Е являются не обязательно двухэлементные, а любые подмножества множества Ъ', то такие элементы множества Е называ- ются гипердугаии, а граф называется гиперграфом. 5. Если задана функция Г: )г -+ М и/или Р: Е -» М, то множество М называется множеством пометок, а граф называется помеченным (или нагруженным). В качестве множества пометок обычно используются буквы или целые числа. Далее выражение «граф С($;Е)» означает неориентированный непомеченный граф без петель и кратных ребер. 193 7Л.
Опрвдопвнии графов 7.1.6. Изоморфизм графов Говорят, что два графа С1Я, Е1) и Сз()гз, Ез) изоморфны (обозначается Ст Сз), если существует биекция Ь: Ъ~ -1 1'з, сохраняющая смежность: Е1 (и,и) о Е1 =Ь ЕЗ = (6(и),х(О)) о ЕЮ ез=(и,о) оЕг=Фе1=(Ь (и),п (о)) еЕ1. Изоморфизм графов есть отношение эквивалентности. Действительно, изоморфизм обладает всеми необходимыми свойствами: .1.
рефлексивностги С С, где требуемая биекция суть тождественная функция; 2. симметричность: если С, Сз 'с биекцией й, то Сз С1 с биекцией 6 ', 3. транзитивностгс если С1 Сз с биекцией й и Сз Сз с биекцией д, то С1 Сз с биекцией д.о Ь. Графы рассматриваются с точностью до изоморфизма, то есть рассматриваются классы эквивалентности по отношению изоморфизма (см.
раздел 2.2). Пример Три внешне различные диаграммы, приведенные на рис. 7.5, являются диаграммами одного и того же графа Кз,з. 5 Юв В1 Рис. 7Ъ. Диаграммы изоморфных графов Числовая характеристика, одинаковая для всех изоморфных графов, называется инвариантам графа. Так, р(С) и д(С) — инварианты графа С. Не известно никакого набора инвариантов, определяющих граф с точностью до изоморфизма.
Пример Количество вершин, ребер и количество смежных вершин для каждой вершины не определяют граф. На рис. 7.б представлены диаграммы графов, у которых указанные инварианты совпадают, но графы при этом не изоморфны. 194 Глава 7. Графы Рис. 7.6. Диаграммы нвизоморфных графов с совпадающими инввривнтвми 7.2. Элементы граФов После рассмотрения определений, относящихся к графам как к цельным объектам, естественно дать определения различным составным элементам графов. 7.2.1.
Подграфы Граф С'(У', Е') называется подграфом графа С(У, Е) (обозначается С' с С), если 1" с У и/или Е' с Е. Если Ъ' = У, то С' называется вставным подграфам С. Если Ъ" с У 1г Е' с Ей(Ъ' ф. У'~7 Е' ~ Е), то граф С' называется собственным подграфом графа С. Подграф С'(У',Е') называется правильным подграфом графа С(У,.Е), если С' содержит все возможные ребра С: Ч и, с е У' (и, е) е Е =ь (и, и) е Е'. Правильный подграф С'Я', Е~) графа С(У, Е) определяется подмножеством вершин У'. 1.2.2.
Валентнооть Количество ребер, инцидентных вершине о, называется степенью (или валентностью) вершины о н обозначается Щи): Чн й У О ~ (д(и) (~ р — 1, г((в) = )Г(о)1 Обозначим минимальную степень вершины графа С через 6(С), а максимальную — через гл(С): Ю(С(У,Е)):=шшд(и), Ь(С(У,Е)):=шахд(и). Если степени всех вершин равны й, то граф называется регулярным степени й: 6(С) = Ь(С) = й. Степень регулярности является инвариантом графа и обозначается г(С). Для нерегулярных графов г(С) не определено.
Пример На рис. 7.7 приведена диаграмма регулярного графа степени 3. дз. Элементы графов рнс. 7.7. Диаграмма регулярного графа степане 3 Если степень вершины равна О (то есть д(о) = 0), то вершина называется изолированной. Если степень вершины равна 1 (то есть д(о) = 1), то вершина называется концевой, или висячей. Для орграфа число дуг, исходящих из вершины о, называется пслуствпвнью остада, а входящих — полустепвнью захода. Обозначаются эти числа, соответственно, й (о) и а+(о). ТЕОРЕМА (Эйлера) Сумма степеней вершин графа равна удвоенному количеству ребер: й(о) =2д, ~~ а (о)+ ~ д+(о) = 2д «ад' «еи «еи Доказатвльство При подсчете суммы степеней вершин каждое ребро учитывается два раза: для одного конца ребра и для другого.
П 7.2.3. Маршруты, цепи, циклы г«гаршрутом в графе называется чередующаяся последовательность вершин и ребер оо,е„од,еэ,оэ,...,еь,оь, в которой любые два соседних элемента инцидентны. ЗАМЕЧАНИЕ Это определение подходит также для псевдо-, мульти- н орграфов. Для «обычного«графа достаточно указать только последовательность вершин нлн только последовательность Если оо = ок«то маршрут эамкнут, иначе открыт. Если все ребра различны, то маршрут называется цепью. Если все вершины (а значит, и ребра) различны, то маршрут называется простой цепью.
В 'цепи оо,ед,...,еде оь вершины оо и оь называются концами цепи. Говорят, что цепь с концами и н о совдинлегп вершины и и о. Цепь, соединяющая вершины и и о, обозначается (и, о). Очевидно, что если есть цепь, соединяющая вершины и и о, то есть и простая цепь, соединяющая эти вершины. 196 Глава 7.
Графы Замкнутая цепь называется циклом; замкнутая простая цепь'называется простым циклом. Число циклов в графе О обозначается з(С). Граф без циклов называется ациклическим, Для орграфов цепь называется путем, а цикл — контуром. Пример В графе, диаграмма которого приведена на рис. 7.8; 1. и,, из, иы и4 — маршрут, но не цепь; 2. иы из, ию из, из, ил — цепь, но не простая цепь; 3 иы и4 из, из из — простая цепь; 4. иы из из ию из ие иг — цикл, но не простой цикл; 5.
иы из иа — простой цикл. Рис. 7.В. Маршруты, цепи, циклы 7.2.4. Расстояние между вершинами Длиной маршрута называется количество ребер в нем (с повторениями). Если маршрут М = ио,ег,имев,из,...,еаиы то длина М равна й (обозначается ~М( = к). Расстоянием между вершинами и и и (обозначается г)(и,и)) называется длина кратчайшей цепи (и, и), а сама кратчайшая цепь называется геодезической.
ЗАМЕЧАНИЕ Если Л (и,и), то по определению а(и,и):=+оо. Диаметром графа О (обозначается Р(С)) называется длина длиннейшей геоде- зической. Множество вершин, находящихся на одинаковом расстоянии и от вершины и (обозначенне Р(и, и)), называется ярусом: Р(и,о): =(и н Ъ' ) д(и,и) = и). 197 та. Виды графов и операции иед графами 7.2.5. Свяаность Говорят, что две вершины в графе связаны, если существует соединяющая их (простая) цепь. Граф, в котором все вершины связаны, называется связным. Отношение связанности вершин является эквивалентностью. Классы эквивалентности по отношению связанности называются компонентами связности графа.
Число компонент связности графа С обозначается й(С). Граф С является связным тогда и только тогда, когда й(С) = 1. Если й(С) > 1, то С вЂ” несвязный граф. Граф, состоящий только из изолированных вершин (в котором й(С) = р(С) и г(С) = 0), называется вполне несвязным. 7.3. Виды графов и операции над графами В данном разделе рассматриваются различные частные случаи графов и вводятся операции над графами и их элементами. Заметим, что не все из используемых обозначений операций над графами являются традиционными и общепринятыми.
' 7.3.1. Тривиальные и полные графы Граф, состоящий из одной вершины, называется тривиальным. Граф, состоящий из простого цикла с й вершинами, обозначается Сь. Пример Сз — треугольник, Граф, в котором каждая пара вершин смежна, называется полным, Полный граф с р вершинами обозначается К, он имеет максимально возможное число ребер: р(р 1) 2 Полный подграф (некоторого графа) называется квакай (этого графа), 7.3.2. Двудольные графы Двудольный граф (или биграф, или четный граф) — это граф С($; Е), такой что множество Ъ' разбито на два непересекающихся множества Ъ1 и 1з ($"~ О Ьг = У й Ъг Г1Ъз = И), причем всякое ребро из Е инцидентно вершине из Ъ'г и вершине из гз (то есть соединяет вершину из Ъ; с вершиной из )гз).
Множества Р; и 1'г называются долями двудольного графа. Если двудольный граф содержит все РебРа, соединЯющие множества 1гг и 1гз, то он называетсЯ полным двУдольным графом. Если (\",( = т и Я! = п, то полный двудольный граф обозначается й~и,и ° Пример На рис. 7.9 приведена диаграмма графа Лз з. 198 Глава 7. ГраФы рис. 7.9. Диаграмма граФа Кз,з ТЕОРЕМА Граф являвпгса двудольным тогда и только тогда, когда всв вго простыв циклы имеют чвглную длину. ДОКАЗАТЕЛЬСТВО Необходимость.
От противного. Пусть СЯ, з'з; Е) — двудольный граф, и омов,...,ива+мог — простой цикл нечетной длины. Пусть ог Е 'гы тогда ог Е 'зг, оз Е 'гы оз Е ью °,озь+г Е кы Имеем: ог, саь.~.г Е $", н (ог, еаь+г) Е Е, что противоречит двудольности. Достаточность. Не ограничивая общности, можно считать, что С вЂ” связный граф, поскольку каждую компоненту связности можно рассматривать отдельно. Разобьем множество Р на з'г и $'з с помощью следующей процедуры: Вход: граф С(зг, Е). Выход: Множества Ъ; и )гг — доли графа. зегесг о Е 'зг ( произвольная вершина ) 'гз . = и ( в начале первая доля содержит о, ... ) Ггз .
= зг ( ... а вторая пуста ) Гагин Ъ'~(о) ззо зг д(р, и) — четно ззгеп Ъ~. —— згг 0(и) ( в первую долю ) е!Зе 'гг . = зг2 О (и) ( во вторую долю ) епзз зг епзз Гог Далее от противного. Пусть есть две вершины в одной доле, соединенные ребром. Пусть для определенности и,тю и 'згз и (и, ш) Н Е. Рассмотрим геодезические (о, и) и (о, и) (здесь о — та произвольная вершина, которая использовалась в алгоритме построения долей графа). Тогда длины ! (о, и) ! и ~ (р, зв) ~ нечетны. Эти геодезические имеют общие вершины (по крайней мере, вершину о).
Рассмотрим наиболее удаленную от о общую вершину геодезических (о„и) и (о, зв) и обозначим ее р' (может оказаться так, что о = о'). Имеем: ! (о', и) / + ! (о', ю) / = ) (о, и) ! + ! (о, зо) ! — 2/ (о, о') ~ — четно, и о',..., и, зв,..., о'— простай цикл нечетной длины, что противоречит условию. Если же и, зв Н згы то 7.3. Виды графов и операции над графами длины ~ (о,и) ! и ~ (о,ш) ~ четны и аналогично имеем: о',...,и,«в,...,о' — простой цикл нечетной длины. с) 7.3.3. Направленные орграфы и сети Если в графе ориентировать все ребра, то получится орграф, который называется направленнььи. Направленный орграф, полученный из полного графа, называется турниром.
ОТСТУПЛЕНИЕ Название «турнир» имеет следующее происхождение. Рассмотрим спортивное соревнование лги пар участников (или пар команд), где пе предусматриваются ничьи. Пометим вершины орграфа участниками и проведем дуги от победителей к побежденным. В таком случае турнир в смысле теории графов — это как раз результат однокругового турнира в спортивном смысле.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
