Карточки
Тесты
Зави
Графы: вершины, ребра, степени, обход
В уроке «Таблицы и столбиковые диаграммы» вы читали схемы, на которых важны числа. Сегодня — схема, на которой важно только одно: что с чем соединено. Такую схему называют графом. Разберем, как считать линии графа, ничего не пропуская и не считая дважды, и когда граф можно обойти, пройдя каждую линию ровно один раз.
Карта, на которой важно только, что с чем соединено
Город Кенигсберг (сегодня Калининград) стоит на реке Преголе. В черте города река огибает два острова, и в XVIII веке берега и острова соединяли семь мостов. Жители спорили: можно ли прогуляться так, чтобы пройти по каждому мосту ровно один раз? Ни один из испробованных маршрутов не подошел. Но, может быть, нужный просто не нашли?
Леонард Эйлер заметил, что для ответа не важны ни длина мостов, ни форма берегов, ни ширина реки. Важно только, какие части суши соединяет каждый мост. Вообразавр предлагает сделать так же: представьте карту, на которой каждая часть суши — точка, а каждый мост — линия между двумя точками. Такая карта связей и есть граф.
Определение
Граф — набор точек (вершин) и линий (ребер), которые соединяют некоторые пары вершин.
Точки называют вершинами, линии — ребрами. Ребро, которое соединяет вершины $A$ и $B$, записывают так: ребро $A$–$B$.
Вершины — места или участники: части суши, города, люди. Ребра — связи между ними: мосты, дороги, рукопожатия. Граф задают список вершин и список ребер. Рисовать линии прямо или криво, длинно или коротко — дело рисунка, а не графа: на карте связей форма линии ничего не значит.
На рисунке три картинки одного графа: звезда, пятиугольник и петля из кривых линий. Вершины везде одни и те же — $A$, $B$, $C$, $D$, $E$, и ребра одни и те же — значит, и граф один.
Ошибка
Решавр смотрит на звезду и насчитывает $10$ вершин: пять точек с буквами и пять точек, где линии пересекаются. Проверим по списку ребер: в нем встречаются только $A$, $B$, $C$, $D$, $E$. В пятиугольнике тот же граф нарисован без пересечений, и лишних точек нет.
Рассуждение сломалось там, где пересечение линий приняли за место. Пересечение — случайность рисунка: перерисуйте граф, и оно исчезнет. Вершина — только то, что объявлено вершиной; на рисунках это отмеченная точка с буквой.
Каждое ребро считается с двух концов
Пять учеников $A$, $B$, $C$, $D$, $E$ отметили, кто с кем дружит. Дружба — ребро. Сколько друзей у ученика $A$? Из вершины $A$ выходят три ребра: к $B$, $C$ и $D$. Это число называют степенью вершины.
Определение
Степень вершины — число ребер, выходящих из этой вершины.
Степени: у $A$ — $3$, у $B$ — $2$, у $C$ — $3$, у $D$ — $3$, у $E$ — $1$. Сумма степеней $3 + 2 + 3 + 3 + 1 = 12$. А ребер на рисунке шесть: $A$–$B$, $A$–$C$, $A$–$D$, $B$–$C$, $C$–$D$, $D$–$E$. Сумма вдвое больше, и это не совпадение: у каждого ребра две стрелочки, по одной к каждому концу. Ребро $A$–$B$ попадает и в степень $A$, и в степень $B$ — каждое ребро учтено ровно два раза.
Правило
Сумма степеней всех вершин графа равна удвоенному числу ребер.
Ошибка
Решавр сложил степени, получил $12$ и записал: «В графе $12$ ребер». Проверим по рисунку: ребер шесть, а не двенадцать.
Рассуждение сломалось там, где ребра считали «у вершин». У вершин каждое ребро встречается дважды: ребро $D$–$E$ есть и в степени $D$, и в степени $E$. Сумма степеней — это число концов ребер, а не число ребер. Чтобы получить число ребер, сумму степеней делят на $2$.
Правило помогает проверять себя. Решавр насчитал в графе $9$ ребер и сумму степеней $20$. Ошибка видна без рисунка: при $9$ ребрах сумма степеней равна $2 \cdot 9 = 18$. Где-то пропущено ребро или неверна степень — нужно пересчитать.
Следствие
Вершину с нечетной степенью называют нечетной, с четной степенью — четной. В любом графе нечетных вершин четное число: $0$, $2$, $4$ и так далее.
Почему: сумма степеней четная — она равна удвоенному числу ребер. А нечетные слагаемые дают четную сумму, только если их четное число.
Пример
В компании $9$ человек. Может ли каждый быть знаком ровно с $5$ другими?
Решение. Нарисуем граф: люди — вершины, знакомство — ребро. Тогда у каждой из $9$ вершин степень $5$, и сумма степеней равна $9 \cdot 5 = 45$. Это нечетное число, а сумма степеней равна удвоенному числу ребер и должна быть четной. По-другому: все $9$ вершин нечетные, а нечетных вершин должно быть четное число.
Ответ: нет, так быть не может.
Сколько рукопожатий, если каждый пожал руку каждому
Четыре человека встретились, и каждый пожал руку каждому. Нарисуем граф: люди — вершины, рукопожатие — ребро. Граф, в котором каждые две вершины соединены ребром, называют полным. На рисунке в середине — полный граф на четырех вершинах, у него шесть ребер.
Посчитаем без рисунка, через степени. Каждый из четырех пожал руки трем другим, поэтому степень каждой вершины $3$, а сумма степеней $4 \cdot 3 = 12$. Каждое рукопожатие посчитано у обоих участников: $12 : 2 = 6$ — как ребер на рисунке. Для пяти человек: $5 \cdot 4 = 20$, $20 : 2 = 10$.
Правило
Если каждый из $n$ человек пожал руку каждому, то рукопожатий
Здесь $n-1$ — сколько рук пожал один человек, $n \cdot (n-1)$ — сумма степеней, а делим на $2$, потому что каждое рукопожатие посчитано у двух участников.
Пример
В классе $25$ учеников, и каждый пожал руку каждому. Сколько было рукопожатий?
Решение. Каждый пожал $24$ руки; $25 \cdot 24 = 600$ — это сумма степеней, в ней каждое рукопожатие посчитано дважды. Рукопожатий $600 : 2 = 300$. Ответ $600$ — ошибка Решавра: сумма степеней вместо числа ребер.
Ответ: $300$ рукопожатий.
Пример
В турнире каждый сыграл с каждым по одной партии, всего сыграно $55$ партий. Сколько было участников?
Решение. Если участников $n$, то $n \cdot (n-1) : 2 = 55$, значит, $n \cdot (n-1) = 110$. Это произведение двух соседних чисел: $11 \cdot 10 = 110$. Проверка: $11 \cdot 10 : 2 = 55$.
Ответ: $11$ участников.
Когда карту можно обойти, пройдя каждую линию один раз
Начнем с известной задачи: нарисуйте конверт, не отрывая карандаша и не проводя ни одну линию дважды. Конверт — граф с пятью вершинами и восемью ребрами. Диагонали квадрата пересекаются, но, как и в звезде, это не вершина. Начнем из $A$: $A$–$B$–$C$–$D$–$A$–$C$–$E$–$D$–$B$. Все восемь ребер пройдены, каждое по одному разу. Такой маршрут — пример обхода графа.
Определение
Путь — последовательность вершин, в которой каждые две соседние соединены ребром, например $A$–$B$–$C$ в конверте.
Цикл — путь, который заканчивается в той же вершине, с которой начался, и не проходит ни по одному ребру дважды, например $A$–$B$–$C$–$A$.
Определение
Обход графа — путь по графу, проходящий по каждому ребру ровно один раз (эйлеров путь). Обход конверта выше — пример.
Граф связный, если из любой его вершины можно по ребрам дойти до любой другой. Иначе до части ребер не дойти.
Посмотрим на степени: у $A$ и $B$ — по $3$, у $C$ и $D$ — по $4$, у $E$ — $2$. Обход начался в одной нечетной вершине и закончился в другой. Почему? В вершину в середине маршрута входят по одному ребру и выходят по другому: каждый проход забирает пару ребер «вошли — вышли». Поэтому у вершин, где маршрут не начинается и не заканчивается, степень четная. Нечетными могут быть только начало и конец, то есть не больше двух вершин. Если маршрут вернулся в начало, нечетных вершин нет совсем.
Теорема
Связный граф можно обойти, пройдя по каждому ребру ровно один раз, тогда и только тогда, когда нечетных вершин в нем ноль или две.
При двух нечетных вершинах обход начинается в одной из них и заканчивается в другой. При нуле обход можно начать в любой вершине и вернуться в нее же — получится цикл (эйлеров цикл).
Почему нечетных вершин не больше двух, объясняют пары «вошли — вышли». Что при нуле или двух нечетных вершинах обход всегда найдется, примем без доказательства: оно длиннее.
Теперь мосты. Части суши — вершины: $A$ — остров Кнайпхоф, $D$ — остров Ломзе, $B$ и $C$ — северный и южный берега. Мосты — ребра. Вершины $A$ и $B$ соединяют два моста, и это два разных ребра; так же $A$ и $C$. Степени: у $A$ — $5$, у $B$, $C$ и $D$ — по $3$. Проверка: $5 + 3 + 3 + 3 = 14 = 2 \cdot 7$, мостов семь. Нечетных вершин четыре. Значит, обойти мосты нельзя: горожане не нашли маршрут, потому что его нет.
Ошибка
Решавр рассуждает: «Все части города соединены мостами, из любой можно попасть в любую. Значит, обход есть, нужно только поискать маршрут получше». Проверим: граф Кенигсберга связный, но нечетных вершин в нем четыре — обхода нет.
Рассуждение сломалось на слове «значит». Связность нужна — без нее до части ребер просто не дойти. Но ее мало: каждая вершина в середине маршрута тратит ребра парами, а четыре нечетные вершины не могут все оказаться началом или концом.
Пример
Какой один мост нужно было бы добавить в Кенигсберге, чтобы обход стал возможен?
Решение. Новый мост добавляет по единице к степеням двух вершин, которые соединяет. Если соединить две нечетные вершины, обе станут четными. Соединим берега $B$ и $C$: степени станут $A$ — $5$, $B$ — $4$, $C$ — $4$, $D$ — $3$. Нечетных вершин две, $A$ и $D$, — обход есть: $A$–$B$–$A$–$C$–$A$–$D$–$B$–$C$–$D$.
Ответ: например, мост между берегами $B$ и $C$. Все четыре вершины здесь нечетные, поэтому подойдет мост между любыми двумя частями суши.
Интересный факт: Эйлер и мосты
Скрыть
Леонард Эйлер (1707–1783) много лет работал в Петербургской академии наук. Его статья о семи мостах напечатана в трудах этой академии: том за 1736 год вышел в 1741 году. Что при нуле или двух нечетных вершинах обход всегда существует, строго доказал немецкий математик Карл Хирхольцер; его работа опубликована в 1873 году.
Где еще пригодится карта связей
Граф помогает везде, где есть места и связи: метро, дороги, турниры, знакомства. Считаем по тем же правилам: каждое ребро — с двух концов.
Пример
В школьном турнире по волейболу $5$ команд: 7А, 7Б, 7В, 7Г, 7Д; каждая должна сыграть с каждой по одному разу. На схеме ребро — сыгранный матч. Сколько матчей уже сыграно и сколько осталось?
Решение. Число матчей команды — степень вершины: 7А — $3$, 7Б — $2$, 7В — $3$, 7Г — $2$, 7Д — $2$. Сумма степеней $12$, значит, сыграно $12 : 2 = 6$ матчей. Всего нужно сыграть $5 \cdot 4 : 2 = 10$ матчей (как рукопожатий). Осталось $10-6 = 4$ матча — это пары, не соединенные ребром: 7А–7Д, 7Б–7Г, 7Б–7Д, 7В–7Г.
Ответ: сыграно $6$ матчей, осталось $4$.
Иногда у связи есть направление: улица с односторонним движением, «кто кого победил». Тогда на ребрах рисуют стрелки, и такой граф называют ориентированным. В этом уроке все графы без стрелок. Дальше в курсе граф встретится еще раз: дерево исходов, по которому перебирают результаты бросков монеты, — тоже граф.
Вывод
Граф — карта связей: вершины — места или участники, ребра — связи между ними, а форма рисунка ничего не значит. Все подсчеты на такой карте держатся на одной мысли: каждое ребро видно с двух концов, поэтому сумма степеней вдвое больше числа ребер. По семи мостам Кенигсберга за один проход пройти нельзя: на его карте четыре нечетные вершины.
Так проверяют, можно ли проехать все улицы района по одному разу, — например, маршрут поливальной машины или почтальона.
Попробуйте сами: нарисуйте граф улиц вокруг вашего дома и найдите нечетные вершины — можно ли обойти все улицы, не проходя ни одну дважды?
Часто задаваемые вопросы
На графике функции важны расстояния и масштаб. В графе важно только, какие вершины соединены ребрами: его можно перерисовать как угодно, и он останется тем же.
Да, если связей действительно две: в Кенигсберге остров и северный берег соединяли два моста, и это два разных ребра. В степени вершины учитывается каждое из них. В рукопожатиях и турнирах двух ребер между одной парой не бывает по смыслу.
Сумма степеней равна удвоенному числу ребер, то есть четная. А три нечетных числа вместе с любыми четными дают нечетную сумму. Поэтому нечетных вершин всегда четное число.
Если нечетных вершин две, начинайте в одной из них — закончите в другой; из четной вершины обход не получится. Если нечетных нет, начинайте с любой вершины — в нее же и вернетесь.
5
5
1
5