Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 103
Текст из файла (страница 103)
23 24 Покажите, что если à — изоморфизм из графа С в граф С' и Н вЂ” компонента графа С, то 7'(Н) — компонента графа С'. 25 Покажите, что если à — изоморфизм из графа С в граф С' и вершина э е Ъ' имеет степень и в графе С, то вершина Г(о) имеет степень и в графе С'. 26 Покажите, что если à — изоморфизм из графа С в граф С' и граф С имеет эйлеров цикл, то граф С' тоже имеет эйлеров цикл. 27 Покажите, что если 7" — изоморфизм из графа С в граф С' и граф С имеет собственный эйлеров путь, то граф С' тоже имеет собственный эйлеров путь. 28 Покажите, что если à — изоморфизм из графа С в граф С' и граф С является двудольным, то граф С' тоже является двудольным.
29 30. Покажите, что если à — изоморфизм из С в С' и граф С является полным двудольным графом К „, то граф С' является полным двудольным графом Кть. 31. Докажите, что пересечение графа С = (Ъ; Е) и его дополнения представляет собой граф, состоящий только из вершин графа С и не содержащий ребер.
32. Докажите, что объединение графа С = (КЕ) и его дополнения является полным графом. 33. Покажите, что если à — изоморфизм из графа С в граф С' и е — разрезающее ребро графа С, то 7"(е) — разрезающее ребро графа С'. 34. Граф С вЂ” самодополнительный граф, если он изоморфеи своему дополнению (см, определение 14.19). Приведите пример самодополнительного графа. 35. Какая связь между матрицами смежности графа и его дополнения? 37.
*Пусть С и С' — графы, а В и В' — соответственно их матрицы смежности. Докажите, что граф С изоморфен графу С' тогда и только тогда, когда существует перестановка Р такая, что В' = РВР' = РВР 38. Найдите три разрезающих множества в графе, изображенном на рис. 14.25. Найдите точку сочленения. Имеются ли разрезающие ребра? а Ь Я Рис. 14,25 39. Найдите три разрезающих множества в графе, изображенном на рис.
14.26. Найдите точки сочленения. Найдите разрезающие ребра. 36. Покажите, что граф С1 изоморфен графу С тогда и только тогда, когда граф С; изоморфен графу С'. РЯ372ЕЛ 14. 1. Алгебраические свойстве гргфсе 579 ./ Рис. 14.26 40. Найдите три разрезающих множества в графе, изображенном на рис. 14.27. Найдите точки сочленения. Найдите разрезаюшие ребра. Ь Рис.
И.27 41. Докажите теорему 14.28. Ребро е графа С является разрезающим ребром графа С тогда и только тогда, когда оно не входит в цикл графа С. 42. Докажите теорему 14.27. Если Т(Ъ; Е') — остовное дерево графа С = (К Е) и С вЂ” разрезающее множество графа С, то С Г~ Е' ф о. 43. Докажите теорему 14.36. Если компонента двусвязности С,')гг, Е;) состоит из единственного ребра е„ то е; — разрезающее ребро графа С.
44. Дано следующее определение. Пусть С = С(1г, Е) — граф и Сы Сз, Сз,..., ф— подграфы графа С. Подграф С' графа С называется пересечением графов с Сы Сз, Сз,..., С„и обозначается П С„если 1. Для всех 1 С' -с С,. 2. Для всех 1 С" -с С -с С, то С" ~ С'. Покажите, что это определение эквивалентно определению пересечения, приведенному в данном разделе. 45. Дано следующее определение. Пусть С = С(К Е) — граф и Сы Сз, Сз,..., ф— подграфы графа С. Подграф С' графа С называется объединением графов и Сы Сз, Сз,..., С„и обозначается Ц С„если 1=1 1.
Для всех г С, -с С' 2. Для всех1С сС" сС, то С'-сС". Покажите, что данное определение эквивалентно определению объединения, приведенному в данном разделе. 580 ГЛАВА 14. Некоторые специальные вопросы теории графов 14.2. ПЛАНАРНЫЕ ГРАФЫ Интегральная микросхема состоит из слоев миниатюрных микросхем, впечатанных в пластину. В такой ситуации крайне важно исключить пересечение проводов в местах, не предназначенных для соединений.
Если изобразить места указанных соединений вершинами графа, то возникнет задача построения графа с непересекающимися ребрами. Важно отметить, что нас интересует возможность построения графа с непересекающимися ребрами. Например, граф, изображенный на рис. 14.28, изображается также другим способом (рнс. 14.29). Граф, изображенный на рис.
14.30, может быть изображен, как показано на рис. 14.31. Рис. 14.29 Риа ИгВ Рис. 14.3! Рис. 14.30 Если бы проблема, рассмотренная нами в разделе 6.1, заключалась в предоставлении двух видов коммунальных услуг трем домам или трех видов коммунальных услуг двум домам, то ее можно было бы решить, используя в каждом случае граф, изображенный на рис. 14.32, согласно которому линии снабжения не будут пересекаться. Рис. 14.32 Чтобы решить задачу о предоставлении коммунальных услуг трем домам, потребуются некоторые определения и методы. Начнем с наименования графов, обладающих указанными свойствами. ОПРЕДЕЛЕНИЕ 14.43. Планарным графом называется граф, который может быть изображен в плоскости, так что его ребра не пересекаются. Граф, который не является планарным, называется нелланарным.
РАЗДЕЛ 14.2. Пленарные графы 581 Рассмотрим граф как рисунок, изображенный на листе бумаги. Если граф планарен и нарисован так, что никакие линии не пересекаются, и его необходимо разрезать вдоль ребер, то граф окажется разделенным на части, включая внешнюю часть. Такие части называются гранями. Заметим, что граница каждой грани является циклом. ОПРЕДЕЛЕНИЕ 14А4. Грань планарного графа — максимальный участок плоскости такой, что любые две точки этого участка могут быть соединены кривой, не пересекающей ребро графа. Теперь докажем теорему, называемую формулой Эйлера, с помощью которой можно определять, является ли граф планарным.
ТЕОРЕМА 14.45. Если С вЂ” связный планарный граф, содержащий е вершин, е ребер и Г граней, то п — е+ Г = 2. ДОКАЗАТЕЛЬСТВО. Докажем утверждение, используя индукцию по числу ребер. Если е = О, то имеется одна вершина, нет ребер и есть одна грань, которая составляет всю плоскость. Поэтому имеем 1 — О+ 1 = 2, и теорема верна, если е = О. Отметим также, что если имеется одно ребро, то существуют две вершины и одна грань. Поэтому имеем 2 — 1+ 1 = 2; и теорема верна для е = 1. Предположим, что теорема верна для произвольного связного планарного графа, у которого й ребер, и имеется планарный граф Сгэы у которого й + 1 ребер.
Теперь удалим ребро, так что останется связный планарный граф С„, у которого к ребер, поэтому формула е — е + Г = 2 для него верна. После этого докажем, что формула также верна и для связного планарного графа Сг„ы Предположим, что граф Се+1 не имеет циклов. Движемся вдоль пути до тех пор, пока не достигнем вершины, из которой нет другого выходящего ребра. Это произойдет, если граф Сьч.1 не содержит циклы.
Найденная вершина будет иметь степень 1. Удалим эту вершину и ребро, инцидентное ей. Количество граней не изменится. При этом граф останется связным и планарным и будет иметь й ребер, значит формула п — е + Г = 2 верна. Поскольку количество ребер и количество вершин уменьшилось на 1, то значение выражения е — е + Г после процедуры удаления останется неизменным, поэтому е — е+ Г = 2 для связного планарного графа Сьэы Далее предположим, что граф Сгч.1 содержит цикл. Удалим из цикла ребро е, с инцидентными вершинами и, и сы но сами вершины оставим. Согласно теореме 14.28 известно, что все еще имеется путь из вершины сч в вершину оы так что граф остается связным.
Граф также остается планарным и будет иметь й ребер, так что выполняется формула и — е+Г = 2. Поскольку ребро е; входит в цикл, оно разделяет две грани. Следовательно, удаление ребра равноценно удалению грани. Таким образом, удалены одно ребро и одна грань. Поэтому значение выражения е — е+ Г не изменилось, и формула е — е+ Г = 2 справедлива для графа Сгч.ы ° Теперь имеется все необходимое для доказательства того, что граф, описывающий проблему предоставления трех видов коммунальных услуг трем домам, является полным двудольным графом Кз з и его нельзя изобразить без пересекающихся ребер.
882 ГЛЯВЯ 14. Некоторые специальные вопросы теории графов ТЕОРЕМА 14.48. Полный двудольный граф Кз з не является планарным. ДОКАЗАТЕЛЬСТВО. Используем метод приведения к абсурду и предположим, что граф Кз3 планарный. Если Кз3 планарный граф, и поскольку имеется девять ребер и шесть вершин, то 6 — 9 + ~ = 2, поэтому г" = 5. Пусть А и  — непересекающиеся трехэлементные множества вершин, формирующие множество Ъ' вершин графа Кз з.
Если начать путь из одного из непересекающихся множеств, например, А, и не повторять ребра, то можно попасть в вершину из множества В, вернуться в вершину из множества А, вернуться в вершину из множества В и, наконец, вернуться в вершину из множества А, прежде чем завершить цикл. Каждый цикл в Кз з представляет собой путь, длина которого, по меньшей мере, равна 4. Поэтому каждая грань определена циклом, в котором не менее четырех ребер. Следовательно, сумма ребер всех граней больше, чем 4г". Но каждое ребро подсчитывается не более двух раз, поскольку оно может служить границей только для двух граней.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
