Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 43
Текст из файла (страница 43)
В определении, приведенном ниже, свойства пути очерчены более формально. Для удобства договоримся в оставшейся части этого раздела использовать символы сш иы оз, оз,... Ьь, и и и для обозначения вершин. ОПРЕДЕЛЕНИЕ 6.11. Пусть С = С()г,Е) — граф с вершинами ио, оы из, из,..., иь е Ъ' и ребрами еы ез, ез,..., еь е Е. Путем длины Ь из ио в иь (или между ио и иь) называется последовательность иоегигезизезиз... иьеьиь такая, что е, = (и, ми,).
Таким образом, путь длины й имеет 1с ребер. По причине избыточности обозначений в этом определении для графа в общем случае путь будет обозначаться через иоигиэиз... иь. Каждые два последовательных ребра пути имеют общую вершину, поэтому являются смежными. Простым путем из ио в иь называется путь, в котором нет повторяющихся вершин. РАздел вид Графы 249 ПРИМЕР 6.12. В графе, изображенном на рис. 6.13, "а У! г б Рис. ЕЛЗ из г!о в ьт велут пУти иоэ!г!гвзгбт, гбогбгигвзюби!игизгбт, сои! вбиьибизпг и спизгб,ивют Длины 4, 8, 6 и 4 соответственно. ПУти вовгигвьвт и иовзвбиавт ЯвлЯютсЯ пРостыми. П ОПРЕДЕЛЕНИЕ 6.13.
Граф С называется связиъбгб, если имеется путь между любыми двумя его различными вершинами. ПРИМЕР 6.14. Граф на рис. 6.14 не связный. Например, нет пути из ио в из и между гбг и иб. >'! ! б Рис. 6.14 Возвращаясь к рассмотрению графа на рис. 6.13, следует отметить, что путь пои! вгвзибв!игиьит можно сократить до ион! вгизит, Поскольку вершина в! повторялась, необходимо удалить часть пути между двумя появлениями вершины вг и после первого появления вершины г!! переходить сразу к г!г.
Аналогично, путь вов1юб взюб в507 можно сокРатить до иог!,гбб взг!т. Таким обРазом, если пУть включает какую-либо вершину иб более чем один раз, его можно сократить, удалив гб, и вершины, лежашие на пути между двумя появлениями вершины ьо Можно продолжать действовать таким образом, пока не будет исключено повторение любой из вершин. Проведенные рассуждения дают возможность сформулировать следующую теорему. ТЕОРЕМА 6.16. Пусть С = С()г, Е) — граф. Если существует путь из вершины гб, в вершину и., тогда сушествует простой путь из вершины и! в вершину о!. Комбинируя определение 6.!3 и теорему 6.15, приходим непосредственно к такому следствию (следствием называется теорема, которая непосредственно вытекает из другой теоремы).
СЛЕДСТВИЕ 6.16. Граф С является связным тогда и только тогда, когда между любыми двумя его вершинами существует простой путь. 260 ГЛАВА 6. Графы, ориентированные графы и деревья ПРИМЕР 6.18. Графы, изображенные на рис. 6.15 и 6.16, являются компонентами графа, представленного на рис. 6.14. Рис. 6.16 Рис. 6./б ОПРЕДЕЛЕНИЕ 6.19. Пусть С = (17,Е) — граф.,Циклом называется путь ненулевой длины, соединяющий вершину саму с собой и не содержащий повторяющихся ребер. Простым циклом называется цикл, соединяющий вершину и саму с собой и не содержащий повторяющихся вершин, кроме и.
Цикл называется п-циклом, если он содержит и ребер и и различных вершин. ПРИМЕР 6.20. Если опять рассмотреть граф на рис. 6.!3, то в нем пути иои1иаизиш иои1иаиьитиоиаизио, и|изизитиоиаиа и иоиаитизитиеиаизио являются циклами. При атом все циклы, кроме иои1 иаизитиоиаизио, простые. П Давайте теперь определим графы специального вида, которые пригодятся нам в следующих разделах.
ОПРЕДЕЛЕНИЕ 6.21. Граф называется лолным, если любые две его вершины соединены ребром. Полный граф с п вершинами обозначается через К„. ПРИМЕР 6.22. На рис. 6.17 показаны, соответственно, графы Кз, Кз, Ка и Кз. Рис. 6.17 ОПРЕДЕЛЕНИЕ 6.23. Граф С = (17, Е) называется двудольным, если Ъ' можно представить как объединение непересекающихся множеств, скажем, Ъ' = А! !В, так что каждое ребро имеет вид (а, Ь), где а е А и Ь е В. Таким образом, каждое ребро связывает вершину из А с вершиной из В, но никакие две вер- РАЭДел б.1.
Графы 251 шины из А или две вершины из В не являются связанными. Двудольный граф называется полным двудольным графом К „, если А содержит т вершин, В содержит и вершин и для каждого а Е А, 6 Е В имеем (а, Ь) Е Е. Таким образом, для каждого а а А и Ь Е В имеется связываюшее их ребро. Рис. б.18 ° УПРАЖНЕНИЯ графе на рис. 6.19? Которые из длину каждого из путей.
1. Что из приведенного ниже является путем в них являются простыми путями? Приведите а) аеЬГсг1; б) аесдаес; в) аеЬесг"Ы; г) аес~Ыа Гс. 2. Что из приведенного ниже является путем в них являются простыми путями? Приведите а) аЬсаЬсд; б) Ьсдеса; в) деЬасе; г) иесаЬ. графе на рис. 6.20? Которые из длину каждого из путей. а Ь с Ь с е Рис. б.20 Рис. б.19 3. Что из приведенного ниже является циклом в графе на рис. 6.21? Которые из них являются простыми циклами? Для каждого п-цикла приведите значение а) даЬс16ед; б) Ь~седЬГсЬ; в) аЬс1'е6)'са; г) аес1Ыа.
4. Что из приведенного ниже является циклом в графе на рис. 6.22? Которые из них являются простыми циклами? Для каждого п-цикла приведите значение п. а) аЬсг)Ьаеа; в) адсбеа; б) еЬсс~Ьсдае г) адЬсдеа. ПРИМЕР 6.24. Графы К1з, Кз з, Кз,з и Кз з приведены по порядку на рис. 6.18 252 ГЛАВА б.
Графы, ориентированные графы и деревья а Ь с а Ь Рис. 6,22 Рис. 6.21 5. Нарисуйте следующие графы: в) Кг,. б) Кцз', в) Кг4, г) Кз 4. 6. Докажите, что если граф содержит цикл от вершины и к самой себе, то он содержит простой цикл от вершины и к самой себе. 7. В игре "вытягивание палочек" некоторое множество их подбрасывается над столом.
Содержание игры — вытащить из образовавшейся груды палочки по одной, не нарушая положение других. Представьте себе, что "палочки"— вершины графа. Между двумя вершинами имеется ребро, если одна палочка касается другой. Что представляют собой компоненты этого графа? 8. Покажите, что каждому рефлексивному отношению соответствует граф с петлями и обратно, граф с петлями в каждой вершине описывает рефлексивное отношение. Верно ли, что каждому графу с петлями соответствует рефлексивное отношение? 6.2. ОРИЕНТИРОВАННЫЕ ГРАФЫ Во многих случаях необходимы графы, у которых ребра, по существу, представляют собой улицу с односторонним движением.
Это означает, что если рассматривается ребро, выходящее из вершины а в вершину Ь, то его нельзя рассматривать выходящим из вершины 6 в вершину а. Например, если граф моделирует поток нефти в трубопроводе, и если нефть течет из пункта а в пункт 6, нам не хотелось бы, чтобы поток был и в обратном направлении, из пункта Ь в пункт а. В последующих главах мы встретим применение ориентированных графов в сетях и теории автоматов. ОПРЕДЕЛЕНИЕ 6.25. Ориентированный граф или арграф С, который обозначается через С((г, Е), состоит из множества 1~ вершин и множества Е упорядоченных пар элементов из $', называемого множеством ориентированных ребер или просто ребер, если понятно, что граф ориентирован.
Элемент множества Е называется ориентированным ребром, Если (а, 6) е Е, то а называется начальной вершиной ребра (а, 6), а Ь называется конечной вершиной. Заметим, что понятие ориентированного графа допускает наличие петель, чего не было в случае простых графов. Тому есть, в основном, две причины. Во-первых, определение ориентированного ребра естественным образом включает понятие петли, т.к. петля у вершины а есть просто ребро (а,а). В случае РАЗДЕЛ 6.2. Ориентированные графы 263 неориентированных графов это нельзя было сделать, так как ребро неориентированного графа имеет вид (а, Ь), поэтому петля должна была бы иметь вид (а, а). Во-вторых, когда речь идет об отношениях, элемент может находиться в отношении с самим собой, что не имеет смысла для множеств, так как любой элемент присутствует во множестве только один раз.
И еще, понятие петли в большей степени присуще ориентированным графам. Ребро (а, Ь) ориентированного графа обозначается на диаграмме стрелкой из а в Ь. Отметим, что в простом графе ребро представляется двухэлементным подмножеством, чтобы подчеркнуть, что отношение симметрично, в то время как в ориентированном графе ребро представлено упорядоченной парой, чтобы акцентировать важность порядка и то, что (а,Ь) может быть ребром в орграфе, а (Ь,а) — нет. ПРИМЕР 6.26. Орграф, у которого Ъ' = (а,Ь,с) и Е = ((а, Ь),(Ь,с),(с, Ь), (с,а)), изображен на рис. 6.23. П ПРИМЕР 6.27. Орграф, у которого Ъ' = (а, Ь, с,д) и Е = ((а, Ь), (Ь, с), (с, с), (Ь, а), (а, Ь), (с,а), (а,а)), изображен на рис.
6.24. П Рис. 6.23 Рис. б.24 ОПРЕДЕЛЕНИЕ 6.28. Если (а,Ь) — ребро ориентированного графа С(Ъ;Е), так что а — начальная вершина, а Ь вЂ” конечная вершина ребра (а, Ь), тогда вершины а и Ь инцидентнги ребру (а, Ь). Вершина а называется смежной к вершине Ь. Вершина Ь называется также смежной от вершины а. ОПРЕДЕЛЕНИЕ 6.29. Степенью выхода вершины и называется количество ребер, для которых и является начальной вершиной, обозначается опЫея(и). Степенью входа вершины и называется количество ребер, для которых и является конечной вершиной, обозначается шйея(и). Если 1пг)ея(и) = О, то вершина и называется источником.
Если опрей(и) = О, то вершина и называется стоком. ПРИМЕР 6.30. В ориентированном графе на рис. 6.25 шдея(ио) = О, 1пдея(иг) = 1, шс1ея(из) = 2, шг1ей(из) = 2 и шс1ей(и4) = 3. Также опгаей(ио) = 3, опЫея(и1) = 2, опЫек(из) = 2, опСде8(из) = 1 и опрей(и4) = О. Таким обРазом, веРшина ров источник, а вершина иг — сток.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
