Доказательство леммы о рукопожатиях

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

Лемма является следствием формулы суммы степеней, также иногда называемой леммой о рукопожатиях.

для графа с множеством вершин V и множеством рёбер E. Оба результата доказаны Эйлером в его знаменитом докладе о семи мостах Кёнигсберга (1736). Эта работа положила начало исследованиям в области теории графов.

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

Содержание

Доказательство [ править | править код ]

При доказательстве упомянутой формулы Эйлер использовал технику двойного (повторного) счёта. Он посчитал количество инцидентных пар (v,e), где e — ребро и v — одна из его концевых вершин двумя разными способами. При добавлении ребра сумма степеней вершин графа увеличивается на 2, т.е. вершина v принадлежит deg(v) парам, где deg(v) — степень вершины (количество инцидентных ей рёбер). Следовательно, число инцидентных пар совпадает с суммой всех степеней. Однако каждое ребро принадлежит двум инцидентным парам, так как имеет две концевые вершины. Поэтому число инцидентных пар равно 2 | E | < extstyle 2|E|> . Поскольку две данные формулы предназначены для одного и то же множества, их значения одинаковы.

Чётность или нечётность суммы целых чисел не зависит от количества чётных слагаемых. Сумма чётна, если число нечётных слагаемых чётно (и нечётна в противном случае). Так как одна часть уравнения всегда чётна ( 2 | E | ) < extstyle (2|E|)> , другая часть должна содержать чётное число нечётных слагаемых, т. е. вершин нечётной степени.

Регулярные графы [ править | править код ]

Формулы суммы степеней подразумевает, что k-регулярный граф с числом вершин n имеет kn/2 рёбер. [1] В частности, если k нечётно, число рёбер должно делиться на k.

Бесконечные графы [ править | править код ]

Лемма не применима к бесконечным графам, даже если они имеют конечное число нечётных вершин. Например, бесконечный путь с одной концевой вершиной имеет единственную нечётную вершину (то есть, нечётное количество).

Приложения [ править | править код ]

Лемма о рукопожатиях также использована в одном из доказательств леммы Шпернера, а также задачи «о восхождении на гору».

Степенью (или валентностью) вершины v называется число инцидентных ей ребер. Степень вершины обозначается deg(v). Очевидно, что для любой вершины v V справедливо: 0  deg(v)  |V| –1; deg(v) = |Г(v)|.

Вершина графа, имеющая степень 0, называется изолированной, а вершина со степенью 1 – висячей, или концевой.

Если степени всех вершин графа одинаковы и равны некоторому числу k, то такой граф называется регулярным графом степени k. Степень регулярности является инвариантом графа и обозначается r(G). Для нерегулярных графов r(G) не определено.

На рисунке показаны регулярные графы соответственно степени 2 и 3.

Для орграфа число дуг, исходящих из вершины v, называется полустепенью исхода, а число входящих – полустепенью захода. Эти числа соответственно обозначаются deg – (v) и deg + (v): deg(v)=deg – (v) + deg + (v).

Теорема Эйлера (Лемма "о рукопожатиях"). Сумма степеней всех вершин графа является четным числом и равна удвоенному числу его ребер, т.е. . Для орграфа:.

Действительно, при подсчете данной суммы каждое ребро считается дважды: при определении степени одного конца и при определении степени другого конца.

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

Найдем степенную последовательность для графа G. Выпишем степени всех вершин графа в соответствии с их номерами (2,2,3,2,1).

28) Маршруты, цепи, циклы. Расстояние между вершинами, диаметр графа.

Маршрутом от вершины u к вершине v или (u,v)-маршрутом в графе G называется всякая последовательность вида , в которой любые два соседних элемента инцидентны, т.е.e_k – ребро, соединяющее вершины v_k–1 и v_k, k = 1,2,…,n.

Это определение подходит также для псевдо-, мульти- и орграфов. В случае орграфа v_k–1 – начало ребра е_k , a v_k – его конец.

При этом вершину u называют началом маршрута, а вершину v – его концом. В маршруте некоторые вершины и ребра могут совпадать. Если u = v, то маршрут замкнут, а иначе открыт.

Для «обычного» графа маршрут можно задавать только последовательностью вершин или ребер.

Маршрут называется цепью, если в нем нет совпадающих ребер, и простой цепью – если дополнительно нет совпадающих вершин, кроме, может быть, начала и конца цепи. Про цепь u==v говорят, что она соединяет вершины u и v и обозначают u,v.

Очевидно, что если есть цепь, соединяющая вершины u и v, то есть и простая цепь, соединяющая эти вершины.

Замкнутая цепь называется циклом; замкнутая простая цепь – простым циклом. Число циклов в графе G обозначается z(G). Граф без циклов называется ациклическим.

Для орграфов цепь называется путем, а цикл – контуром.

(1,2,3,4,5,3,2) – маршрут, не являющийся цепью; (1,2,3,4,5,3) – цепь, не являющаяся простой; (1,2,3,4) – простая цепь; (1,2,3,4,5,3,1) – цикл, не являющийся простым; (1,2,3,1) – простой цикл.

Число ребер в маршруте M (возможно, с повторениями) называется его длиной, обозначается |M|.

Расстоянием между вершинами u и v (обозначается d(u,v)) называется длина кратчайшей цепи u,v, а сама кратчайшая цепь называется геодезической.

Если не существует цепи, соединяющей вершины u и v, то по определению d(u,v) = +.

Диаметром графа G (обозначается D(G)) называется длина длиннейшей геодезической.

Максимальным удалением в графе G от вершины v называется r(v) = max d(v,v’),  v’V. Вершина v графа G является его центром, если максимальное удаление от нее до всех вершин принимает наименьшее значение.

Граф, любая из вершин которого является его центром – максимальное удаление до всех вершин от любой =1.

Класс: 9

Презентация к уроку

Внимание! Предварительный просмотр слайдов используется исключительно в ознакомительных целях и может не давать представления о всех возможностях презентации. Если вас заинтересовала данная работа, пожалуйста, загрузите полную версию.

Цели урока:

• образовательные: передать систему математических знаний по теме «элементарные факты теории графов», выработать умения решать основные типы математических задач, связанные с графами, формировать умения анализировать, выдвигать гипотезы и предположения, строить доказательства, переносить знания в новые ситуации;
• развивающие: создать условия для развития следующих компетенций:
• уверенность в себе;
• самостоятельность мышления, оригинальность;
• критическое мышление;
• готовность работать над чем-либо спорным и вызывающим беспокойство;
• способность принимать решения;
• персональная ответственность;
• способность слушать других людей и принимать во внимание то, что они говорят;

• воспитательные: воспитывать стремление к приобретению новых знаний, интерес к предмету.

Дидактическое обеспечение:

• Презентация Power Point, карточки для рефлексии.

Время занятия: 1 урок (45 минут).

Ход урока.

I. Организационный момент (приветствие, постановка цели урока, заполнение журнала в части указания отсутствующих на уроке).

Слайд 1.

II. Историческая справка. Мотивация.

Итак, как вы все знаете, 1ая работа по теории графов принадлежит Леонарду Эйлеру. Ещё в 1736 году в одном из своих писем итальянскому математику и инженеру Мариони он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов. Но при решении этой задачи сам Эйлер не использует термин «граф». Только через 200 лет, в 1936 году, этот термин был предложен венгерским математиком Денешом Кёнигом в его работе «Теории конечных и бесконечных графов». В начале 20 века наряду с термином «граф» употреблялись и другие: карта, комплекс, диаграмма, сеть, лабиринт и т.п. В настоящее время, термин «граф» считается устоявшимся, хотя в прикладной математике, наряду с ним употребляется и термин «сеть» (сети Петри, нейронные сети и т.д.).

Слайд 2.

Я предлагаю рассматривать тему сегодняшнего занятия через призму задач.

III. Актуализация знаний и их практическое применение.

Давайте рассмотрим достаточно известную задачу о космическом сообщении (была использована в программе летней школы Дилемма – 2010 для 3 группы 6 класса, г.Казань, приведена в [3], [4]): между 9 планетами Солнечной системы введено космическое сообщение. Ракеты летают по следующим маршрутам: Земля – Меркурий, Плутон – Венера, Земля – Плутон, Плутон – Меркурий, Меркурий – Венера, Уран – Нептун, Нептун – Сатурн, Сатурн – Юпитер, Юпитер – Марс и Марс – Уран. Можно ли добраться с Земли до Марса?.

Слайд 3.

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

Следующая задача о конях известна в различных вариациях и была использована в программе летней школы Дилемма – 2010 для учащихся 1, 2 групп 6 класса, г.Казань, а также приведена в [1], [3], [4] книгах. Сформулируем ее следующим образом: В углах доски 3´3 стоят четыре коня: сверху белые, снизу черные. Можно ли их переставить за несколько ходов так, чтобы одноцветные кони стояли в противоположных углах доски?

Слайд 4.

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

Следующая задача о расстановке чисел приведена в [3], [4]: можно ли выписать в ряд цифры от 0 до 9 так, чтобы сумма любых двух рядом стоящих цифр делилась либо на 5, либо на 7, либо на 13?

Слайд 5.

Данная задача – яркий представитель еще одного класса задач, в которых можно использовать графы: задачи на расстановки чисел или каких-то других элементов в определенном порядке.

Решение. За вершины графа примем цифры 0, 1, 2, …, 9. Если сумма двух рядом стоящих цифр делится либо на 5, либо на 7, либо на 13, то соединим соответствующие вершины ребром. Получим граф.

Перебором находим одно из возможных решений: 0 – 7 – 3 – 4 – 6 – 1 – 9 – 5 – 8 – 2.

Обратить внимание учащихся, что приведённый ответ не является единственным.

Задачи о дорогах между 100 городами и о количестве песен взяты из [1], [3], [4] и решаются они по одному и тому же принципу.

Слайд 6.

Задача о дорогах между 100 городами. В государстве 100 городов, и из каждого из них выходит 4 дороги. Сколько всего дорог в государстве?

Задача о количестве песен на концерте. На концерте каждую песню исполняли двое артистов, и никакая пара не выступала вместе более одного раза. Всего было 12 артистов, каждый выступил по 5 раз. Сколько песен было спето?

Считать ребра графа легче, чем дороги или песни: ребра можно нарисовать, разрезать на части (т.е. рассмотреть их концы) и т.п. Именно свойство наглядности и обуславливает широкое распространение графов.

В обеих задачах этого слайда возникает понятие степени (или порядка) вершины, т.е. количества ребер, исходящих из этой вершины. В соответствии с этим понятием вершины делят на четные и нечетные.

Следующая задача о дорогах между 15 городами [1], [5], [6] с неявным использованием понятия «степень вершины» сформулирована следующим образом: В стране 15 городов, каждый из которых соединён дорогами не менее чем с семью другими. Докажите, что из любого города можно добраться в любой город (возможно, проезжая через другие города).

Слайд 7.

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

Следующая задача «на 10 девчонок по статистике 9 рябят»: на дискотеке каждый мальчик танцевал ровно с десятью девочками, а каждая девочка – ровно с девятью мальчиками. Кого больше: мальчиков или девочек?

Слайд 8.

Если эту задачу из [4] книги переформулировать в равносильную, но с другим сюжетом, то решение становится очевидным: к празднику было куплено несколько тортов, и каждый был разрезан на 9 кусков. Каждому пришедшему досталось по 10 кусков. Чего было меньше: тортов или пришедших? Здесь сразу ясно, что каждому досталось по 10/9 торта, то тортов было больше.

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

Задача: Аркадий, Борис, Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько рукопожатий было сделано?

Слайд 9.

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

В построенном графе ровно 10 ребер, которые и соответствуют 10 рукопожатиям.

На самом деле задачу о рукопожатиях из [2] проще решить исходя из логических соображений: всего 5 человек и каждый пожал руку 4ым, но ведь если один пожал руку другому, то и другой пожал руку первому, т.е. число рукопожатий равно 5·4:2 = 10.

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

Из рассмотренной задачи о рукопожатиях естественным образом возникает обобщение на полный граф из n вершин. Число ребер в нем выражается приведенной формулой.

Слайд 10.

Кроме того, рассмотрим и некоторые очевидные закономерности для графов [2], [4].

• Количество ребер в полном графе с n вершинами определяется как число неупорядоченных пар, составленных из n точек без повторений, т.е. число сочетаний без повторений из n элементов по 2: .
• Степени вершин полного графа одинаковы, и каждая на 1 меньше числа вершин этого графа.
• Сумма степеней вершин графа число четное, равное удвоенному числу ребер графа (закономерность справедлива для любого графа, не только полного, и носит название леммы о рукопожатиях).
• Число нечетных вершин любого графа четно (следствие из леммы о рукопожатиях).

А теперь будем решать задачи с использованием приведенных закономерностей.

Слайды 11 – 24.

Рассмотрим задачу о вассалах короля из [1], [6]: у короля 19 баронов-вассалов. Может ли оказаться так, что у каждого вассального баронства 1, 5 или 9 соседних баронств?

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

Задача: докажите, что не существует многогранника, у которого было бы ровно семь ребер.

Доказательство. Если у многогранника 4 вершины, то это тетраэдр, имеющий 6 ребер (каждая из 4·3:2=6 пар вершин соединена не более, чем одним ребром).

Пусть число вершин многогранника n ³ 5. В каждой вершине многогранника сходится по крайней мере три грани, т.е. из каждой вершины многогранника выходит не меньше, чем 3 ребра.

Значит всего ребер не меньше, чем , что и требовалось доказать.

При решении задачи о 9 отрезках на плоскости из [2], [6], как и в задаче о вассалах короля используется следствие леммы о рукопожатиях.

Задача: Можно ли нарисовать на плоскости 9 отрезков так, чтобы каждый пересекался ровно с тремя другими?

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

Ответ: нет, не возможно.

Задача о мышах: в норке живёт семья из 24 мышей. Каждую ночь ровно четыре из них отправляются на склад за сыром. Может ли так получиться, что в некоторый момент времени каждая мышка побывала на складе с каждой ровно по одному разу?

При решении задачи о мышах из [6] используются не только логические рассуждения, но и признак делимости на 3.

Задача об абонентах в системе связи с некоторыми модификациями приведена в [2], [6]: В системе связи, состоящей из 2013 абонентов, каждый абонент связан ровно с n другими. Определите все возможные значения n.

Для решения этой задачи используется понятие степени вершины и лемма о рукопожатиях.

Задача: Петя заметил, что у всех его 25 одноклассников различное число друзей в этом классе. Сколько друзей у Пети? (Укажите все возможные решения)

В задаче о друзьях Пети из [6] используется в неявном виде понятие степени вершины. В ходе решения этой задачи обнаруживается факт о возможности двух различных случаев, приводящих к разным ответам. Так как ситуации равновозможные, то в ответ записывает оба случая.

Задача: на плоскости нарисовано несколько точек, некоторые пары точек соединены отрезками. Известно, что из каждой точки выходит не более k отрезков. Докажите, что точки можно покрасить в k + 1 цвет таким образом, чтобы любые две точки, соединенные отрезком, были покрашены в разные цвета.

В задаче о покраске точек [1], [6] используем индукцию.

И последняя задача на сегодня из [1], [6] имеет уровень сложности 6 из 7. Для ее решения необходимо будет использовать понятие степени вершины и лемму о рукопожатиях.

Задача: Гидры состоят из голов и шей (любая шея соединяет ровно две головы). Одним ударом меча можно снести все шеи, выходящие из какой-то головы A гидры. Но при этом из головы A мгновенно вырастает по одной шее во все головы, с которыми A не была соединена. Геракл побеждает гидру, если ему удастся разрубить ее на две несвязанные шеями части. Найдите наименьшее N, при котором Геракл сможет победить любую стошеюю гидру, нанеся не более, чем N ударов.

Решение. Перейдем к графу, в котором головы – вершины, шеи – ребра, а удар по шеям, выходящим из головы A назовем инвертированием вершины A.

Тогда, если есть вершина X степени не больше 10, то достаточно инвертировать ее соседей, и она отделится, т.е. эта вершина не будет соединена с остальными вершинами графа. Если есть вершина, соединенная со всеми вершинами, за исключением n (n £ 9 ), то нужно инвертировать сначала эту вершину, а затем те n вершин, с которыми она вначале не была соединена, и тогда эта вершина отделится. Если же для каждой вершины есть хотя бы 11 вершин, соединенных с ней, и хотя бы 10, не соединенных с ней, то всего вершин не меньше 22, и ребер не меньше, чем 22·11:2 = 121 > 100.

Приведем пример гидры, которую нельзя разрубить за 9 ударов: две группы по 10 голов и 100 шей, соединяющих все пары голов из разных групп. Заметим, что состояние ребра между вершинами A и B не изменилось (т.е. оно осталось, если было вначале, и не появилось, – иначе) Û вершины A и B отрубали в сумме четное число раз. Поэтому порядок отрубания вершин неважен, и бессмысленно отрубать вершину два раза.

Пусть по этой гидре нанесено не более 9 ударов. Тогда в каждой группе осталось по не отрубленной голове, и поэтому есть шея из одной группы в другую; более того, все не отрубленные головы образуют связное множество.

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

Ответ: 10 ударов.

Если найдется учащийся, сумевший решить эту задачу самостоятельно или с незначительными подсказками, то стоит оценить его положительно сразу же.

V. Домашнее задание.

К следующему уроку придумайте и решите по 3 задачи каждый на сегодняшнюю тему.

VI. Подведение итогов. Рефлексия.

Я рада, что вы все работали хорошо. А теперь вспомните основные моменты нашего урока.

Чему вы научились во время занятия? Учащиеся отвечают.

Сегодня за работу у доски получают оценки…, а также хочу отметить и поощрить за активную работу устно:…

Ребята, обратите внимание, у вас у каждого есть картинки с жестами. Оставьте перед уходом мне на столе тот, что соответствует вашим ощущениям от урока. Если не стесняетесь, то подпишите свою карточку.

Рисунок 5

Рисунок 6