Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 41
Текст из файла (страница 41)
Основные понятия теории графов 205 ветствуюшей пары из набора Х. При этом, если не оговаривается противное, все вершины в графе сохраняются. Дополнением С графа С называется граф, в котором две вершины сможны тогда и только тогда, когда они не смежны в С. Если графы Сз и Сг изоморфны, то их дополнения также изоморфны.
Операция подразбагния ребра (и, о) в графе С = (1г, Х) состоит в удалении от Х ребра (и, и), добавлении к К новой вершины ю и добавлении к Х11(и, о)) двух ребер (и, ю) и (ю, о). Граф С называется подразбиением графа Н, если С может быть получен из Н с помощью операции подразбиения ребра, примененной конечное число раз.
В частности, подразбиенисм графа Н является и сам граф Н. Графы С и Н называются гомеоморфными, .если некоторые их подразбиения изоморфны. Объединение.м графов С = (1г, Х) и Н = = Щ У) называется граф г' = (Г 0 О, Х О у ). Деревом называется связный ациклический (т.е. не имеющий циклов) граф. Ациклический граф называется лесом. Полным называется граф, в котором любые две различные вершины смежны. Полный граф с и вершинами обозначается через К„. Пустым (,вполне несвязным) называется граф, не имеющий ребер. Вполне несвязный граф с л вершинами является, очевидно, дополнением полного графа К„и поэтому часто обозначается через К„.
Одновершинный граф без ребер называется тривиа ьным (его можно обозначать через Кь или Кз). Дв удаль ным называется граф, множество вершин которого можно разбить на два непустых подмножества (на две доли) 1гз и 1гг таким образом, что никакис две вершины из одной и той же доли нс являются смежными. Лвудольный граф с долями 1гз и 1'з и множеством ребер Х обычно обозначается через Я, )4з, Х).
Если каждая вершина из 1гь смежна с каждой вершиной из 1'з, то двудольный граф называется полным двудольным графом. Полный двудольный граф ('гы 1гг, Х), у которого ~$'~~ = пь и ~1гз~ = пг, обозначается через К„, „,. Справедлива следующая теорема Л. Кенига: граф является двудольным тогда и только тогда, когда в нем отсутствуют циклы нечетной длины. Граф называется однородным (или регулярным) графом сглгпени д, если все его вершины имеют степень д. Регулярный граф (подграф) степени 1 называется паросочетанаем. Регулярный граф степени 3 называется кубическим:, к-фактором графа называется его остовный однородный подграф степени к. Совершенным паросочетанигм графа называется его 1-фактор.
Максимальным паросочгтанием графа называется паросочетание, содержащее наиболыпее число ребер. Единичным и-мгрным кубом называется граф Н", вершинами которого являются двоичные наборы длины п, а ребрами неупорядоченные пары соседних наборов (см. гл. 1, ~) 1). 206 Гл. Рй Грифы и сети Вершина графа, при удалении которой увеличивается число компонент связности, называется разделяющей (или тонной сочленения). Граф называется 1-соязнььн, если при удалении любых й — 1 его вершин получается связный граф, отличный от тривиального. Всюду в данном параграфе под графом понимается граф без петель и кратных ребер.
1.1. Показать, что для произвольного псевдографа С = (Ъ; Х) справедливо равенство ~ ши) = 2~Х~. сеи Замечание. Это первая теорема теории графов (принадлежащая Леонарду Эйлеру и опубликованная в 1736 г.). 1.2. Обозначим через п,(С) число вершин степени з в графе С. Построить все попарно неизоморфные графы без петель и кратных ребер, у которых: 1) пз(С) = 1, пз(С) = п4(С) .= 2 и п,ф) = 0 при с' ф 2, 3, 4; 2) пз(С) = 3., пз(С) = 2, п4(С) = 1 и п,(С) = 0 при г ~ 2, 3, 4. 1.3. Изобразить все попарно неизоморфные 4-вершинные графы без петель и кратных ребер.
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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
