Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 44
Текст из файла (страница 44)
1.58. Показать, что во всяком полном ориентированном псевдографе существует источник, т. е. вершина, из которой достижима любая другая вершина псевдографа. 215 1" Я. Паанвриввть и раскраска врафвв 1.59. Пусть С полный сильно связный орграф (без петель и кратных дуг), имеющий и > 3 вершин. 1) Доказать, что, каково бы ни было 6 (3 ( 6 ( и), для всякой вершины орграфа С найдется контур длины й, содержащий эту вершину. 2) Доказать, что если из орграфа С (при и > 4) удалить произвольную вершину, то результирующий орграф либо сильно связный, либо становится сильно связным после добавления одной подходящей дуги.
1.60. Показать, что в любом турнире существует гамильтонова цепь. 1.61. Доказать, что турнир является сильным орграфом тогда и только тогда, когда в нем имеется остовный контур (т.о. когда. этот турнир гамильтонов). 1.62. Пусть (ры ..., е„) множество вершин турнира. Доказать, что ~ ~(д~(п,)) = ~~ (и — 1 — Й~(е,)) . в=1 г=з 1.63. Пусть у вершины в турнира Т полустепснь исхода не меньше, чем полустепень исхода каждой другой вершины турнира. Доказать, что расстояние от вершины в до любой другой вершины турнира не превосходит 2.
1.64. Орграф С(Г, Х) без петель и кратных дуг называется тринзитивным, если из принадлежности дуг (и, о) и (е, и) множеству Х следует принадлежность множеству Х дуги (и, ю). Доказать, что конденсация всякого турнира является транзитивным турниром. 1.65. Доказать, что в любом транзитивном турнире существует гамильтонова цепь. 1.66. Пусть С(г; Х) -- орграф без петель и кратных дуг, а С(1', Х) -- его дополнение, т.е. орграф, имеющий то же множество вершин 1 и такое множество дуг, что (сы пз) Е Х тогда и только тогда, когда (вы пз) ~ Х (здесгь естественно, рз ~ ея).
Через 6(С) и 6(С) обозначим число гамильтоновых цепей в С и С соответственно. Доказатзь что 6(С) = 6(С) (пюй 2). 1.67. Пусть С($; Х) произвольный турнир и 6(С) число гамильтоновых цепей в нем. Доказать, что: 1) при изменении ориентации одной его дуги получается турнир С', у которого число 6(С') гамильтоновых цепей удовлетворяет условию 6(С') = 6(С) (шоб 2); 2) 6(С) — нечетное число. 3 2. Планарность и раскраска графов Мультиграф называется иланарньья, если ого можно изобразить на плоскости так, что любые две дуги кривых (в частности, отрезки прямых), изображающие ребра, либо не имеют общих точек, либо 216 Гл. 17. Графы и сети пересекаются только в точках, соответствующих вершинам графа; причем в любой точке пересечения сходятся лишь дуги (отрезки), сопоставленные ребрам, инцидентным именно той вершине, которой соответствует данная точка.
Такая геометрическая фигура, являющаяся изображением планарного мультиграфа, называется плоским мулшпиграфом. Внутренней гранью плоского мультиграфа называется конечная область плоскости, ограниченная простым циклом и не содержащая внутри себя никаких вершин и ребер мультиграфа, принадлежащих другим простым циклам. Простой цикл, ограничивающий грань, называется ее границей. Часть плоскости, состоящая из точек, не принадлежащих мультиграфу и никакой из его внутренних граней,. называется внешней гранью. Из этих определений следует, что в гранях могут располагаться «древовидные отростки» (в частности, концевые ребра и висячие вершины); они в границы граней не включаются.
Для связных плоских мультиграфов, содержащих и вершин, тп ребер и ф граней (считая и внешнюю), справедливо следующее соотношение, называемое формулой Эйлера: п — т -Ь 7" = 2. Очевидно, что мультиграф С планарен тогда и только тогда, когда планарен граф, получаемый из С заменой каждой совокупности кратных ребер одним ребром с соответствующими концами (т.е., например, совокупность кратных ребер с концами и и ю заменяется одним ребром (и, ш) ) . Критерий планарности (теорема Понтрягина — Куратовского).
Граф ланарен тогда и только тогда, когда ни один из его подграфов не гомеоморфен ни Кв, ни Кз з (см. рис, 6.7, б и рис. 6.4). Раскраской вершин графа (или ребер мультиграфа) называется сопоставление (приписывание, назначение) иветпов (красок) вершинам графа (соответственно ребрам мультиграфа).
Раскраска называется правильной., если смежные вершины (соответственно ребра) окрашены в разные цвета. Наименьшее число цветов, для которого существует правильная раскраска вершин графа С, называется хроматическим числом графа С и обозначается через у(С). Наименьшее число цветов, для которого существует правильная раскраска ребер мультиграфа С, называется хроматическим индексом (или хроматическим лассом, или реберно-хроматпичес»п и числом) мультиграфа С и обычно обозначается через Х'(С). Для хроматического числа графа С = ($; Х) справедливы следующие оценки Ц;г(С) > ю(С), где со(С) число вершин у наиболыпего полного подграфа графа С (так называемое кликовое число графа С); пз 2) г(С) >,, где и = )1с! и т = )Х); 3) х(С) < Ь(С) + 1, где Ь(С) = шах д(о).
ьег 217 ~8. Лоавареостпь е раскраска ерафов Пля хроматического индекса мультиграфа С = ()г, Х) имеют место следующие оценки: 1) у'(С) > Ь(С), где Ь(С) = шахд(е); 2) Х'(С) < [ — Ь(С)! (теорема К. Шеннона); 3) Х'(С) < Ь(С) + д(С), где д(С) = шах д(е, ш) и д(е, ш) от«) число ребер, соединяющих в С вершины е и ю, т. е.
д(С) мощность наибольшей из совокупностей кратных ребер в мультиграфе С; эта оценка получена В.Г. Визингом. Если С граф (без петель и кратных ребер), то Ь(С) < Х'(С) < < Ь(С) + 1. 2.1. Применяя критерий Понтрягина — Куратоижого, выяснить, планарны ли графы, изображенные; 1) на рис. 6.5, а, б; 2) на рис.
6.6, а, б, в. и «секций» в «секций» б Рис. 6.8 2.2. При каких п > 2 являются пленарными графы, изображенные на рис. 6.8, а, бу 2.3. Построить граф с 6 вершинами и 12 ребрами, содержащий одновременно подграфы, гомеоморфные Кв и Кз з. 2.4. Построить все попарно неизоморфные непланарные графы без петель и кратных ребер., содержащие 6 вершин и 11 ребер.
2.5. Построить однородный 9-вершинный граф (без петель и кратных ребер), который не планарен вместе со своим дополнением. 2.6. Используя формулу Эйлера, доказать нспланарность следующих графов: 1) Кз (рис. 6.7, б); 2) Кз 3 (рис. 6.4); 3) граф Петерсена (рис. 6.6, а); 4) граф, изображенный на рис, 6.6, в. 2.7. 1) Выяснить, какое наиъзеньшее число вершин нужно удалить из графа С, чтобы получился планарный граф, если: а) С -- граф Петерсена (рис.
6.6.,а); б) С граф, изображенный на рис. 6.9. 2) Выяснить, какое наименьшее число ребер надо удалить из графа С, чтобы получился планарный граф, если: а) С = Кв, б) С = В4; в) С -- граф ПетерРис, 8.9 2.8. Выяснить, существует ли планарный граф (без петель и кратных ребер), у которого: 1) 7 вершин и 16 ребер; 2) 8 вершин и 17 ребер. 218 Га. $1 Графы и сети 2.9.
Какое наибольшее число граней может быть у плоского 5-вершинного графа, не имеющего петель и кратных ребер? Изобразите такой граф. 2.10. 1) Существует ли плоский 6-вершинный граф (без петель и кратных ребер), у которого 9 граней? 2) Построить все попарно неизоморфные плоские 6-вершинные графы (без петель и кратных ребер), имеющие 8 граней. 2.11. Графы Сз и Сз плоские, б-вершинные, с одинаковым числом граней.
У графа Сз четыре вершины степени 4 и две вершины степени 3. У графа Сз две вершины степени 5, а остальные имеют степени меньше 5. Какие степени могут быть у остальных вершин графа Сз? Изобразите все такие графы С1 и Сз. 2.12. Доказать, что в каждом планарном графе без потель и кратных ребер есть вершина степени, не большей чем 5.
2.13. Плоский связный граф без висячих вершин, каждая грань которого, включая и внешнюю, ограничена циклом длины 3, называется шрианеуляаией. Показать, что триангуляция с п > 3 вершинами имеет Зп — 6 ребер и 2п — 4 граней. 2.14. Доказать, что если у связного планарного графа (без петель и кратных ребер), имеющего и вершин и т ребер, каждый простой цикл содержит не менее й ребер (й > 3), то т < й(п — 2)/(й — 2).
2.15. Доказать, что в любом планарном графе (без петель и кратных ребер), имеющем не менее 4 вершин, найдутся хотя бы 4 вершины, степени которых не больше 5. 2.16. Показать, что 6-связных планарных графов (без петель и кратных ребер) не существует. 2.17.
1) Показать, что плоский кубический граф, граница каждой грани которого имеет не менее 5 вершин, содержит по крайней мере 20 вершин. Привести пример такого графа. 2) Пусть С -" плоский связный кубический граф (без петель и кратных ребер). Через у, (г > 3) обозначим число тех граней графа.
С, каждая из которых ограничена 1 ребрами. Доказать, что ~ ~(6 — г)1, = 12. е>з 2.18. Найти хроматические числа и хроматические индексы графов, изображенных на рис. 6.1, рис. 6.3, рис. 6.5 и рис. 6.6. 2.19. Найти хроматическое число и хроматический индекс графа С; 1) С = В" (и > 1); 2) С = К„ (и > 2); 3) С = К „ (и > т > 1). 2.20. Граф (без петоль и кратных ребор) называется еамильтлоновым, если в нем существует простой остовный цикл (т.е. простой цикл, содержащий все вершины графа). Такой цикл называют еамильтоноеььи. Доказать, что если С вЂ” кубический гамильтонов граф, то 1'(С) = 3.
2.21. Пусть | длина самой длинной простой цепи в графе С, не имеющем петель и кратных ребер. Показать, что Х(С) < 1+ 1. 219 1'М. Яеревьл и сетпи 2.22. Пусть С граф без петель и кратных ребер и Ь(С) наибольшая из степеней его вершин. Показать, что г(С) < Ь(С) + 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
