В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 9
Текст из файла (страница 9)
1'ассматривая отношение 1'(г + 1) [1'(з), уое[кдаемся в том, что на отрезке [1, [и!2! ! функция /(г) убывает. Поэтому [к!21 ,~„' ['(г) ( — 1'(1) = — — О, з=т откуда на основании (3) заключаем, что теорема 12.1 р а. а Теор ем а 12.2. Диал[етры почти всех графов рав- пь[ 2. Для доказательства атой теоремы понадобятся следую- щее очевидное У т в е р ж д е н и е 12.3, Число всех графов из У(п), в каавдои из которых зафикспровапы одии и те лсе г ре- бер и одповревчеико отсутству[от й других фиксировакиь[х и (,) — в — г ребер, равио 2 ' 48 с Доказательство теоремы 122. Прежде всего заметпм, что диаметр почти каждого графа не меньше 2, поскольку только полный граф имеет диаметр 1.
Теперь убедимся, что диаметр почти каждого графа пе может быть больше 2. В множестве «г фиксируем вершину е«и непустое подмножоство Е« ~=. Ег, удовлетворяющее следуюп«нм двум условиям: 1) и1Ф Е«; 2) г=- ~И ~ ~ п — 2. Положим Иг = Ег~(Е«««в|) и выбором вершину и ~ Е«г.
Рассмотрим множество Уге е(п) всех графов из "1е У(п), в которых окружение вершины щ совпадает с б', а вершина о не смежна ни с какой вершиной из К Для графов из этого множества есть г обязательных ребер и и — 1 запрещенных. Согласно утверждению 12.3 ( ) — г — лтч ~ У не е (п) ~ = 2 ' Для выбора вершины о в множестве И' есть п — г — 1 возмоны«остей. Гели теперь Упе (п) = () Уо,,(п), то ')У ц„(п) ! ( (п — г — 1) ~ У не „, (и) ! = ©- —. (")-- + =(и — г — 1)2 ' (и2 ' Пусть, далее, У, (п) чн() У„,(.), где в качестве Е«фигурирует ка«кдое из подмножеств множества «г, удовлетворяющее указанным выше условиям 1) н 2).
При фпкснрованном г= !И для выбора мпоже«а — «« ства Е«есть ~ ) вариантов, поэтому г ) (У ° (п)~( ~~ ( г ))Уп (п)(( ",' Ел — «\,,(",)- — н г ) ()- е «л — «1 Г=, 4 в, л. Киеличел и лр. Далее используем формулу бинома Ньютона: для любых чисел а и Ь и натурального п верно равенство (а + Ь)" = ~ ( ) а" 'Ь' ( 6й здесь ( ) = 1). Согласно этой формуле ~о/ )2 "=( — ) — 1 — „, <( —,) Поэтому из (4) вытекает ! '()! (2) Обозначив У'(и) = () У„(и), '1 " имеем !У'(п)(<п)У, (п)(<п'2 ' ( —,) Далее получаем (у (о)( .,~З~ -г ( и(~)~ „(4) 11ш =1пптгг/ — 1 = О. В то же время легко видеть, что если У ' (п) — множество графов с диаметром более 2, то У" (и) — У'(п).
Действительно, возьмем произвольный п-вершинный граф 6, диаметр которого не менее 3. В нем существуют хотя бы две вершины о1 и о, расстояние между которыми равно трем. Очевидно, что Сан Уо, „(и), где Н=Х,(о1). Поэтому У (и) — У (и). Итак, почти нет графов с диаметром более 2, что и доказывает теорему. 1 С л е д с т в и е 12,4. Радиус почта каждого графа соепадает с диаметром этого графа и равен 2. ~> Очевидно, что т(О)~д(С) для любого графа 6. Поэтому достаточно показать, что почти нет графов радиуса 1. Рассмотрим множество У'(и) графов из У(п), в которых степень фиксированной вершины о равна и — 1, Имеем ( У (и)( 2( . ) 2(.)-.+~ откуда получаем, что число графов нз У(п), максимальная степень вершин которых равна п — 1, не превосходит ( ) — с+г числа п2 ' ° Но это означает, что почти нет графов, среди вершин которых есть хотя бы одна доминирующая. Поэтому почти нет графов радиуса 1, так как всякий граф радиуса 1 содержит хотя бы одну доминирующую вершину.
3 Теорема 12.5. Почти все графы илсеют едииствепную верилияу максимальной (лнышмальиой) степени. Т е о р е м а 12.6. Группа автоморфизжов почти каждого графа совпадает с едшшчпой группой. Доказательства этих теорем можно найти, например, в обзоре 121). УПРАЖНЕНИЯ 1, Пусть о и Н вЂ” дза графа. Докажите, что сели С 77, то ийжС. 2, Найдите зсс попарно пеизоморфпые графы пятого порядка.
3. Доказките, что три графа, изображенные па рис. 1.10, изоморфпы, а графы па рис. 1лм не изоморфны, 4. Найдите число помеченных (и, и)-графов. 5. Докажите, что осли порядок самодополпитсльпого графа равен и, то и = 0 (шоб 4) пли и — = 1 (шой 4). 8. Докажите, что пе все графы с тремя ребрами реберпо рекопструируемы. 7. Найдите самодополпптельный граф с минимальным отличным от 1 числом вершил. 8. Докажите, что для любых натуральных чисел и, и и й, удовлетворяющих условиям (и — 5+1т 1 ~(к( п, и — Ь( и( существует (и, и)-граф, имегощий ровно й компонент. 9. Докаязите, что если число ребер графа порлдка п ) 2 боль/е — 1) ше, чем ~ 2 ~, то оп связоп.
10. Докажите, что в связном графе люоые две простые цепи максимальной длины имеют общую вершину. Н. Докажите, что не существует графа, степени всех вершин которого попарно различны. 12. Докажите, что если 5(6) ) (в — 1)/2, то граф С связен. 13.
Нарисуйте все попарно неизоморфные кубические графы восьмого порядка. 14. Пусть 6 — граф, мповзество вершин которого совпадает с отрезком натурального ряда (1, 2, ..., и), а множество ребер определяется следующим условием: несовпадающие вершины и и и смежны тогда, когда числа и и о взаимно просты. а) Запишите матрицу смеизпости графа Сь б) Является ли граф С„связным) 4е 51 в) Дока>ките, что прн т ( и граф С„, являстсл порожденным подграфом графа С . 15. Докажите, что элемент матрицы (А (С))ь, аапимагащий позицн>о (б 1), равен числу (1, 1)-маршрутов длины й в графе С.
10, !!остройто граф, центр которого: а) состоит ровно из одной вершины; б) состоит ровно из трех вор>пип н яе совпадает с ьшожестиом всех вершин; в) совпадаот с множеством всех вершин. 17. Докажите, что дна графа, изображонные па рпс. 6.2, коспектральпы. 18. Матрица пазываотся вволпе унилодулвркой, если каждый ее минор равен 1, — 1 илп О Докажите, что матрицы ипцидсптпо- 1'пс 1 1 Рпс. 1.2 сти двудольпого графа в ориентированного графа вполне уш>мо. дулярны. 19. Докажите, что диаметр графа пе превосходит его удвоенного радиуса. 20.
Приводите пример графа, диаметр и радиус которого равны. 21. Докаи>иго, что (Ш т)-граф связан, если в нем отсутствуюз циклы нечетной длины и >в ) (и — 1)з»4. 22. 5!вплетая лв граф, нзображош>ый па рис. 1.1, двудольпым? 23. Найдито расстояпио >((и, и) в графе, г>зобралгишом па рпс. 1.2. 24. Докаяшто, что прп п ) 2 зисзда К>, по является реберпым графом. 25.
Пайдите группы автоморфизмов графа, изображенного па рис. И.5, простой цопи Р„простого цикла С и графа Петерсена. Докажите, что группа автоморфизмов графа Петерсена изоыорфпа симметрической группе Бь 26. Пайдитс граф минимального порядка, отличного от 1, с тождественной группой автоморфизиов, 27. Докаж>гто, что число помечоппых графов, изоморф>гых некоторому графу С порядка в, равна и!Дйп1 С(, 28. Сколько поьшчшшых графов порождают простая цепь Р, и простой цикл С ? Глава 11 Деревья Как показано в з 4, среди графов с фиксированными порядком и числом компонент лишь один имеет максимальное число ребер.
Другой крайний случай — минимальное число ребер — приводит к большому классу графов. Наиболее важными среди нпх являются связные графы, которые называются деревьями. Класс деревьев занимает в теории графов особое положение. С одной стороны, это достаточно просто устроенные графы, н многие задачи, весьма сложные в общей ситуации, длн деревьев решаются легко. Доказано, например, что все деревья реконструпруемы; несложно распозпаетсн тиоморфпзм деревьев. С другой стороны, деревья часто встречаются в областях, на первый взгляд пе пмеющкх отношения к теории графов.
Деревья открывались независимо несколько раз. Еще в прошлом веке Г. Кирхгоф ввел деревья и применил нх к исследованию электрических цепей, а А. Кэлп, перечисляя изомеры насыщенных углеводоров, еще раз открыл деревья и первым исследовал их свойства. Тогда же деревья были введены и исследованы К. ГКордапом как чисто математический объект. 5 13. Определение дерева Деревом яазывается связный граф, не содержащий циклов.
Любой граф без циклов называется анияличееким (илк лесом). Таким образом, компонентами леса являются деревья. На рпс. 13.1 изображены все доревья шестого порядка. Существует несколько вариантов опроделепня дерева; некоторые нз нпх отражены в следующен теореме. Теор ем а 13.1. Для (и, т)-графа С следуюиуае утверлсдения эквивалентны: 1) С вЂ” дерево; 2) С вЂ” связный граф и ш = п — 1; 53 3) С вЂ” ациклический граф и т = п — 1; 4) любые две несовпадающие вершины графа С соединяет единственная простая цепь; 5) С вЂ” ациклический граф, обладающий тем свойством, что если какую-либо пару его несмежных вершин соедшгить реброл, то полученный граф будет содержать ровно один цикл. > 1) ~ 2) Воспользуемся индукцпей по и.
Прп п = 1 утвернгдеппе тривиально. Пусть и ~ 1, е ы ЬС. В дорсве 6 пет циклов, слодоватсльпо, согласно лемме 4.8, граф Рас. 13.1 6 — е имеет ровно две компоненты Т1 и Ть каждая яз которых есть дерево. Пусть дерево Т~ является (пь пи)- графом, 1= 1, 2. По индуктивному предположеньпо верно равенство т;=и; — 1 Далее имеем т = т1 + та+ 1 =(и, — 1)+(пг — 1)+ 1 = = (п1 + пз) — 1 = и — 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
