Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 41
Текст из файла (страница 41)
1.4. Построить все попарно неизоморфные несвязные 5-вершинные графы, не имеющие петель, кратных ребер и изолированных вершин. 1.5. Изобразить все попарно нсизоморфные 6-вершинные графы без петель и кратных ребер., состоящие: Ц из 4 компонент; 2) из 3 компонент; 3) из одной компоненты и имеющие 7 ребер и 2 висячие вершины.
1.6. Сколько существует попарно неизоморфных 6-вершинных графов без петель и кратных ребер со следующим набором степеней вершин: (2, 2, 3, 3, 3, 5)? 1.7. Сколько существует попарно неизоморфных, не имеющих петель и кратных ребер кубических графов с 6 вершинами? Есть ли среди них двудольныс графы? 1.8. Существует ли 6-вершинный граф без петель и кратных ребер, имеющий такой набор степеней вершин: (2, 2, 2, 4, 5, 5)? 1.9. Выяснить, какие наборы степеней вершин могут быть у 6-вершинных связных графов без петель и кратных ребер, имеющих 7 ребер и содержащих вершину степени 2 и вершину степени 3. Лля каждого допустимого набора степеней вершин построить пример соответствующего графа. 1.10.
Показать, что в любом графе без петель и кратных ребер, содержагцем не менее 2 вершин, найдутся 2 вершины с одинаковыми степенями. 1.11. Показать, что для всякого и ) 3 существует и-вершинный связный граф без петель и кратных ребер, содержащий п — 1 вершин с неравными друг другу степенями. З 1. Основные понятое теорие графов 207 1.12. Доказать, что в мультиграфе всякий замкнутый маршрут нечетной длины е > 3 содержит простой цикл.
Справедливо ли аналогичное утверждение для маршрутов четной длины? 1.13. Пусть 5(С) — наименьшая из степеней вершин графа С, не имеквщего петель и кратных ребер и содержащего и вершин (п > 2). 1) Доказать, что если б(С) > (и — 1)/2, то граф связен. 2) Показать, что в предыдущем утверждении заменить (п — 1)/2 на 0п — 1)/2) нельзя. 1.14. Индукцией по и доказать, что связный псевдограф с п вершинами содержит не менее и — 1 ребер ~п > 1). 1.15. Доказать, что если из связного мультиграфа удалить произвольное ребро, содержащееся в некотором цикле, то новый мульти- граф будет также связным. 1.16. Доказать, что в связном псевдографе любые две простые цепи максимальной длины имеют хотя бы одну общую вершину.
Верно ли, что у них всегда есть общее ребро? 1.17. Доказать, что всякий связный псевдограф, имеющий не менее двух вершин, содержит вершину., не являющуюся разделяющей. 1.18. Показать, что если в мультиграфе степень каждой вершины больше 1, то в нем есть цикл. 1.19. Пусть С произвольный граф без петель и кратных ребер, а С . его дополнение. Доказать,что: 1) хотя бы один из графов С или С связен; 2) если в С более 4 вершин, то хотя бы в одном из графов С или С имеется цикл; 3) если граф С несвязен или его диаметр не меньше 3, то диаметр графа С не больше 3; 4) если о --. разделяющая вершина графа С, то она не является разделяющей в графе С. 1.20. Граф (без петель и кратных ребер) называется еамодополнительнььн, если он изоморфен своему дополнению.
1) Показать, что если граф самодополнительный, то число вершин в нем равно либо 41 (1 > 1), либо 41+ 1 (1 > О). 2) Доказать, что среди 4-вершинных графов самодополнительным является только один, а среди 5-вершинных только два. 3) Показать, что самодополнительный граф связен. 4) Доказать, что диаметр самодополнительного нетривиального графа С удовлетворяет неравенствам 2 < 71(С) < 3. 1.21. Выяснить, сколько существует попарно неизоморфных графов без петель и кратных ребер, имеющих: 1) 6 вершин и 11 ребер; 2) 7 вершин и 18 ребер; 3) 8 вершин и 24 ребра; 4) 6 вершин, 7 ребер и 2 компоненты связности; 5) 8 вершин и удовлетворяющих следукзщему условикк сумма степеней всех вершин не меньше 53. 208 Га. $7.
Графы и сети 1.22. Пусть у графа без петель и кратных ребер п вершин и е компонент связности. Локазать, что число ребер в нем не меньше, чем и — е и не превосходит (и — з) (п — е + 1) /2. Вывести отсюда, что если у и-вершинного графа (и ) 2) число ребер больше (и — 2)(п — 1)/2, то он связный. 1.23. Локазать, что если в псевдографе имеются ровно две вершины ночетной степени, то существует цепь, соединяющая их.
1.24. Показать, что если в п-вершинном графе без петель и кратных ребер нет циклов нечетной длины и число ребер больше ((и — 1)/2)з, то граф связен (и ) 2). 1.25. Пусть С граф с п > 2 вершинами, не имеющий петель. Доказать эквивалентность следующих утверждений: 1) С -- связный граф с п — 1 ребрами; 2) С связный граф, но после удаления любого ребра получается несвязный граф; 3) лкебая пара различных вершин в графе С соединена единственной цепью; 4) граф С не имеет циклов, но добавление ребра, соединяющего любые двс различные вершины, приводит к появлению цикла. 1.26.
Локазать, что во всяком дереве с п ) 2 вершинами содержится нс менее двух висячих воршин. 1.27. Пусть п1 --- число висячих вершин у и-верщинного дерева, не содержащего вершин степени 2. Локазать, что п1 > п(2+ 1. 1.28. 1) Индукцией по и доказать, что каждое дерево с и > 2 вершинами является двудольным графом. 2) Какие деревья являются полными двудольными графами? 1.29. Изобразить все попарно неизоморфные деревья; 1) с 6 ребрами и 3 висячими вершинами; 2) с 6 ребрами и 4 висячими вершинами; 3) с Т ребрами и 3 висячими вершинами; 4) с 8 ребрами и 3 вершинами степени 3.
1.30. Подсчитать число попарно неизоморфных 7-вершинных де- 7 ревьев, удовлетворяющих условию ~~ д~(и,) < 26. 1.31. Описать все графы, являющиеся деревьями вместе со своими дополнениями. 1.32. Пусть и, т и е соответственно число вершин, число ребер и число компонент у мультиграфа С. Доказать, что: 1) число циклов у мультиграфа С не меньше, чем т — п+ з; 2) мультиграф С является лесом тогда и только тогда, когда т — и+я=О. 1.33.
Если графы С и Н, не имеющие петель и кратных ребер, изоморфны, то для каждого д > О число вершин степени 4 в графах С и ЕХ одинаково. Показать, что: 209 61. Оеноеные понятие теории ерофее 1) в том случае, когда в каждом из графов С и Н не более четырех вершин, сформулированное (необходимое) условие для изоморфности графов является также и достаточным; 2) это условие не является достаточным для графов с пятью и более вершинами, причем если число вершин не меньше 6, то даже для деревьев.
1.34. Среди пар графов, изображенных на рис. 6.1 — 6.5, указать пары изоморфных и пары неизоморфных графов. Ответ обосновать. Рис. 6.2 Рис, 6.1 Рис. 6.3 Рис. 6.5 Рис. 6.4 1.35. Ц Пусть С и Н не имеют петель и кратных ребер, являются двухсвязными, содержат по 6 вершин и по 8 ребер. Пусть, кроме того, граф С имеет ровно 2 вершины степени 2, а граф Н ровно 4 вершины степени 3. Изоморфны ли графы С и Н? 2) Известно, что 6-вершинные графы С и Н не имеют петель и кратных ребер, двухсвязны, содержат по 10 ребер и удовлетворяют следующему условию: степень одной вершины в каждом из них равна 4 (1 < 4 < 5), а степени всех остальных вершин равны 4з (дз < е?з).
Показать, что графы С и Н изоморфны. 1.36. Выяснить, существуют ли в графах, изображенных на рис. 6.6, подграфы, гомеоморфные графу С: 14 Г. П. Гаврилов, А. А. Сапоженко 210 Гл. Ъ7. Графы и сети Рис. 6.6 Рис. 6.7 Ц С = Кл (рис. 6.7,а); 2) С = Кв (рис. 6.7,б); 3) С = Кзз (рис. 6.7, в). 1.37. Пусть и нечетное число, не меньшее 3, и В," подмножество всех вершин куба В", имеющих вес й (см, гл, 1, з Ц.
Пусть ф— — подграф куба В", порожденный множеством В"„ь 0 Э Вь (ит1~/я' Ц Построить по одному совершенному паросочетанию в графах Сз и Св. 2) Показать, что в графе Ст существует совершенное паросочетание. 1.38. Ц Привести пример связного однородного графа степени 4, не имеющего петель и кратных ребер и не содержащего остовного простого цикла. 2) Локазатгь что всякий однородный псевдограф степени 4 можно представить в виде объединения двух реберно непересекающихся 2-факторов. 2. Ориентированные графы. Ориенпеированный псевдогуаф С = С('г; Х) определяется непустым (конечным) множеством г' и набором Х упорядоченных пар элементов из 1с.
Элементы множества )г называются вершинами, а элементы набора Х дугами (или ориентированными ребрами) ориентированного псевдографа С(г; Х). В наборе Х могут встречаться пары вида (и, и), называемые петлями, и одинаковые пары, называемые кратными (или параллельными) дугами. Пары (и, о) и (и, и) считаются одинаковыми лишь в том случае, когда и = о. Ориентированным мультиграфом называется ориентированный псевдограф, не содержащий петель.
Если в ориентированном псевдографе нет ни петель, ни кратных дуг, то он называется ориентированныи графом (или, короче, орграфом). Направленным гра- З'1. Основные понятия теории графов 211 фом называется такой орграф, который не имеет симметричных пар ориентированных ребер (т.е. множество Х у направленного графа не может содержать одновременно и дугу (и, о), и противоположно направленную дугу с»и,и)).
Пусть х = (и, и) дуга ориентированного псевдографа. Вершину и называют началом или начальной вершиной, а вершину о концом или конечной вершиной дуги х. В этом случае говорят также, что дуга х исходит из вершины и и заходит в вершину о. Если вершина о является началом или концом дуги х, то говорят, что и и х инцидентны. Нолустеленью исхода вершины о псевдографа С называется число дуг псевдографа С, исходящих из вершины о.
Полустепень исхода вершины о обозначается через од(о) или д»(о). Аналогично полу- степенью захода вершины о (обозначения: Ы (о) и с1 (о)) павывается число дуг псевдографае заходящих в вершину о. Заменяя каждук» упорядоченную пару (и, о) из набора Х ориентированного псевдографа С(1», Х) неупорядоченной парой Ги, о), состоящей из тех же элементов и и о, получаем псевдограф Н = (Ъ; Х"), ассоциированный с ориентированным псевдографом С(Ъ", Х). Ориентированные псевдографы С»Я, Х») и Сз()з, Хз) называются изоморфными., если существуют два таких взаимно однозначных соответствия ун Ъ» +» 7~ и уч Х» е» Хз, что для всякои дуги х = (и, о) е Х» справедливо соотношение ф(х) = (у»(и), у»(о)). Операции удаления вершины и дуги, а также понятия подграфа, остовного подграфа и порожденного подграфа определяются для ориентированных псевдографов аналогично тому, как это делалось в случае неориентированных псевдографов.
При определении ориентированных маршрута, замкнутого маршрута, цепи, цикла, простой цепи и простого цикла требуется (в отличие от определения соответствующих «неориентированных понятий»), чтобы последовательность (вершин и дуг) оы хы ог,хз,... ..., х„з, о„ы х„ы и„(г» > 2) удовлетворяла условию: каждая дуга х, (1 < 1 < и — 1) имеет вид (о,, оь»»), т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
