"Информатика (базовый и углублённый уровень)", Гейн А.Г., Сенокосов А.И.
Граф — это модель, в которой объекты представлены вершинами, а связи между ними — рёбрами. Так можно описать дороги между городами, маршруты, знакомства или соединения в сети. По графу определяют, какие вершины связаны, и считают степень каждой вершины — число рёбер, к ней присоединённых. Главное свойство: сумма степеней всех вершин равна удвоенному числу рёбер. Отсюда следует, что вершин нечётной степени в любом графе чётное количество. Эти правила помогают анализировать графы и проверять, может ли существовать граф с заданными степенями.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Граф — совокупность вершин и соединяющих их рёбер. Его задают рисунком или списком: сначала указывают вершины, затем пары вершин, соединённых рёбрами. Такое описание позволяет изучать связи между объектами, не обращаясь к их внешнему виду.
Вершина графа — объект, изображаемый точкой и соединяемый рёбрами с другими вершинами. На рисунке вершины обычно обозначают буквами или числами. Вершины нужны, чтобы представить объекты сети: например, города, компьютеры или людей.
Ребро графа — соединение двух вершин; его концы называют концевыми вершинами. Вершины, соединённые общим ребром, называют смежными, а само ребро — инцидентным каждой из них. Это различие помогает точно описывать пары объектов и связи между ними.
Степень вершины — количество рёбер, инцидентных этой вершине. Её обозначают, например, deg(A) или d(A), и находят подсчётом всех рёбер, касающихся точки. Петля, соединяющая вершину с самой собой, учитывается дважды, поскольку имеет два конца.
Чтобы определить смежность, найдите вершины, входящие в одну пару из списка рёбер. Например, если указано ребро AB, вершины A и B смежны. Ребро инцидентно своим концам: AB инцидентно A и B, но не вершине C. Так списочное описание превращается в понятную картину связей.
Степень вершины показывает, сколько рёбер к ней присоединено, поэтому на рисунке нужно считать линии, касающиеся соответствующей точки. При нескольких рёбрах между одной парой вершин каждое считают отдельно: это разные связи. Петля добавляет к степени 2, так как оба её конца находятся в одной вершине. В простом графе петель и кратных рёбер нет, но при подсчёте в общем графе эти случаи учитывают.
Сумма степеней всех вершин равна 2m, где m — число рёбер. Причина в том, что у каждого обычного ребра два конца: при сложении степеней оно попадает в счёт у обеих вершин. Петля тоже даёт два вклада в степень одной вершины, поэтому равенство сохраняется и для графов с петлями. Это свойство называют леммой о рукопожатиях.
Из равенства следует, что сумма степеней всегда чётная, поскольку 2m делится на 2. Чётные степени в сумме дают чётное число, поэтому сумма нечётных степеней также должна быть чётной. Нечётное количество нечётных чисел даёт нечётную сумму, а чётное количество — чётную. Значит, вершин нечётной степени может быть ноль, две, четыре и так далее, но не нечётное число.
Эти свойства работают как быстрые проверки. Если в списке рёбер забыли связь или ошиблись при подсчёте степени, сумма степеней может не совпасть с удвоенным числом рёбер. Для последовательности степеней проверяют чётность суммы и, в простом графе с n вершинами, условие d ≤ n − 1. Нарушение хотя бы одного условия доказывает, что такого графа быть не может, хотя выполнение условий само по себе ещё не всегда доказывает существование графа.
| Понятие или свойство | Определение или формула | Как определить на графе | Пример или следствие |
|---|---|---|---|
| Вершина графа | Объект, изображаемый точкой | Найти точку или элемент списка вершин | Вершина A может обозначать город |
| Ребро графа | Связь двух вершин | Найти линию или пару в списке рёбер | AB соединяет A и B |
| Смежные вершины | Вершины с общим ребром | Проверить, есть ли ребро между ними | При ребре AB вершины A и B смежны |
| Степень вершины | Число инцидентных рёбер; петля считается дважды | Посчитать все рёбра, касающиеся вершины | Если к A подходят три ребра, d(A) = 3 |
| Сумма степеней вершин | ∑d(v) = 2m | Сложить степени или удвоить число рёбер | При 4 рёбрах сумма степеней равна 8 |
| Число вершин нечётной степени | Всегда чётно | Посчитать вершины с нечётными степенями | Таких вершин может быть 0, 2 или 4 |
Таблица помогает перейти от определения к проверке конкретного графа: сначала найдите вершины и рёбра, затем определите смежность и степени. Для контроля сложите степени и сравните результат с удвоенным числом рёбер. При проверке списка степеней также посчитайте, сколько значений нечётны, и учтите ограничения простого графа.
Задача 1. Дан граф с вершинами A, B, C, D и рёбрами AB, AC, BC, CD. Найдите степень каждой вершины и назовите пары смежных вершин.
Ответ: d(A) = 2, d(B) = 2, d(C) = 3, d(D) = 1; смежные пары: A–B, A–C, B–C, C–D. Проверка: сумма степеней 8, а рёбер 4, так что 2m = 8.
Задача 2. В графе 8 рёбер. Известны степени семи вершин: 1, 2, 2, 3, 3, 4, 5. Найдите степень восьмой вершины и проверьте возможность такого графа.
Ответ: такого графа не существует. Условие о сумме даёт невозможную отрицательную степень, а проверка чётности также исключает граф.
Задача 3. Можно ли построить простой граф с шестью вершинами, степени которых равны 1, 1, 2, 2, 3, 5?
Ответ: да, такой простой граф существует. Две вершины, которым после связи с вершиной степени 5 остаётся степень 0, больше ни с кем не соединяются; три другие образуют путь из трёх вершин.
Считать степень по числу соседей. В простом графе это срабатывает, но при кратных рёбрах две вершины могут быть соединены несколькими связями, и каждую нужно учесть. Петля тоже не создаёт нового соседа, однако даёт два вклада в степень. Проверяйте, считаете ли вы именно рёбра, а не только разные вершины рядом.
Считать каждое ребро один раз в сумме степеней. Так считают общее число рёбер, но при сложении степеней ребро учитывается у обоих концов. Ошибка возникает, если забыть, что одно ребро связано сразу с двумя вершинами. Проверьте итог равенством ∑d(v) = 2m.
Решить, что нечётное число вершин нечётной степени невозможно. Невозможно именно нечётное количество таких вершин, независимо от общего числа вершин графа. Например, три вершины нечётной степени недопустимы, а две — допустимы. Пересчитайте нечётные степени в списке, а не общее число вершин.
Путать смежность и инцидентность. Смежными называют вершины, имеющие общее ребро, а инцидентным — ребро, относящееся к своей концевой вершине. Эти слова часто смешивают, потому что оба описывают связь. Для самопроверки сформулируйте отношение точно: AB смежны A и B; ребро AB инцидентно вершинам A и B.
Для работы с графами нужны понятия множества, пары объектов и способы вести подсчёт; таблица помогает не терять связи и степени. Графы применяют, когда описывают сети, маршруты, транспортные схемы и социальные связи: вершины задают объекты, рёбра — отношения между ними. Свойства степеней становятся основой для следующих тем — путей, циклов, связности и алгоритмов на графах. Например, перед поиском маршрута полезно понимать, какие вершины соединены и сколько связей к ним подходит.
Почему сумма степеней вершин получается в два раза больше числа рёбер?
Каждое ребро имеет два конца и учитывается в степенях обеих своих концевых вершин. Поэтому при сложении степеней каждое ребро даёт вклад 2, а сумма равна 2m, где m — число рёбер. Петля тоже даёт два вклада в степень своей вершины.
Как считать степень вершины, если у неё есть петля?
Петля соединяет вершину саму с собой и учитывается в её степени дважды. Это соответствует общему правилу: у петли два конца, хотя оба находятся в одной вершине. Поэтому при подсчёте степени прибавьте за петлю 2.
Могут ли две вершины быть соединены несколькими рёбрами?
Да, если рассматривается граф, в котором допускаются кратные рёбра. Тогда каждое из них учитывается отдельно и увеличивает степень обеих вершин на 1. В простом графе кратных рёбер и петель нет.
Почему число вершин нечётной степени не может быть нечётным?
Сумма степеней всех вершин равна удвоенному числу рёбер, поэтому она чётная. Сумма чётных степеней чётна, а сумма нечётных чисел чётна только тогда, когда слагаемых нечётной величины чётное число. Значит, вершин нечётной степени всегда чётное количество.
Как по списку степеней понять, может ли существовать такой граф?
Сначала проверьте, что степени — целые неотрицательные числа и что их сумма чётна. В простом графе с n вершинами степень каждой вершины не больше n − 1. Эти условия необходимы, но не всегда достаточны: иногда нужно дополнительно проверить, можно ли соединить вершины так, чтобы получить указанные степени.
§ 51. Простейшие свойства графов
