Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 102
Текст из файла (страница 102)
Если е~ = ез или ез = ез то результат очевиден. В противном случае существует цикл, содержащий в качестве ребер е, и ез, и цикл, содержащий в качестве ребер ез и ез. Если оба цикла содержат еь и ез, доказательство завершено. Если нет, то существуют различные циклы, содержащие ребро ег и, возможно, другие ребра вместе с ним. Пусть еоеьезез... етео — цикл, содержащий еы и еое',езез е,',ео — цикл, содержащий ез Пусть е,е,.ь,еоьз . е,. и е'еьь,еь+з ..е,' — пути максимальной длины в циклах еоеьезез .
е„,ео и еое',езез е,',ео, соответственно такие, что еь — ребро пути е,еьь~еььз.. еуп а ез — ребро пути еьеь+,еьь е,', причем е, = е'„и е = е,', но пути не имеют других общих точек. Значит путь е;е;~геььз е е,',е,' е'„является простым циклом, содержащим ребра еь и ез. Следовательно, отношение В транзитивно. ° РАЗДЕЛ 14.1. Алгвбрвичвскив свойства графов 663 ОПРЕДЕЛЕНИЕ 14.34.
Пусть для каждого класса эквивалентности Е; и отношения эквивалентности В К вЂ” множество вершин, инцидентных ребрам из множества Е;, н С,Я,Е,) — подграф графа С(КЕ) с вершинами Р1 и ребрами Е,. Подграф С1Я,Е,) называется компонентой двусвязности графа С(К Е). ТЕОРЕМА14.35. Если (а,Ь) и (с,д) — различные ребра из компоненты двусвязности С;(К, Е,), то в подграфе С<(й, Е,) существует простой цикл, содержащий в качестве ребер (а,Ь) и (с,д).
ДОКАЗАТЕЛЬСТВО. Если (а,Ь) и (с,д) — различные ребра из компоненты двусвязности С,(Ъ;, Е,), то в графе С(К Е) существует простой цикл, содержащий в качестве ребер (а, 6) и (с, д). Но если существует ребро (с, Ы) из этого цикла, не принадлежащее классу эквивалентности Ео то существуют два ребра из разных классов эквивалентности, которые входят в один простой цикл, что противоречит принципу построения классов эквивалентности. Доказательство приведенных ниже теорем предоставляется читателю. ТЕОРЕМА 14.36. Если компонента двусвязности С,(Ъ;, Е,) состоит из единствен- ного ребра е,, то е; — разрезающее ребро графа С. ТЕОРЕМА 14.37. Если каждые два различных ребра входят в общий простой цикл графа С(Ъ', Е), то граф С(Ъ', Е) — двусвязный. ДОКАЗАТЕЛЬСТВО.
Предположим, что каждые два различных ребра входят в один и тот же цикл. Если С(Тг, Е) содержит единственное ребро е„то результат очевиден. В противном случае, пусть и и и — вершины графа С и а — вершина на пути из вершины и в вершину и. Пусть (с,а) и (а, Ь) — различные ребра из этого пути.
Тогда (с, а)и (а,6) — ребра, входящие в один и тот же простой цикл, поэтому существует путь из Ь в с, который не проходит через вершину а. Согласно теореме 14.28 вершина а не может быть точкой сочленения. Следовательно, граф С(К Е) двусвязный. СЛЕДСТВИЕ 14.38. Подграф С<Я, Е,) — двусвязный.
ТЕОРЕМА 14.39. Если С;Я, Е,) и С,Я, Е,) — компоненты двусвязности графа С(Ъ; Е), то й й $~ содержит не более одной вершины. ДОКАЗАТЕЛЬСТВО. Если К й Р; содержит две вершины а и Ь, то существуют два ребра (а,с) и (Ь,д), принадлежащие классу эквивалентности Е,. По определению Е;, в С,Я,Е,) существует простой цикл, содержащий (а,с) и (Ь,д).
Следовательно, в графе С,Я, Е,) существует путь из вершины а в Ь. Аналогично, в графе С Я, Е ) существует путь из Ь в а. Но поскольку графы С,(К, Е,) и Сз(~', Е ) не имеют общих ребер, то путь из вершины а в Ь в графе С,(ка Е,), за которым следует путь из вершины Ь в а в графе СуЯ, Еу), является циклом, который содержит простой цикл. Но тогда в общем простом цикле существуют ребра из графов С;Я, Е,) и С Я, Еу), что противоречит принципу построения графа С,Я,Е;) и графа С,Я,Е,).
564 ГПЯВЯ 14. Некоторые специальные вопросы теории графов ТЕОРЕМА 14.40. Вершина а является точкой сочленения тогда и только тогда, когда для некоторого 1 ~ 1 эта вершина принадлежит )Г, О Ъ; для компонент двусвязности С,()г„ Е;) и С Я, Е,) ДОКАЗАТЕЛЬСТВО. Если а — точка сочленения, то сушествуют ребра (а, Ь) и (а, с) такие, что не сушествует пути из вершины Ь в с, не проходящего через а. (См. доказательство теоремы 14.37.) Следовательно, ребра (а, Ь) и (а, с) не входят в один и тот же простой цикл и, значит, принадлежат различным компонентам двусвязности, например, С,Я, Е,) и С Я,Е,). Поэтому а Е 1г, О Ъ', Обратно, если а Е р) ОЪ'„то существует ребро (а, Ь) из класса эквивалентности Е; и ребро (а, с) из класса еквивалентности Есь Но при этом не существует другого пути из Ь в с, кроме как через а.
Иначе (а, Ь) и (а,с) были бы ребрами одного и того же простого цикла, что противоречит построению множеств Е, и Е,. Следовательно, а — точка сочленения. ТЕОРЕМА 14.41. Граф С(Ъ; Е) является двусвязным тогда и только тогда, когда любые два различных ребра входят в один и тот же простой цикл графа С(Ъ; Е). ДОКАЗАТЕЛЬСТВО. Половина утверждения теоремы является переформулировкой теоремы 14.37.
Предположим, что в графе С(1г, Е) имеются два различных ребра, которые не входят в общий простой цикл графа С(1г, Е). Тогда они принадлежат различным компонентам двусвязности. Следовательно, соединяющий их путь должен проходить через вершину, которая, согласно предыдущей теореме, является точкой сочленения, общей для этих компонент двусвязности. Поэтому граф С(1г, Е) не является двусвязным.
° УПРАЖНЕНИЯ 1. Для каждой приведенной ниже пары графов ваго графа во второй, если он существует. а) "з к~ найдите гомоморфизм из пер- [ ь к~ ТЕОРЕМА 14.42. Если С,()х, Е,) — компонента двусвязности графа С(Ъ;Е) и С,(1г„Е;) ф С($г, Е), то существует, по крайней мере, одна несовпадающая компонента двусвязности С (Ь), Е,) такая, что Р) йЪ' содержит ровно одну вершину. ДОКАЗАТЕЛЬСТВО. Согласно теореме 14.39, для любых двух различных компонент двусвязности Ъ; и Ъ', пересечение множеств 1г, О Ъ; содержит не более одной вершины. Однако, если а Е Ь; и Ь ф У„сушествует путь из вершины а в 6, и последняя вершина и по ходу пути, принадлежащая )г„ является элементом пересечения множеств й и Ъ' для некоторого ~'. 566 ГЛАВА 14. Некоторые специальные еопросы теории ерэфое 2.
Для каждой приведенной ниже пары графов опишите изоморфизм или покажите, что вследствие нарушения инвариантностн графы не изоморфны. а) с б) Ф а в) 5 б Ь с 'СК к, к, г) РАЗДЕЛ 14.1. Алгебраические сеойсглеа графов 567 е) Ь с 3. Для каждой приведенной ниже пары графов опишите изоморфизм или покажите, что вследствие нарушения инвариантности графы не изоморфны. а) б) а Ь в) 568 ГЛАВА 14. Некоторые специальные вопросы теории графов г) д) Ув Ь с е) 5 б у 4. Для каждой приведенной ниже пары графов опишите изоморфизм или покажите, что вследствие нарушения инвариантности графы не изоморфны. а) РЯЗДЕЛ 14.1.
Япгеораические сеойстеа графов 569 а Ь с И е 570 ГЛА8А 14. Нвкоторыв спвииапьныв вопросы теории врвфов 5. Какой из приведенных ниже графов является производным от графа, изображенного на рис. 14.20? с а Ь Рис 14 во а) а Ь г) в) Ь > в Ь 6. Какой из приведенных ниже графов является производным от графа, изображенного на рис. 14.21? К Рис. 14.2! РЯЭДЕЛ14.1. Алгвсрвцчвскив свойсгсвв графов 571 а) б) г) в) Ь с 7.
Какие из приведенных ниже пар графов гомеоморфны) а) Я б) а Ь М У Я в) в Ь Х 672 ГЛАВА 14. Некоторые специальные вопросы теории графов г) и о е г д) е) а Ь М~ с Ы е 8. Какие из приведенных ниже пар графов гомеоморфны? а) о Я Ь РАЗДЕЛ 14.1.
Алаебраические сеойопеа арафое 573 в) г) а Ь д) а Ь е) а Ь с 9. Найдите объединение и пересечение приведенных ниже множеств графов а) Ь с Ь с 676 ГЛввВА те. Некоторые специальные вопросы теории графов г) в) "г Ув е) д) е, иг егг кв 12. Задан граф С, изображенный на рис. 14.22. Какие из приведенных ниже графов являются его остовными графами? У Рис.
14.22 б) а) Ь в) г) Ь '! 13. Задан граф С, изображенный на рис. 14.23. Какие из приведенных ниже графов являются его остовными графами? РАЗДЕЛ 14.1. Алгебраические свойства графов 577 Рис. 14.23 б) а) г) в) 14. Покажите, что любой гомоморфизм из графа, изображенного на рис. 14.24, на граф С является изоморфизмом. ! Рис.
!4.24 15. Покажите, что если С и С' — графы, Г: С вЂ” С' — гомоморфизм, а граф С связный, то граф С' может быть несвязным. 16. Докажите теорему 14.3. Если граф С связный и à — гомоморфизм, то граф Г(С) тоже связный. 17. Докажите теорему 14.4.
Если граф С полный и 7' — гомоморфизм, то граф Г(С) тоже полный. 18. Докажите теорему 14.17, Если графы С1 и Сз являются различными компонентами графа С, то графы Сг и Сз попарно непересекаюшиеся. 19. Докажите теорему 14.18. Граф С вЂ” объединение попарно непересекающихся компонент. 20. Докажите теорему 14.23.
Если ТЯ, Е') — остовное дерево графа С = (К Е), то для любого цикла иоигигизи4,. ио в графе С, по крайней мере, одно ребро должно принадлежать множеству Š— Е'. 21. Докажите, что если граф С связный и à — гомоморфизм, то граф ДС) тоже связный. 22. Покажите, что если С(Ъ', Е) и С'(Ъ', Е') — графы, У: С вЂ” С' — изоморфизм, и вершина и Е Ъ' имеет степень и, то в графе Г(С) вершина Г(и) 678 ГПА8А 14. Некоторые спеццвпьные вопросы теории графов необязательно имеет степень и.
Что можно сказать о степени вершины 7'(с) как о вершине графа 1(С)? Что можно сказать о степени вершины Г(э) как о вершине графа С'? Покажите, что если графы С и С' — изоморфны, то они имеют одинаковое количество вершин и ребер. Покажите, что если à — изоморфизм из графа С в граф С', то граф С связный тогда и только тогда, когда граф С' связный.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
