Графы и степени вершин.
Пусть в простом непустом графе более k вершин, и степень каждой вершины кратна k. Доказать, что найдутся k+1 неизолированных вершин, имеющих одинаковую степень.
задан 22 Ноя ’15 7:55
1 ответ
Начну с критики формулировки условия. Пустым следует называть граф, в котором нет ни вершин, ни рёбер (такой объект часто вообще не рассматривают, но в принципе можно рассмотреть). Получается, что если в графе более k вершин, то он уже непустой, и эта информация является лишней. Более того, она лишняя даже в случае, если под «непустотой» понималось наличие хотя бы одного ребра.
Число k здесь подразумевается натуральным, что можно отдельно не оговаривать. Тогда, если степень каждой вершины кратна k, то она уже не меньше k. Граф простой, кратных рёбер нет. Одна вершина соединена с k различными, то есть всего, считая её, вершин больше k. Спрашивается, зачем в условии даётся лишняя информация на этот счёт?
С учётом предыдущей оговорки, изолированные вершины из графа можно удалить. Тогда получится следующая формулировка. Пусть k — натуральное число. Рассмотрим простой конечный граф без изолированных вершин, в котором степень каждой вершины кратна k. Доказать, что найдутся k+1 вершин, имеющих одинаковую степень. В таком виде и будем решать.
Пусть вершин у графа имеется $%n$%. Положим $%n-1=kq+r$%, где $%q$% целое, $%0\le r < k$% — остаток от деления $%n-1$% на $%k$%. Ввиду того, что степени вершин простого графа не превосходят $%n-1$%, а изолированных вершин у нас нет, значения степеней вершин могут быть только такие: $%k$%, $%2k$%, . , $%qk$%. Всего $%q$% возможностей. Это верно для каждой из вершин. Поскольку общее их число равно $%n > kq$%, то можно применить принцип Дирихле, и из него сразу следует, что найдётся более $%k$% вершин (а потому не менее $%k+1$%), у которых степени одинаковы.
§ 3.1. Основные определения
Граф, его вершины и ребра. Смежные вершины. Кратные ребра, петли. Инцидентные вершины и ребра. Степени вершин. Висячие и изолированные вершины. Лемма о рукопожатиях. Диаграмма графа. Изоморфные графы. Специальные виды графов: обыкновенные, полные, двудольные, полные двудольные графы. Матрица смежности и матрица инцидентности. Подграф. Операции над графами: объединение, пересечение, декартово произведение.
Базовые понятия и утверждения
1. Общие понятия. Различают два вида графов — неориентированные и ориентированные. Знакомство с теорией графов мы начнем с изучения графов первого вида.
Определение. Пусть 
— конечное непустое множество, 
— конечное множество, состоящее из поименованных неупорядоченных пар элементов множества 
, причем это могут быть пары из одинаковых элементов и одинаковые пары с разными именами. Совокупность множеств 
и 
называют графом (или неориентированным графом) и обозначают 
.
Элементы множества 
называют вершинами, а элементы множества 
— ребрами.
Граф может вовсе не иметь ребер. Такой граф называют нулевым.
Множества вершин 
и ребер 
графа 
также обозначают 
и 
соответственно. Если ребро 
— это пара вершин 
и 
, то пишут 
.
Обычно графы представляют диаграммами. Каждой вершине графа 
ставят в соответствие свою точку плоскости или пространства, которую помечают тем же символом, что и вершину 
, а каждому ребру 
ставят в соответствие непрерывную кривую, соединяющую точки 
, 
и не проходящую через точки, изображающие другие вершины графа.
Если 
, то говорят, что ребро 
соединяет вершины 
и 
, и вершины 
и 
называют концами ребра 
. Если две вершины соединены ребром, их называют смежными вершинами. Если ребра имеют общую концевую вершину, то их называют смежными ребрами. Если 
— конец ребра 
, то ребро 
и вершину 
называют инцидентными. Если 
и 
, то ребра 
и 
называют кратными. Ребро вида 
называют петлей.
Граф без петель и кратных ребер называется обыкновенным.
Число ребер, инцидентных вершине 
(петля учитывается дважды), называют степенью вершины и обозначают 
. Если 
, то вершину 
называют изолированной, а если 
, то — висячей. Ребро, инцидентное висячей вершине, также называют висячим.
Вершины 
и 
, 
и 
, 
и 
, 
и 
— смежные. Ребра 
, 
— кратные, ребро 
— петля. Вершина 
— инцидентна ребру 
, 
— ребрам 
, 
, 
и 
, 
— ребрам 
, 
и 
, 
— ребрам 
, 
и 
. Вершины графа имеют степени: 
, 
, 
, 
, 
. Вершина 
— висячая, вершина 
— изолированная. Ребро 
— висячее.
Лемма (о рукопожатиях). Для любого графа 
сумма степеней вершин равна удвоенному числу ребер:
.
Доказательство. При подсчете суммы степеней вершин произвольное ребро 
внесет вклад, равный 1, как в степень вершины 
, так и в степень вершины 
, т.е. будет учтено в сумме дважды. ■
Пример 2. Выяснить, существует ли граф со следующим набором степеней вершин:
а) 1, 2, 2, 2, 3, 4, 5; б) 1, 1, 1, 2, 3, 3, 3.
◄ а) Предположим, что такой граф 
существует. Тогда, согласно утверждению леммы о рукопожатиях, сумма степеней его вершин равна удвоенному числу ребер, т.е. 
, откуда 
. Но это невозможно, так как число ребер не может быть дробным. Полученное противоречие показывает, что предположение о существовании графа с указанным набором степеней вершин было неверным.
б) Если граф с набором степеней вершин 1, 1, 1, 2, 3, 3, 3 существует, то он, согласно лемме о рукопожатиях, имеет 7 ребер (
, откуда 
). Действуя методом проб, несложно подобрать примеры таких графов (диаграммы двух из них изображены на рис. 3.3 и 3.4). ►
Существует ли граф на 9 вершинах, степени которых равны 1, 1, 1, 1, 1, 2, 4, 5, 6?
конкретно здесь можно измыслить так:
вершины 4, 5, 6, даже если соединены друг с другом попарно (на что уйдет 6 степеней), всё равно имеют 9 свободных степеней, которые не накрываются остальными вершинами.
но это при условии, что нет кратных ребер (когда ребра А и Б соединены более чем одной вершиной), и петель (ребер А-А). У тебя ведь именно такой кейс?
Вектор степеней графа это
3.02.1. Основные числовые характеристики и матрицы графа. Степени вершин графа
Степенью вершины V графа G называется число инцидентных ей рёбер, т. е. число рёбер, выходящих из данной вершины. (В случае псевдографов каждая петля добавляет 2 в степень вершины). Обозначается степень вершины V графа G: degGv или просто deg V, если ясно, о каком графе G идет речь.
Вершина степени 0 называется Изолированной. Вершина степени 1 называется Концевой (или Висячей). Ребро, инцидентное концевой вершине также
Называется Концевым.
Вершина V Графа G, смежная со всеми другими вершинами G, называется Доминирующей. Её степень degGv очевидно равна |G| —1.
Граф G называется Регулярным (или, по-другому, Однородным), если степени всех его вершин равны. Эта общая степень всех вершин регулярного графа G называется степенью регулярного графа G и обозначается deg G.
Последовательность степеней вершин графа G, записанная в каком либо порядке называется степенной последовательностью графа G. Например, граф на рисунке справа имеет степенную последовательность (3, 3, 1, 0, 1, 2).
Понятно, что изоморфные графы имеют одинаковые (с точностью до порядка следования элементов) степенные последовательности. Однако, из этого совпадения степенных последовательностей двух графов ещё не следует их изоморфность. На следующих двух рисунках изображены два неизоморфных регулярных графа степени 2.
Таким образом, степенная последовательность не определяет граф полностью и не может
служить способом его задания.
Степенная последовательность не может быть произвольным набором чисел, а обладает определёнными свойствами.
Лемма 1 («о рукопожатиях»). Сумма степеней всех вершин графа G есть число чётное, ровно в два раза большее числа рёбер графа G, т. е.
 |
Доказательство: Действительно, подсчитаем количество рёбер графа G, просматривая поочередно все вершины графа G и считая рёбра выходящие из этих вершин. Так как из каждой вершины V выходит degGV рёбер, то мы получим сумму:
Но при этом каждое ребро будет учтено 2 раза: один раз, когда рассматривался один его конец, другой раз, когда — второй. Таким образом, лемма верна.
Из леммы 1 вытекает
Следствие. В любом графе число вершин нечётной степени является чётным.
Доказательство. В самом деле, иначе, если бы сумма целых чисел содержала нечётное число нечетных слагаемых, то она, очевидно, была бы нечётной, что противоречит лемме о рукопожатиях.
В ориентированных графах для каждой вершины V дополнительно рассматривается также полустепень исхода и полустепень захода. Полустепенью исхода вершины V называется число дуг графа G, для которых V Является началом, а Полустепенью захода – число дуг, для которых V является концом. Обозначаются полустепени захода и исхода графа G соответственно deg-V и deg+V. При этом полная степень degV = deg-V+ deg+V. Поскольку каждая дуга имеет ровно одно начало и один конец, то справедлива
Вектор степеней второго порядка
Вектор, компонентами, которого являются окружения всех вершин графа, называют вектором степеней второго порядка.
У графа Г на рисунке вектор степеней второго порядка равен ((3), (2, 3), (2, 3), (2, 2), (2, 2), (2, 2, 1)).
Чтобы различать эти два вектора, простой вектор степеней иногда называют вектором степеней первого порядка.
Из сохранения отношения смежности при изоморфизме следует, что векторы степеней изоморфных графов совпадают.
Рис. 82. Неизоморфные графы Г1 и Г2 имеют одинаковые векторы степеней
Иначе говоря, для изоморфизма графов необходимо равенство векторов степеней.
Обратное утверждение неверно.
Равенства векторов степеней недостаточно для изоморфизма графов.
Конечно, в некоторых случаях, изоморфизм графов все-таки следует из равенства векторов степеней. Например, два графа с одинаковым числом вершин изоморфны, если оба пусты, или оба полные, или каждый содержит в точности по одному ребру.
Графический вектор может задавать неизоморфные графы.
Например, вектор (2, 2, 2, 2, 2, 2) — графический, он является вектором степеней графа, причем даже не одного, а двух — неизоморфных графов.
Мало того, что графы Гі и Гг неизоморфны. Первый граф распадается на два, несоединенных между собой «куска». Такой граф называется несвязным, а два «куска» графа — это две компоненты связности.
Пример графов Гі и Гг показывает, что по вектору степеней, вообще говоря, нельзя даже определить, связный граф или не связный. Если граф не связный, то с помощью этого вектора не удастся вычислить точное число компонент связности графа.
Не спасает положения и вектор степеней второй ступени: и эти векторы у графов Г і и Гг одинаковые.
Однако в следующем примере (графы Гз и Гд) вектор степеней второго порядка поможет справиться с ситуацией.
Рис. 83. Векторы степеней у Гз и Гд совпадают
Вектор степеней графа Гз равен вектору степеней графа Гд и равен (2, 2, 2, 3, 3).
Вектор степеней второго порядка графа Г з равен ((3, 3), (3, 2), (3, 2), (3, 2, 1), (3, 2, 2, 1)).
Вектор степеней второго порядка для графа Гд другой: ((3, 3), (3, 3), (3, 3), (2, 2, 2), (2, 2, 2)).
Эти векторы различны, и, следовательно, графы Гз и Гдне изоморфны.
То, что эти графы не изоморфны, видно, впрочем, и из других соображений. Например, в графе Гз есть только один цикл, состоящий из трех ребер, а в графе Гд таких циклов два.
Рис. 84. Помеченные графы R и Ге— равные
Построение графов на основе их характеристик
Отметим, что в задачах на построение решение необходимо искать среди простых неориентированных графов (т.е. графов без кратных ребер и без петель). К сожалению, не существует универсальной методики, позволяющей точно определить, может ли быть построен граф с заданными характеристиками.
Важно помнить, что в любом графе сумма степеней всех его вершин — число четное, равное удвоенному числу ребер графа, так как каждое ребро участвует в этой сумме ровно два раза. Этот результат, известный еще 200 лет назад Эйлеру, часто называют леммой о рукопожатиях. Из нее следует, что если несколько человек обменялись рукопожатиями, то общее число пожатых рук обязательно четно, ибо в каждом рукопожатии участвуют две руки (при этом каждая рука считается столько раз, сколько она участвовала в рукопожатиях). Отсюда следует, что:
- • число вершин с нечетной степенью у любого графа четно;
- • во всяком графе с п вершинами, где п > 2, всегда найдутся по меньшей мере две вершины с одинаковыми степенями;
- • если в графе с вершинами п > 2 в точности две вершины имеют одинаковую степень, то в этом графе всегда найдется либо в точности одна вершина степени 0, либо в точности одна вершина степени (п — 1).
При решении задач необходимо очень внимательно читать условие, так как многие прилагательные, описывающие свойства графа, имеют численные эквиваленты. Приведем таблицу таких соответствий, чаще всего встречающихся в формулировке задач (табл. 2.9).
После того как получены все необходимые числительные, нужно попробовать рассчитать недостающие характеристики графа. Иногда в условии приводятся степени всех или нескольких вершин. В этом случае на основе того факта, что каждое ребро графа добавляет к его суммарной степени вершин ровно два, можно воспользоваться формулой
где т — количество вершин, а суммирование ведется по всем вершинам от 1 до п.
Задача 2.42. Построить граф на восьми вершинах, имеющий следующее распределение степеней вершин: две вершины степени 4; три вершины степени 3; две вершины степени 2; одна вершина степени 1.
Суммарная степень всех вершин равна 2-4 + 3- 3 + 2- 2+1 • 1=22, отсюда следует, что всего 11 ребер. Строить графы на основании вектора степеней проще, начиная с вершин больших степеней. Вер-