В графе 30 вершин и 80 ребер каждая вершина имеет степень 5 или 6 сколько в нем вершин степени 5

Под графом мы будем понимать множество точек ( вершин ), некоторые из которых соединены отрезками ( ребрами ).
Степень вершины графа — это количество выходящих из нее (или, что то же самое, входящих в нее) ребер (еще говорят: количество ребер, инцидентных данной вершине). Вершина графа называется четной , если ее степень четна, и нечетной в противном случае.
Некоторая часть вершин данного графа называется компонентой связности , если из любой ее вершины можно «дойти» до любой другой, двигаясь по ребрам.

В некоторых случаях на ребрах графа выбирается «направление движения» (например, когда на автомобильной дороге вводится одностороннее движение). При этом получается ориентированный граф . (Если направление движения по ребрам не определено, то граф называется неориентированным ). В ориентированном графе различают положительную и отрицательную степень каждой вершины (то есть количество ребер, соответственно, входящих и выходящих из нее). Две вершины могут быть соединены и несколькими ребрами, направления движения по которым противоположны («дорога с двусторонним движением»). Изменяется понятие компоненты связности: теперь каждый «маршрут» от одной вершины до другой должен учитывать направление движения по ребрам.

Задачи

1. Между девятью планетами Cолнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля — Меркурий, Плутон — Венера, Земля — Плутон, Плутон — Меркурий, Меркурий — Венера, Уран — Нептун, Нептун — Сатурн, Сатурн — Юпитер, Юпитер — Марс и Марс — Уран. По каждому маршруту ракеты летают в обе стороны. Можно ли долететь на рейсовых ракетах от Земли до Марса?

Решение.
Построим граф, вершинами которого являются планеты Солнечной системы, а ребрами — существующие маршруты рейсовых ракет. Изобразив такой граф на рисунке, нетрудно заметить, что он состоит из двух компонент связности (на нашем рисунке они выделены разными цветами). Земля и Марс оказываются в разных компонентах связности, поэтому долететь от Земли до Марса на рейсоых ракетах нельзя.

2. Доска имеет форму двойного креста, который получается, если из квадрата 4×4 убрать угловые клетки. Можно ли обойти ее ходом шахматного коня и вернуться на исходную клетку, побывав на всех клетках ровно по одному разу?

Ответ. На рисунке указано одно из возможных решений (клетки пронумерованы в том порядке, в котором их обходит конь).

3. Можно ли, сделав несколько ходов конями из исходного положения (верхний рисунок), расположить их так, как показано на нижнем рисунке? (Выходить за пределы поля 3×3 не разрешается.)

Решение. Пронумеруем клетки поля 3×3, как показано на рисунке слева. Построим граф, вершинами которого являются эти клетки. Две клетки соединим ребром графа, если из одной в другую можно попасть за один ход коня. Расположим вершины графа так, как показано на рисунке справа, и проведем все ребра. Отметим на этом рисунке начальное и конечное местоположение коней. Для того, чтобы осуществить требуемую перестановку коней, нужно по крайней мере, чтобы, например, один из черных коней «перепрыгнул» через одного из белых. Но кони ходят по очереди, и ни в какой момент времени на одной клетке не могут оказаться два коня сразу. Поэтому осуществить такое «перепрыгивание» невозможно. Стало быть, невозможно и переставить коней требуемым образом.

4. В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией в том и только в том случае, если двузначное число, образованное названиями городов, делится на 3. Можно ли долететь по воздуху из города 1 в город 9?

Построим граф, вершинами которого являются города, а ребрами — существующие авиалинии. Вспомним признак делимости на 3: натуральное число делится нацело на 3 тогда и только тогда, когда сумма его цифр делится на 3. Заметим, что если название города делится на 3, то он соединен авиалиниями только с городами, названия которых тоже делятся на 3. Наоборот, те города, названия которых не делятся на 3, не могут быть соединены авиалиниями с городами, названия которых делятся на 3. Поэтому города 3, 6 и 9 образуют одну компненту связности графа, в которую никакие другие города не входят. Это означает, что из города 1 в город 9 добраться по воздуху нельзя.

Упражнение: А какие еще компоненты связности есть в этом графе?

5. В государстве 100 городов. Из каждого города выходит 4 дороги. Сколько всего дорог в государстве?

Решение. Обойдем по очереди все города, считая дороги, входящие из них. Всего таким способом мы насчитаем 400 дорог. Но каждая дорога выходит из двух городов, значит, каждую дорогу мы посчитали два раза. Поэтому на самом деле дорог в государстве в два раза меньше, чем мы насчитали, то есть 200.

Теорема 1. Количество ребер в любом графе равно половине суммы степеней его вершин.
Докажите эту теорему самостоятельно по аналогии с задачей 5.

6. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?
Подсказка: попытайтесь посчитать количество телефонных проводов.

Решение. В качестве вершин графа возьмем телефоны, а в качестве ребер — телефонные провода. Применим к этому графу теорему 1. Степень каждой вершины графа равна 5, значит, сумма степеней всех вершин равна 5·15=75. Это нечетное число, поэтому его половина — число нецелое. То есть в нашем графе нецелое число ребер, и в городе нецелое число проводов, чего быть не может.

Следующую задачу в силу ее важности сформулируем в виде теоремы. 7. Теорема 2. Всякий (неориентированный) граф содержит четное число нечетных вершин.

Доказательство. По теореме 1 количество ребер графа равно половине суммы степеней всех вершин графа. Все вершины графа делятся на четные и нечетные. Сумма степеней четных вершин графа всегда четна. А вот сумма нечетного количества нечетных чисел нечетна, поэтому если нечетных вершин нечетное количество, то сумма их степеней будет нечетна. Тогда сумма степеней всех вершин графа будет нечетна. Половина этой суммы будет нецелым числом, то есть в графе нецелое число ребер, а такого быть не может. Полученное противоречие доказывает, что количество нечетных вершин графа не может быть нечетным.

При решении всех последующих задач мы будем пользоваться этой теоремой. Любое решение следует начинать с выбора вершин и ребер графа. Попробуйте решить эти задачи самостоятельно, не ссылаясь на теорему, а заново проводя ее доказательство в каждом конкретном случае.

8. В классе 30 человек. Может ли быть так, что 9 человек имеют по 3 друга, 11 — по 4 друга, а 10 — по 5 друзей?

Решение. Сделаем учеников вершинами графа, а ребрами будем соединять тех из них, которые дружат между собой. По условию в таком графе четных вершин будет 11, а нечетных 9+10=19, то есть нечетное число, что противоречит теореме 2.

9. Школьник Вася Пупкин сказал своему приятелю Вите Иванову:
— У нас в классе тридцать пять человек. И представь, каждый из них дружит ровно с одиннадцатью одноклассниками.
— Не может этого быть, — сразу же ответил Витя Иванов, победитель математической олимпиады.
Почему он так решил?

Решение. Решение этой задачи полностью аналогично решению задачи 6.
10. У короля 19 вассалов. Может ли оказаться так, что у каждого вассала 1, 5 или 9 соседей ?

Решение. Сделаем вассалов вершинами графа; ребрами соединим тех из них, которые являются соседями. По условию все вершины этого графа нечетны, а всего их 19, то есть тоже нечетное число. Но по теореме 2 такого быть не может.

11. Может ли в государстве, в котором из каждого города выходит ровно 3 дороги, быть ровно 100 дорог?

Решение. Сделаем города вершинами графа, а дороги — его ребрами. По условию в этом графе 100 ребер, а по теореме 1 число ребер равно половине суммы степеней всех вершин. Значит, сумма степеней всех вершин равна 200. Но степень каждой вершины по условию равна 3, а 200 не делится на 3. Полученное противоречие доказывает, что такого быть не может.

12. В школе 953 ученика. Одни из них знакомы, другие не знакомы друг с другом. Доказать, что хотя бы у одного из них число знакомых среди учеников этой школы чётно.

Решение. Сделаем учеников вершинами графа и будем соединять ребрами тех из них, которые знакомы друг с другом. Если бы у всех школьников число знакомых среди учеников этой же школы число знакомых было нечетно, то все 953 вершины нашего графа были бы нечетными, что противоречит теореме 2. Значит, есть по крайней мере один школьник, у которого число знакомых среди учеников этой же школы четно. Более того, можно сказать, что таких школьников обязательно должно быть нечетное число (подумайте почему).

13. Докажите, что число людей, живших когда-либо на Земле и сделавших нечетное число рукопожатий, четно.

Решение. Сделаем всех людей, когда-либо живших на Земле, вершинами графа, а рукопожатия — его ребрами. (При этом две вершины могут соединяться и несколькими ребрами; такие ребра называют кратными .) Люди, сделавшие нечетное число рукопожатий, — нечетные вершины такого графа, поэтому по теореме 2 их количество четно.

14*. Докажите, что не существует графа с пятью вершинами, степени которых равны 4, 4, 4, 4 и 2 соответственно.

Решение. У каждой из первых четырех вершин степень 4, то есть каждая из этих вершин соединена ребрами со всеми остальными (поскольку всего вершин 5). В частности, каждая из этих четырех вершин соединена и с пятой вершиной. Поэтому если в графе с пятью вершинами четыре вершины имеют степень 4, то и оставшаяся вершина должна иметь степень 4.

15*. Можно ли расположить в пространстве 9 шаров так, чтобы каждый из них касался ровно пяти других?

Решение. Сделаем вершинами графа шары и соединим ребрами те из них, которые касаются друг друга. По условию в таком графе будет нечетное число нечетных вершин, что противоречит теореме 2.

16*. а) Можно ли нарисовать на плоскости 8 отрезков так, чтобы каждый пересекался ровно с тремя другими? б) Тот же вопрос для 9 отрезков.

Ответ. а) Да, см. рисунок; б) нет.

Решение. Сделаем отрезки вершинами графа и соединим ребрами те из них, которые пересекаются между собой. По условию п. б) в таком графе нечетное число нечетных вершин, что противоречит теореме 2. Для пункта а) это рассуждение не годится, однако это еще не означает, что сделать такой рисунок возможно. Чтобы это доказать, надо его нарисовать. Для этого достаточно придумать рисунок с 4 отрезками, каждый из которых пересекается ровно с тремя другими, а потом изобразить два таких рисунка рядом. (Здесь важно, что в условии фигурируют именно отрезки, а не прямые.)

ЗАДАЧИ
7 класс
Занятие 1
Занятие 2
Занятие 3
Занятие 5
Занятие 6
Занятие 7
Занятие 8
Занятие 10
Занятие 11
Занятие 12
Занятие 13
Занятие 14
Занятие 15
Занятие 16
Занятие 19
Занятие 20
Занятие 21

Вы видите ошибку? Выделите её и нажмите Ctrl+Enter!

Пути, циклы, связность

Путь в графе – это последовательность вершин , в которой каждая пара , , является ребром, причем все эти ребра различны. Путь соединяет вершины и . Длиной пути называется число ребер в нем, т.е. . Цикл – путь, у которого . Граф называется связным, если для любых двух его вершин имеется путь, соединяющий эти вершины. Если граф несвязен, то он состоит из нескольких связных частей, они называются компонентами связности. Шарнир (точка сочленения) в графе – вершина, при удалении которой увеличивается число компонент связности. Перешеек – ребро, при удалении которого увеличивается число компонент связности. Теорема о перешейках. Ребро является перешейком тогда и только тогда, когда через него не проходит ни один цикл. В ориентированном графе можно определить два типа путей. Ориентированный путь – это, как и в неориентированном случае, последовательность вершин , в которой каждая (упорядоченная) пара , , является ребром (и все эти ребра различны). Неориентированный путь – последовательность вида , где , а – ребра графа, причем или для каждого . Орграф называется связным, если между любыми двумя вершинами имеется соединяющий их неориентированный путь. Он называется сильно связным, если из любой вершины в любую другую имеется ориентированный путь.

Расстояния и метрические характеристики

Расстоянием между вершинами в графе называется наименьшая длина соединяющего их пути. Расстояние между вершинами x и y обозначается через . Эксцентриситет вершины – расстояние от нее до самой удаленной вершины: . Диаметр графа – максимальное расстояние между вершинами, то есть наибольший эксцентриситет: . Радиус графа – наименьший эксцентриситет: . Центральная вершина – вершина, эксцентриситет которой равен радиусу графа. Центр – множество всех центральных вершин. Диаметр и радиус графа связаны соотношениями: .

Графы пересечений

Пусть дано семейство множеств . Графом пересечений этого семейства называется граф с множеством вершин , в котором вершины и смежны тогда и только тогда, когда . Этот граф обозначается . Граф содержит в компактном виде информацию о том, какие множества из семейства имеют непустое пересечение. С другой стороны, семейство можно рассматривать как еще один способ представления графа . Следующая теорема показывает, что этот способ универсален, то есть любой граф можно представить как граф пересечений некоторого семейства множеств. Теорема о графах пересечений. Для любого графа существует такое семейство множеств F, что . Задачи 1.1. Граф задан множеством вершин и множеством ребер . Нарисуйте этот граф, постройте для него матрицы смежности и инцидентности, списки смежности. 1.2. Постройте матрицу инцидентности для графа, заданного списками смежности: 1.3. В графе 30 вершин и 80 ребер, каждая вершина имеет степень 5 или 6. Сколько в нем вершин степени 5? 1.4. В графе каждая вершина имеет степень 3, а число ребер заключено между 16 и 20. Сколько вершин в этом графе? 1.5. Найдите все абстрактные графы с 4 вершинами. 1.6. Найдите все абстрактные графы с набором степеней а) (2,2,2,3,3,4); б) (2,2,2,3,3,3). 1.7. Восстановите граф по его а) порожденным подграфам, полученным удалением одной вершины: б) остовным подграфам, полученным удалением одного ребра: 1.8. Граф имеет n вершин и m ребер. Сколько у него различных а) остовных; б) порожденных подграфов? 1.9. 1) Представьте граф как объединение трех графов с множествами вершин , , . 2) Верно ли, что любой граф с 6 вершинами можно представить как объединение трех графов с такими множествами вершин? 3) Верно ли, что любой граф с 6 вершинами можно представить как объединение трех графов с множествами вершин , , ? 1.10. Верно ли, что для любых графов и выполняется равенство ? 1.11. Найдите граф с минимальным числом вершин такой, что оба графа и связны. 1.12. Найдите граф с минимальным числом вершин такой, что оба графа и несвязны. 1.13. Изоморфны ли графы 1) и ; 2) и ; 3) и ? 1.14. Найдите граф с минимальным числом вершин , который не является суммой или соединением меньших графов. 1.15. Граф задан матрицей смежности: . Постройте для него матрицу расстояний между вершинами, найдите эксцентриситеты вершин, диаметр, радиус, центр. Изоморфны ли этот граф и дополнительный к нему? 1.16. Каково расстояние между вершинами (0,0. 0) и (1,1. 1) в графе ? Сколько имеется кратчайших путей между этими вершинами? 1.17. Какой наибольший диаметр может быть у графа с вершинами? Сколько имеется (абстрактных) графов с таким диаметром? 1.18. Найдите все (с точностью до изоморфизма) графы с 5 вершинами диаметра 3. 1.19. Может ли радиус графа в результате добавления одного нового ребра а) увеличиться; б) уменьшиться; в) остаться прежним? 1.20. Найдите все (с точностью до изоморфизма) графы с 5 вершинами радиуса 1. 1.21. Найдите все (с точностью до изоморфизма) графы с 4 вершинами, имеющие точно одну центральную вершину. 1.22. Постройте граф пересечений а) граней трехмерного куба; б) ребер графа . 1.23. Сколько ребер в графе пересечений ребер графа ? 1.24. Граф пересечений семейства интервалов на прямой называют графом интервалов. Какие из следующих графов являются графами интервалов: , , , , , , ? 1.25. Граф пересечений семейства дуг окружности называют графом дуг. Какие из графов предыдущей задачи являются графами дуг?

Перечисление графов

1.2. Постройте матрицу инцидентности для графа, заданного списками смежности:

1.3. В графе 30 вершин и 80 ребер, каждая вершина имеет степень 5 или 6. Сколько в нем

вершин степени 5?

1.4. В графе каждая вершина имеет степень 3, а число ребер заключено между 16 и 20.

Сколько вершин в этом графе?

1.5. Найдите все абстрактные графы с 4 вершинами.

1.6. Найдите все абстрактные графы с набором степеней а) (2,2,2,3,3,4);

1.7. Восстановите граф по его

а) порожденным подграфам, полученным удалением одной вершины:

б) остовным подграфам, полученным удалением одного ребра:

1.8. Граф имеет n вершин и m ребер. Сколько у него различных а) остовных;

б) порожденных подграфов?

1.9. 1) Представьте граф как объединение трех графов с множествами вершин

2) Верно ли, что любой граф с 6 вершинами можно представить как объединение трех

графов с такими множествами вершин?

3) Верно ли, что любой граф с 6 вершинами можно представить как объединение трех

1.10. Верно ли, что для любых графов и выполняется равенство

1.11. Найдите граф с минимальным числом вершин такой, что оба графа и

1.12. Найдите граф с минимальным числом вершин такой, что оба графа и

1.13. Изоморфны ли графы 1) и ; 2)и ; 3) и ?

1.14. Найдите граф с минимальным числом вершин , который не является суммой

или соединением меньших графов.

1.15. Граф задан матрицей смежности:

Постройте для него матрицу расстояний между вершинами, найдите

эксцентриситеты вершин, диаметр, радиус, центр. Изоморфны ли этот граф и

дополнительный к нему?

1.16. Каково расстояние между вершинами (0,0. 0) и (1,1. 1) в графе ? Сколько

имеется кратчайших путей между этими вершинами?

1.17. Какой наибольший диаметр может быть у графа с вершинами? Сколько имеется

(абстрактных) графов с таким диаметром?

1.18. Найдите все (с точностью до изоморфизма) графы с 5 вершинами диаметра 3.

1.19. Может ли радиус графа в результате добавления одного нового ребра а) увеличиться;

б) уменьшиться; в) остаться прежним?

1.20. Найдите все (с точностью до изоморфизма) графы с 5 вершинами радиуса 1.

1.21. Найдите все (с точностью до изоморфизма) графы с 4 вершинами, имеющие точно

одну центральную вершину.

1.22. Постройте граф пересечений а) граней трехмерного куба; б) ребер графа .

1.23. Сколько ребер в графе пересечений ребер графа ?

1.24. Граф пересечений семейства интервалов на прямой называют графом интервалов.

Какие из следующих графов являются графами интервалов: , , , , ,

1.25. Граф пересечений семейства дуг окружности называют графом дуг. Какие из

графов предыдущей задачи являются графами дуг?

Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями: