Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 43
Текст из файла (страница 43)
(Петля считается ориентированным циклом длины 1.) 1.47. Пусть орграф С (без петель и кратных дуг) является по меныпсй мере слабо связным. Пусть )г = (сы вг, ..., п„) — — множество его вершин (и > 2), Н' (с1) — с? (нз) = 1, 4+(сз) — с? (вг) = — 1, ем~'(в,) = сз (р,) при у = 3, ..., п. Доказать, что в орграфе С существует ориентированная (ны сг)-цепь, содержащая все его дуги. 214 Га.
11 Графы и сети 1.48. 1) Доказать, что ориентированный псевдограф, имеющий не менее 2 вершин, сильно связен тогда и только тогда, когда в нем существует ориентированный остовный замкнутый маршрут. 2) Можно ли в приведенном утверждении заменить замкнутый маршрут циклом'? 1.49. Доказать, что слабо связный псевдограф является сильно связным тогда и только тогда,, когда в нем существует ориентированный замкнутый маршрут, содержащий каждую дугу псевдографа хотя бы один раз.
1. 50. Пусть ориентированный псевдограф С можно представить в виде объединения некоторых его ориентированных замкнутых маршрутов Мы Мз,..., Ма (Й > 1), удовлетворяющих условию: каждые два соседних маршрута М и Мсы (1 ( ф ( й — 1) имеют хотя бы одну общую вершину. Показать, что псевдограф С сильно связсн. 1.51. 1) Привести пример 7-вершинного орграфа без петель и кратных дуг, опровергающий следующее утверждение: если полу- степени исхода и захода любой вершины орграфа положительные и четные, то для каждой вершины орграфа найдется контур, содержащий ее. 2) Показать, что орграфа без петель и кратных дуг, имеющего менее 7 вершин и опровергающего приведенное выше утверждение, не существует.
1.52. Доказать, что в конденсации С* произвольного ориентированного псевдографа С контуры отсутствуют. 1.53. Доказатгь что если ориентированный псевдограф С нс является сильно связным, то он будет односторонним тогда и только тогда, когда его конденсация С* имеет ориентированную остовную цепь. 1.54. Бескантурнььи ориентированным мультиграфом называется мультиграф, не содержащий контуров. Доказатгч что в бесконтурном ориентированном мультиграфе существует вершина с нулевой полустопонью исхода. 1.55. Доказать, что ориентированный псевдограф изоморфен своей конденсации тогда и только тогда, когда он является бесконтурным орграфом (не имеющим петель и кратных дуг). 1.56. Пусть С слабо связный ориентированный псевдограф, не являющийся односторонним.
Доказать, что в С не существует такой вершины, удаление которой дает сильно связный псевдограф. 1.57. Доказать, что слабо связный орграф является растущим деревом тогда и только тогда, когда лишь одна его вершина имеет нулевую полустепень захода, а полустепень захода любой из остальных верьтин равна 1. 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). Раскраской вершин графа (или ребер мультиграфа) называется сопоставление (приписывание, назначение) цветов (красок) вершинам графа (соответственно ребрам мультиграфа). Раскраска называется правильной., если смежные вершины (соответственно ребра) окрашены в разные цвета. Наименьшее число цветов, для которого существует правильная раскраска вершин графа С, называется хроматическим числом графа С и обозначается через у(С). Наименьшее число цветов, для которого существует правильная раскраска ребер мультиграфа С, называется хроматическим индексом (или хроматическим лассом, или реберно-хроматпическ1 и числом) мультиграфа С и обычно обозначается через Х'(С). Для хроматического числа графа С = ($; Х) справедливы следующие оценки Ц;г(С) ) ю(С), где ш(С) число вершин у наиболыпего полного подграфа графа С (так называемое кликовое число графа С); пз 2) с(С) ~),, где и = )1г! и гп = )Х); 3) х(С) < Ь(С) + 1, где Ь(С) = шах д(о).
ьег 217 ~8. Лоавареостпь е раскраска ерафов и «секций» в «секций» б Рис. 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 ребер.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
