ответить на вопросы на стр 51 и сделать задание 68 и 69
Сверь числа и знаки с фото.
[обрезано: «…ому там степень вершины ничем не ограничена.»]
[Рисунок: простой граф с вершинами a, b, c, d, e, f, g, соединёнными рёбрами.] Рис. 35. Степени вершин
Таблица 43 Вершина | a | b | c | d | e | f | g Степень | 1 | 2 | 3 | 3 | 4 | 5 | 6
На рисунке 35 изображён простой граф с 7 вершинами. Их степени равны 1, 2, 3, 3, 4, 5, 6 (табл. 43). Мы уже поняли, что диапазон, в котором могут лежать степени вершин такого графа, — это числа от 0 до 6. Но всякий ли набор чисел из этого диапазона может служить степенями вершин? Скажем, можно ли построить простой граф с 7 вершинами, все степени которых равны 2? равны 3? Можно ли построить граф со степенями вершин 0, 1, 2, 3, 4, 5, 6? со степенями 1, 1, 2, 2, 3, 3, 4? Прежде чем читать параграф дальше, попробуйте построить такие графы (ещё раз напомним, что речь идёт о простых графах, в которых нет петель и кратных рёбер).
[внизу слева обрезано: «…енты теории графов»] 51
- Петя вбил в землю 5 колышков и соединил некоторые из них верёвками. Могло ли так получиться, что к каждому колышку привязано ровно по 3 верёвки?
- На олимпиаде по математике каждый из 30 участников решил по 4 задачи, а каждую задачу решило ровно 10 человек. Сколько задач было на олимпиаде?
Краткий ответ
Вопросы на стр. 51
- Все 7 степеней равны 2 — да (подходит цикл из 7 вершин).
- Все 7 степеней равны 3 — нет.
- Набор степеней 0, 1, 2, 3, 4, 5, 6 — нет.
- Набор степеней 1, 1, 2, 2, 3, 3, 4 — да.
№ 68 — нет, так получиться не могло. № 69 — на олимпиаде было 12 задач.
Главный инструмент
В простом графе (без петель и кратных рёбер) сумма степеней всех вершин равна удвоенному числу рёбер:
\[ \deg v_1+\deg v_2+\dots+\deg v_n = 2E \]
Отсюда два следствия, которыми решаются почти все эти задачи:
- сумма степеней всегда чётна;
- число вершин нечётной степени всегда чётно.
Стр. 51: разбор по пунктам
1) Все степени по 2 — можно. Строим цикл \(C_7\): семь вершин в кольцо, каждая соединена ровно с двумя соседями. Проверка: \(7\cdot 2=14\), значит рёбер \(14:2=7\) — как раз семь сторон кольца.
2) Все степени по 3 — нельзя. Если бы такой граф был, сумма степеней равнялась бы \(7\cdot 3=21\), а она обязана быть чётной. Противоречие. (Нечётное число вершин нечётной степени тоже сразу «сигналит» об ошибке.)
3) Набор 0, 1, 2, 3, 4, 5, 6 — нельзя. В графе с 7 вершинами степень 6 означает «соединена со всеми остальными шестью». Но тогда вершина степени 0 всё равно оказалась бы соединена с ней — а у неё рёбер быть не должно. Противоречие. Общее правило: в одном графе не могут одновременно встретиться степени 0 и \(n-1\).
4) Набор 1, 1, 2, 2, 3, 3, 4 — можно. Сумма \(1+1+2+2+3+3+4=16\) чётна, значит запрета нет — остаётся построить пример. Обозначим вершины \(A,B,C,D,E,F,G\) и возьмём рёбра \(AB, AC, AD, AE, BC, BD, CE, FG\). Считаем степени: \(A=4,\ B=3,\ C=3,\ D=2,\ E=2,\ F=1,\ G=1\). Рёбер 8, и \(2\cdot 8=16=4+3+3+2+2+1+1\) — сходится.
№ 68
Колышки — это вершины, верёвки — рёбра. Условие «к каждому колышку привязано ровно по 3 верёвки» означает, что все пять степеней равны 3. Тогда сумма степеней была бы
\[ 5\cdot 3 = 15, \]
а она должна быть чётной. Значит, такого графа не существует: не могло получиться.
№ 69
Считаем не задачи, а «решения»: каждый из 30 участников дал по 4 решения, всего
\[ 30\cdot 4 = 120 \]
решений. Каждая задача собрала ровно 10 решений, поэтому задач
\[ 120:10 = 12. \]
Проверка: 12 задач по 10 решивших — это 120 решений, и 30 участников по 4 задачи — тоже 120. Всё сходится.
