Теорема Эйлера о плоском графе С л а й д – л е к ц и я. - презентация

1 Теорема Эйлера о плоском графе С л а й д – л е к ц и я

2 Оглавление Введение Слайд 33 Часть I. Необходимые сведения по теории графов Слайд Задача, приводящая к графам Слайд Полный граф. Дополнение графа Слайд Степень вершины Слайд Путь в графе. Цикл Слайд Связность графа Слайд Операция удаления ребра. Мост Слайд Деревья. Лес Слайд Представление о плоском графе Слайд Триангулированный граф Слайд Теорема Эйлера Слайд Следствия из теоремы Эйлера [3,163] Слайд Приложение формулы Эйлера к географии [2,258] Слайд Теорема Эйлера и правильные многогранники Слайд 3232 Часть II. Теорема Эйлера о плоском графе и задачи по математике Слайд 3535 Задача 1 Слайд 36 Задача 10 Слайд 44 Задача 18 Слайд Задача 2 Слайд 37 Задача 11 Слайд 45 Задача 19 Слайд Задачи 3, 4 Слайд 39 Задачи 12, 13 Слайд 46 Задача 20 Слайд Задачи 5, 6 Слайд 40 Задача 14 Слайд 47 Задача 21 Слайд Задача 7 Слайд 41 Задача 15 Слайд 48 Задача 22 Слайд Задача 8 Слайд 42 Задача 17 Слайд 49 Задачи 23, 24 Слайд Задача 9 Слайд 43 Доказанные утверждения Слайд Выводы Слайд 5757 Литература Слайд 5858

3 Введение Если вы любите решать задачи на смекалку, логические, олимпиадного типа или головоломки, то, наверное, не раз составляли таблицы, изображали объекты точками, соединяли их отрезками или стрелками, подмечали закономерности у полученных рисунков, выполняли над точками и отрезками операции, не похожие на арифметические, алгебраические или на преобразования в геометрии, то есть вам приходилось строить математический аппарат специально для решения задачи. А это означает, что вы заново открывали для себя начала теории графов. Исторически сложилось так, что теория графов зародилась именно в ходе решения головоломок двести с лишним лет назад. Очень долго она находилась в стороне от главных направлений исследований учёных, была в царстве математики на положении Золушки, чьи дарования раскрылись в полной мере лишь тогда, когда она оказалась в центре всеобщего внимания. Толчок к развитию теория графов получила на рубеже XIX и XX столетий, когда резко возросло число работ в области топологии и комбинаторики, с которыми её связывают самые тесные узы родства. Как отдельная математическая дисциплина теория графов была впервые представлена в работе венгерского математика Кёнига в 30-е годы XX столетия. Ведущее место в теории графов занимает теорема Л. Эйлера. Великий математик Эйлер ещё в XVIII веке доказал формулу, связывающую число вершин В, рёбер Р и граней Г плоского связного графа (выпуклого многогранника) В – Р + Г = 2. Пользуясь теоремой Эйлера, можно быстро и красиво решить многие задачи по математике, в том числе из школьного курса. В последнее время графы и связанные с ними методы исследований органически пронизывают на разных уровнях едва ли не всю современную математику. Графы эффективно используются в теории планирования и управления, теории расписаний, социологии, математической лингвистике, экономике, биологии, медицине. Широкое применение находят графы в таких областях прикладной математики, как программирование, теория конечных автоматов, электроника, в решении вероятностных и комбинаторных задач. Теория графов быстро развивается, находит всё новые приложения и ждёт молодых исследователей. Оглавление

4 Часть I Необходимые сведения по теории графов

5 1.1. Задача, приводящая к графам Задача. В первенстве класса по настольному теннису 6 участников: Андрей, Борис, Виктор, Галина, Дмитрий и Елена. Первенство проводится по круговой системе – каждый из участников играет с каждым из остальных один раз. К настоящему моменту некоторые игры уже проведены: Андрей сыграл с Борисом, Галиной и Еленой; Борис, как уже говорилось, с Андреем и ещё с Галиной; Виктор – с Галиной, Дмитрием и Еленой; Галина – с Андреем и Борисом; Дмитрий – с Виктором и Елена – с Андреем и Виктором. Сколько игр проведено к настоящему моменту и сколько ещё осталось? [4,32] Оглавление А Г ВБ Е Рис.1 Д АГ ВБ Е Рис.2 Д Решение. Изобразим данные задачи в виде схемы (рис.1). Участников будем изображать точками: Андрея – точкой А, Бориса – точкой Б и т.д. Если двое участников уже сыграли между собой, то будем соединять изображающих их точки отрезками. Получается схема, показанная на рисунке 1. Такие схемы называются графами. Точки А, Б, В, Г, Д, Е называются вершинами графа. Заметьте, что точки пересечения рёбер графа часто являются его вершинами. Во избежание путаницы вершины графа часто изображают не точками, а маленькими кружочками. Рёбра зачастую оказывается удобнее изображать не прямолинейными отрезками, а криволинейными – «дугами». Но вернёмся к нашей задаче. Число игр, проведённых к настоящему моменту, равно числу рёбер, т.е. 7. Чтобы найти число игр, которые осталось провести, построим ещё один граф с теми же вершинами, но рёбрами будем соединять тех участников, которые ещё не играли друг с другом (рис.2). Рёбер у этого графа оказалось 8, значит, осталось провести 8 игр: Андрей должен сыграть в теннис с Виктором и Дмитрием: Борис – с Виктором, Дмитрием и Еленой и т.д. Графами мы пользуемся довольно часто. Возьмём схему железных дорог: здесь станции – это вершины графа, перегоны (участки пути между станциями) – рёбра графа. Вершины и рёбра многогранника (куба, пирамиды и т.д.) тоже образуют граф.

6 1.2. Полный граф. Дополнение графа Граф называется полным, если каждые две различные вершины его соединены одним и только одним ребром (рис.3). [1,10] В полном графе каждая его вершина принадлежит одному и тому же числу рёбер. Для задания полного графа достаточно знать число его вершин. Граф, не являющийся полным, можно преобразовать в полный с теми же вершинами, добавив недостающие рёбра. Например, граф Г на рисунке 4 неполный. Проведя недостающие рёбра (для удобства их можно выделить др. цветом или др. типом линии), получаем полный граф с пятью вершинами (рис.5 а). Вершины графа Г и рёбра, которые добавлены, тоже образуют граф. Он приведён на рисунке 5 (б). Такой граф называют дополнением графа Г и обозначают его Г'. Дополнением графа Г называется граф Г' с теми же вершинами, что и граф Г, и с теми и только теми рёбрами, которые необходимо добавить к графу Г, чтобы получился полный граф. Оглавление Рис.5 а) Г': б) Рис.4 Г: Рис.3

7 1.3. Степень вершины Вершины в графе могут отличаться друг от друга тем, скольким рёбрам они принадлежат. Степенью вершины называется число рёбер графа, которым принадлежит эта вершина. Обозначать степени вершин А, В, С будем соответственно так: степ.А, степ.В, степ.С и т. п. У графа на рисунке 6 (а): степ.А = 1; степ.В = 2. У графа на рисунке 6 (б) степени всех вершин равны нулю. Вершина называется нечётной, если её степень – число нечётное. Вершина называется чётной, если её степень – число чётное. Оглавление DС АВ Г а) Рис.6 DС АВ Г б)

8 1.3. Степень вершины Задача. Участники молодёжного слёта, познакомившись, обменялись конвертами с адресами. Докажите, что а) всего было передано чётное число конвертов; б) число участников, обменявшихся конвертами нечётное число раз, чётное. [1,11] Решение. Пусть участники слёта А 1, А 2, А 3,..., А n – вершины графа, а рёбра соединяют на рисунке 7 пары вершин, изображающих ребят, обменявшихся конвертами: а) степень каждой вершины А i показывает число конвертов, которые передал участник А i своим знакомым. Общее число переданных конвертов N равно сумме степеней всех вершин графа. N = степ.А 1 + степ.А степ.А n-1 + степ.А n, но N = 2 р, где р - число рёбер графа, то есть N - чётное. Следовательно, было передано чётное число конвертов; Оглавление А1А1 А2А2 А7А7 А6А6 А5А5 А3А3 А4А4 Рис.7 б) в равенстве N = степ.А 1 + степ.А степ.А n-1 + степ.А n сумма нечётных слагаемых должна быть чётной, а это может быть только в том случае, если число нечётных слагаемых чётно. А это означает, что число участников, обменявшихся конвертами нечётное число раз, чётное. В ходе решения задачи доказаны две теоремы. [1,12] Теорема 1. В графе Г сумма степеней всех его вершин – число чётное, равное удвоенному числу рёбер графа. Теорема 2. Число нечётных вершин любого графа чётно.

9 1.4. Путь в графе. Цикл Как пройти по рёбрам на рисунке 8 из А 1 в А 5 ? Вот три последовательности рёбер, следуя которым можно попасть из А 1 в А 5 : (А 1,А 4 ); (A 4,A 6 ). (А 1,А 2 ); (А 2,А 4 ); (А 4,А 5 ). (А 1,А 4 ); (А 4,А 2 ); (А 2,А 1 ); (А 1,А 4 ); (А 4,А 5 ). В одних – рёбра повторяются, в других – не повторяются. Можно указать маршрут от А 1 до А 5, содержащий все вершины графа. Таков, например, маршрут: (А 1,А 2 ); (А 2,А 4 ); (А 4,А 3 ); (А 3,А 1 ); (А 1,А 4 ); (А 4,А 5 ). Но не всякую последовательность рёбер, ведущих из А1 в А5, называют путём из А 1 в А 5. Оглавление А4А4 А3А3 А5А5 А2А2 А1А1 Рис.8 Путём от А 1 до А n в графе называется такая последовательность рёбер, ведущая от А 1 к А n, в которой каждые два соседних ребра имеют общую вершину и никакое ребро не встречается более одного раза. [1,16] Вершина А 1 – начало пути, вершина А n – конец. Из определения следует, что последовательность рёбер (А 1,А 4 ); (А 4,А 2 ); (А 2,А 1 ); (А 1,А 4 ); (А 4,А 5 ) не является путём в графе.

10 1.4. Путь в графе. Цикл Заметим, что согласно определению вершины пути могут повторяться, т. е. путь может быть самопересекающимся. Путь от А 1 до А n называется простым, если он не проходит ни через одну из вершин графа более одного раза. Циклом называется путь, в котором совпадают его начальная и конечная вершины. Простым циклом в графе называется цикл, не проходящий ни через одну из вершин графа более одного раза. Длиной пути называется число рёбер этого пути. Аналогично длиной цикла называется число рёбер в этом цикле. От вершины А 1 до вершины А 6 графа на рисунке 9 можно пройти четырьмя путями; один из них – длины 1, второй – длины 2 и два пути длиной 6. Оглавление А5А5 А2А2 А3А3 А4А4 А6А6 А1А1 Рис.9

11 1.5. Связность графа Задача. Может ли так случиться, что в одной компании из шести человек каждый знаком с двумя и только с двумя другими? [1,17] Решение. Участника этой компании изобразим вершиной графа, а отношение знакомства между двумя участниками – ребром. Изобразим графы, которые могут соответствовать такой компании (рис.10 и 11). Итак, ситуация, рассмотренная в задаче, вполне возможна. Но случай, рассмотренный на рисунке 11, соответствует не одной, а двум компаниям, участники одной из них не знакомы с участниками другой. Про граф, изображенный на рисунке 12, говорят, что он связный, так как из каждой вершины по рёбрам можно попасть в любую другую. Делаем вывод, что в этом случае каждый через своих знакомых может познакомиться со всеми остальными. Во втором случае получились два простых цикла, не сцепленные между собой в вершинах. Такой граф называется несвязным. Две вершины А и В графа называются связными, если в графе существует путь с концами А и В. Две вершины графа называются несвязными, если в графе не существует ни одного пути, связывающего их. Пример. В графе Г (рис.13) вершины А и В – связные, а вершины А и Н – несвязные. Граф называется связным, если каждые две вершины его связные. Граф называется несвязным, если хотя бы две вершины его несвязные. Оглавление Рис.10 Рис.11 Рис.12 H D E C B А

12 1.5. Связность графа Теорема. Связный граф представляет собой простой цикл тогда и только тогда, когда каждая его вершина имеет степень 2. [1,18] Прямая теорема. Если Г – связный граф и степень каждой его вершины равна 2, тогда Г – простой цикл. Доказательство. Из каждой вершины данного графа в любую другую ведёт путь. Начнём путь из какой-нибудь вершины А и пройдем по одному из двух рёбер, которым принадлежит эта вершина. Попав во вторую вершину, выйдем из неё по второму ребру и т. д. С необходимостью все рёбра графа будут пройдены, и мы вернёмся в исходную вершину А (рис.13). Путь замкнётся. Обратная теорема. Если граф Г – простой цикл, тогда степень каждой его вершины равна двум. Доказательство. Так как граф Г – замкнутый простой путь, то из каждой его вершины можно попасть в любую другую, не проходя ни через какую вершину более одного раза. Степень каждой вершины такого графа равна двум. Покажем, что в простом цикле не может быть вершины, степень которой не равна двум. Если какая-то вершина в графе имеет степень меньше двух, то она не принадлежит никакому простому циклу (рис.14). Если какая-то вершина имеет степень больше двух, то никакой простой цикл (по определению) не может содержать все рёбра, которым принадлежит эта вершина (рис.15). Оглавление А А Рис.15 Рис.14 Рис.13

13 1.6. Операция удаления ребра. Мост Важные закономерности, свойственные графам, обнаруживаются при удалении из них рёбер. При удалении ребра (А, В) из графа Г получается граф с теми же вершинами, что и граф Г, и всеми рёбрами, кроме ребра (А, В). [1,19] Пример осуществления операции удаления ребра (А, В) из графа показан на рисунке 16. При удалении ребра из связного графа новый граф может оказаться как связным, так и несвязным. Ребро (А, В) называется мостом графа Г, если в графе, полученном после удаления из Г ребра (А, В), вершины А и В оказываются несвязными. На рисунке 16 мост (А, В) выделен штриховой линией. Оглавление В А В А Рис.16

14 1.6. Операция удаления ребра. Мост Существуют несколько признаков мостов. Известно, что признак какого-то объекта может заменить его определение, т. е. по признаку можно распознать объект. Рассмотрим признаки мостов. [1,20] Ребро (А, В) является мостом в том и только в том случае, если (А, В) – единственный путь, соединяющий вершины А и В (рис.17). Ребро (А, В) является мостом в том и только в том случае, если найдутся две вершины С1 и С2 такие, что каждый путь, соединяющий их, содержит А и В (рис.18). Ребро (А, В) является мостом в том и только в том случае, если оно не принадлежит ни одному циклу (рис.17 и 19). Докажем справедливость третьего признака. Прямая теорема. Если ребро (А, В) не принадлежит ни одному циклу, то (А, В) – мост. Так как ребро (А, В) не принадлежит ни одному циклу, то при его удалении не останется пути, связывающего А и В, т. е. (А, В) является мостом (рис.17). Обратная теорема. Если ребро (А, В) – мост, то (А, В) не принадлежит ни одному циклу. Если бы ребро (А, В) принадлежало циклу (рис.19), то при удалении ребра (А, В) остался бы второй путь, связывающий А и В (на рисунке 19 он выделен штриховой линией), т. е. ребро (А, В) не было бы мостом. Следовательно, (А, В) не принадлежит циклу. Оглавление В А В А С2С2 С1С1 Рис.18 Рис.19 В А Рис.17

15 1.7. Деревья. Лес Задачи: а) Нарисуйте граф с семью вершинами и шестью рёбрами, не имеющий ни одного цикла. б) Нарисуйте связный граф с семью вершинами и шестью рёбрами. в) Нарисуйте граф с семью вершинами, в котором для любых двух вершин существует один и только один связывающий их путь. г) Постройте связный граф с семью вершинами, каждое ребро которого – мост. [1,21] Оглавление Рис.20 Рассмотрим внимательно рисунки, которые строили при решении задачи. Что характерно для всех построенных графов? Во-первых, они связные; во-вторых, они не содержат циклов. Такие графы выделяются в отдельный класс, представители которого именуются деревьями Деревом называется всякий связный граф, не имеющий циклов (рис.20). Удобно считать, что граф, состоящий из одной изолированной вершины, тоже является деревом. Для каждой пары вершин дерева существует единственный соединяющий их путь. Вершина дерева, степень которой равна единице, называется висячей вершиной (на рис.20 висячие вершины выделены закрашенными кружками).

16 1.7. Деревья. Лес Лесом называется несвязный граф, представляющий объединение деревьев (рис.21 и 22). Всякое ребро в дереве (и в лесе) является мостом (признак 3). Постройте какое-нибудь дерево с пятью вершинами и подсчитайте число рёбер в полученном графе. Оказывается, что в любом дереве с пятью вершинами всегда будет четыре ребра. Теорема. Дерево с в вершинами имеет в – 1 ребро. [1,22] Для того чтобы из одного дерева Г, не являющегося изолированной вершиной, получить два дерева с теми же вершинами, необходимо удалить из Г одно ребро. Для образования трёх деревьев необходимо удалить из Г два каких-нибудь ребра. Самое большее из дерева Г с в вершинами можно получить в деревьев, каждое из которых является изолированной вершиной. Для этого необходимо удалить в – 1 ребро из дерева Г. Итак, действительно, в дереве с в вершинами в – 1 ребро. Оглавление Рис.21 Рис.22

17 1.8. Представление о плоском графе На рис.23 (а) изображён граф Г; некоторые рёбра его пересекаются. На рис.23 (б) этот же граф Г изображён так, что его рёбра не пересекаются. Граф Г называют плоским, если его можно нарисовать на плоскости так, чтобы никакие два его ребра не имели других общих точек, кроме их общей вершины. Рисунок графа, в котором никакие два его ребра не пересекаются, если не считать точками пересечения общие вершины, называют плоским представлением графа. Ясно, что плоское представление имеет только плоский граф. Обратно, у всякого плоского графа непременно найдётся плоское представление. Плоские графы – простые циклы, деревья, лес, а также и граф, содержащий цикл, из вершин которого «выходят» деревья (рис.24). Приведём ещё один пример плоского графа Г (рис.25 а). Легко проверить, что на рис.25 (б) изображён тот же самый граф Г, что и на рис.25 (а). Рис.25 (б) служит плоским представлением графа Г. Примером не плоского графа может служить полный граф с пятью вершинами. Любые попытки нарисовать его плоское представление обречены на неудачу. В качестве характеристики плоского представления графа вводится понятие грани. Гранью в плоском представлении графа Г называется часть плоскости, ограниченная простым циклом и не содержащая внутри других циклов. Оглавление Рис.23 а)б) Г: А3А3 А2А2 А1А1 А4А4 А5А5 А3А3 А2А2 А1А1 А4А4 А5А5 А3А3 А2А2 А1А1 А4А4 А5А5 А6А6 А3А3 А2А2 А1А1 А4А4 А5А5 А6А6 а) б) Г: Рис.24 Рис.25 Г:

18 1.8. Представление о плоском графе На рис.26 плоское представление графа Г с четырьмя гранями: (1, 7, 4, 1), (1, 3, 2, 4, 1), (1, 2, 3, 1), (2, б, 5, 4, 2). Часть плоскости, ограниченная простым циклом (1, 2, 4, 1), гранью не является, так как содержит внутри себя цикл (1, 2, 3, 1). А на рис.27 часть плоскости, ограниченная простым циклом (1, 2, 3, 4, 5, 1), является гранью, так как ребро (4, 5), расположенное внутри грани, не образует цикла. Не является гранью и заштрихованная часть плоскости на рис.28, так как она содержит внутри себя цикл, да к тому же эта часть плоскости не ограничена циклом. Ребро (А, В) на рис.28 является мостом, соединяющим циклы. Такие мосты будем называть перегородками. Простой цикл, ограничивающий грань, назовём границей грани. Две грани будем называть соседними, если их границы имеют хотя бы одно общее ребро. Грани (1, 3, 2, 1) и (1, 3, 2, 4, 1) на рис.27 соседние, а грани (1, 3, 2, 1) и (2, 6, 5, 4, 2) не являются соседними. Оглавление Рис.26Рис.27 А В Рис.28

19 1.8. Представление о плоском графе В качестве грани можно рассматривать и часть плоскости, расположенную «вне» плоского представления графа; она ограничена «изнутри» простым циклом и не содержит в себе других циклов. Эту часть плоскости называют «бесконечной» гранью. На рис.29 часть бесконечной грани заштрихована. Часть плоскости, заштрихованная на рис.30, гранью не является, так как она не ограничена изнутри простым циклом. Ребро (А, В) в этом графе является перегородкой. Всякое плоское представление графа либо не имеет бесконечной грани (рис.30), либо имеет в точности одну бесконечную грань (рис.29). Как особый случай вводится бесконечная грань в плоском представлении дерева и леса. В плоском представлении дерева и леса за грань принимают всю плоскость. Оглавление А В Рис.29 Рис.30

20 1.9. Триангулированный граф На рис.31 (а) изображён плоский граф Г с пятью вершинами. Если добавить к нему рёбра (1, 3) и (1, 5), то полученный новый граф Г тоже будет плоским (рис.31, б). К этому графу не удастся добавить ни одного ребра так, чтобы новый граф тоже был плоским. Плоский граф называется максимально плоским, если невозможно добавить к нему ни одного ребра так, чтобы полученный граф был плоским. Граф, изображенный на рис.31 (б), является максимально плоским. Каждая грань в плоском представлении максимально плоского графа имеет 3 вершины. Поэтому максимально плоский граф называют ещё триангулированным. [1,34] Операция добавления новых рёбер, в результате которой в плоском представлении каждая грань имеет ровно 3 вершины, называется триангуляцией графа. Обратите внимание на то, что триангулированный граф имеет ровно три «внешних» ребра (рис.31, б). (Они составляют границу бесконечной грани.) Интересно, что триангулированные графы с одним и тем же числом вершин могут не совпадать. На рис.32 изображены два разных триангулированных графа с шестью вершинами. В одном есть две вершины степени 5 (рис.32, правый), а в другом вершины степени 5 нет (рис.32, левый). Но существует только один триангулированный граф с четырьмя вершинами и только один – с пятью вершинами. Оглавление а) б) Рис.31 Рис.32

21 1.10. Теорема Эйлера Оглавление Рассмотрим графы, показанные на рисунке 33. Эти графы состоят из вершин (В), рёбер (Р) и граней (Г). Так, граф на рис.33 (а) имеет 10 вершин, 11 ребер и 3 грани (считая внешнюю); на рис.33 (б) – 5 вершин, 9 ребер и 6 граней; на рис.33 (в) – 10 вершин, 14 рёбер и 6 граней. Нетрудно обнаружить интересную закономерность, связывающую число вершин (В) с числом рёбер (Р) и числом граней (Г) графа: 10 – = 2 (для графа на рис.33 а); 5 – 9 +6 = 2 (для графа на рис.33 б); 10 – = 2 (для графа на рис.33 в); т. е. В – Р + Г = 2. Эта закономерность В – Р + Г = 2 впервые была обнаружена Р. Декартом (1596–1650), когда он исследовал правильные многогранники. Спустя почти 100 лет великий математик Леонард Эйлер (1707–1783) переоткрыл формулу Декарта и первым доказал её. Поэтому закономерность В – Р + Г = 2 получила название формулы Эйлера для плоского графа. Существует несколько разновидностей формулировок и доказательств формулы Эйлера. а)б)в) Рис.33 в)

22 1.10. Теорема Эйлера I. Теорема: Для любого плоского графа имеет место соотношение В – Р + Г = 2, (1) где В число вершин графа; Р число его рёбер; Г число его граней. [7,34] Доказательство этой теоремы проведем методом математической индукции (по числу граней Г). Пусть дан плоский граф, число граней которого равно 1, и предположим, что этот граф имеет n вершин (а следовательно, он будет иметь n – 1 рёбер). В этом случае В – Р + Г = n – n = 2. также плоским (на рис.34 грань изображена пунктиром). Получим граф с k + 1 гранью. Предположим, что грань F имеет m рёбер, из которых l рёбер совпадает с рёбрами прежнего графа. Тогда l + 1 вершин грани F также совпадают с l + 1 вершинами прежнего графа. Следовательно, для вновь полученного графа будем иметь: В 1 = В + m – (l + 1), Р 1 = Р + (m – l ), Г 1 = k + 1, где B 1, P 1 и Г 1 – соответственно число вершин, рёбер и граней графа с числом граней k + 1. Подставим эти значения B 1, P 1 и Г 1 в выражение В – Р + Г. Получим: B 1 – P 1 + Г 1 = В + m – (l + 1) – Р – (m – l ) + k + 1, или B 1 – P 1 + Г 1 = В – Р + k. Так как В – Р + k = 2, то и B 1 – P 1 + Г 1 = 2. Теорема доказана. Оглавление Рис.34 F Таким образом, при Г = 1 соотношение (1) верно. Предположим теперь, что соотношение (1) верно для такого плоского графа, который имеет k граней, и докажем, что оно верно для плоского графа, который имеет k + 1 грань. Пусть плоский граф, изображенный на рис.34, имеет k граней. Добавим к этому графу новую грань F так, чтобы полученный граф был

23 1.10. Теорема Эйлера II. Теорема: Всякое вложение связного графа с В вершинами и Р рёбрами в сферу разбивает её на Г областей, причём В – Р + Г = 2. [8,5] Доказательство. Пусть на сфере нарисован произвольный связный граф с В вершинами и Р рёбрами, разбивающий её на Г областей. Мы будем последовательно упрощать наш граф, уменьшая числа его рёбер и вершин, но так, чтобы сумма В – Р + Г сохранялась при всех упрощениях. Если после всех упрощений будет выполнено условие В – Р + Г = 2, значит, оно выполнялось и для исходного графа. Упрощения графа будут двух сортов. 1°. Стягивание в точку одного ребра, соединяющего две разные вершины. Такая операция уменьшает на единицу число вершин графа (В) и точно так же уменьшает число его рёбер (Р). Число областей (Г), на которые граф делит сферу, при этом не изменяется – так что сумма В – Р + Г сохраняется (рис.35, а – д). Наша операция 1° может увеличить число петель в графе – но это нам не мешает. Напротив, наша промежуточная цель – сделать число вершин графа (В) равным 1 (рис.35, д). Такой граф называется букетом петель; упростить его дальше с помощью операции 1° невозможно; поэтому мы вводим следующую операцию. 2°. Пусть на сфере лежит букет петель; мы уберём одну из них. Тогда число областей (Г), на которые делит сферу новый граф (он – тоже букет петель), на единицу меньше, чем было у исходного графа. Значит, сумма В – Р + Г сохраняется при преобразовании 2°. Ясно, что таким образом мы можем уменьшить число рёбер графа до нуля: граф превратится в одну точку на сфере, а для такого графа В – Р + Г = 1 – = 2. Доказательство теоремы Эйлера закончено. а) б) в) г) д) Рис.35 Оглавление

24 1.10. Теорема Эйлера III. Известный популяризатор математики У. Болл в книге «Математические эссе и развлечения» [2,252] приводит следующие рассуждения для доказательства формулы Эйлера. Для исследования топологии замкнутой поверхности (такой, как сфера или тор) нарисуем на ней некую карту, т. е. разобьем ее на F односвязных «стран», проведя Е дуг (границ наших стран), соединяющих (попарно) V точек (вершин карты). При сжатии или растяжении поверхность деформируется; однако так как мы не допускаем разрывов и склеиваний поверхности, числа F, Е, V при этом не меняются. Докажем, что число F – Е + V характеризует саму поверхность, а не только карту на ней, т. е. что если на той же поверхности другая карта имеет F' стран, Е' границ и V' вершин, то F' – Е' + V' = F – Е + V. В самом деле, предположим, что эти две карты налагаются одна на другую и их границы, взаимно пересекая друг друга, образуют третью карту, имеющую скажем, f областей, е границ, v вершин. Число v вершин этой карты равно сумме V + V' вершин двух исходных карт плюс число точек пересечения границ наших двух карт. Видоизменим первую карту, прибавив эти точки пересечения в качестве новых вершин, что приведет к разбиению старых границ (на которых лежат эти и вершины) на меньшие части. Поскольку числа Е и V увеличиваются при этом на одну и ту же величину, сумма F – Е + V не изменится. Не использованные до сих пор границы и вершины третьей карты можно теперь добавить в виде последовательных «цепей», каждая из которых соединяет две какие-то вершины и разделяет соответствующую «страну» на две новые «страны». Пусть, например, некоторая цепь состоит из u новых границ, сходящихся в u – 1 новых вершинах (u 1). Включение такой цепи увеличивает число F на 1, число Е – на u и число V – на u – 1; однако сумма F – Е + V при этом, очевидно, остаётся неизменной. Продолжая этот процесс до включения всей третьей карты, мы убедимся, что f – е + v = F – Е + V. Аналогично f – е + v = F' – Е' + V'. Следовательно, F' – Е' + V' = F – Е + V, что и требовалось доказать. Инвариант χ = F – Е + V называют эйлеровой характеристикой поверхности. Для заданной поверхности можно найти ее эйлерову характеристику путем размещения на ней той или иной простой карты. Например, в случае сферы мы можем использовать вписанный в сферу тетраэдр, для которого F = V = 4 и Е = 6, откуда следует, что здесь χ = 2. Тем самым мы доказали формулу Эйлера F – Е + V = 2 Оглавление

25 1.10. Теорема Эйлера IV. А вот как доказывается теорема Эйлера в книге «Числа и фигуры» [6,97] известных немецких учёных ХХ века Ганса Радемахера и Отто Теплица. На карте рис.36, например, имеется 8 вершин (т. е. точек, в которых соприкасаются по крайней мере 3 страны), 6 стран и 12 границ (каждая граница считается от одной вершины до другой, ближайшей), и действительно, мы имеем здесь = Чтобы доказать теорему, представим себе, что наш рисунок изображает вовсе не географическую карту, а систему разграниченных плотинами полей; извне система окружена водой, и нам требуется последовательно снимать эти плотины одну за другой так, чтобы все поля одно за Оглавление Рис.36 Рис другим оказались орошенными водой (рис.37). Для осуществления этого вовсе нет необходимости снимать все плотины: наоборот, мы условимся оставлять те плотины, с обеих сторон которых поля уже орошены; во всяком случае можно открывать только те плотины, с одной стороны которых поле уже орошено, с другой стороны – еще нет, так что при снятии каждой из них для воды открывается всякий раз новое поле. Ясно, что для орошения имеющихся у нас, кроме внешнего пространства, f – 1 полей необходимо снять не более f – 1 плотин. С другой стороны, ясно также, что процесс снятия плотин должен продолжаться до тех пор, пока у нас не останется ни одного неорошенного поля, т. е. пока у нас не будут орошены все f – 1 полей. Процесс, следовательно, не может быть закончен, прежде чем не будут сняты f – 1 плотин. Итак, число подлежащих снятию плотин в точности равно f – 1. Рассмотрим теперь систему плотин, оставшихся нетронутыми.

26 1.10. Теорема Эйлера 1. Двигаясь по ним, можно еще сухим путем достигнуть любой вершины, выходя из любой другой. Ведь первоначально, когда вода находилась лишь вне нашей системы, это было, конечно, возможно – в противном случае мы имели бы дело не с одной, а с двумя или несколькими независимыми системами полей, с островами, расположенными в окружающей массе воды, и нашу задачу нужно было бы в этом случае решать для каждой такой системы в отдельности. Но если бы в результате одного из последующих снятий какой–либо плотины АВ оказалось, что оставшиеся плотины распались на две независимые системы (рис.38), так что с вершины, расположенной на одной из них, нельзя было бы уже сухим путем достигнуть вершины, расположенной на другой системе, то вода с обеих сторон свободно протекала бы между А и В, а это означало бы, что поля с обеих сторон плотины АВ уже были орошены до ее снятия. Мы же условились такие плотины не снимать. 2. Если из произвольной вершины, например Р, послать двумя различными путями двух курьеров для обхода всех плотин и посещения всех вершин, то возможность встречи этих курьеров в какой-либо точке Q исключается. Ведь Оглавление Рис.38 А В Рис.39 Q P если бы вдоль оставшихся плотин от Р к Q вело два различных пути, как это указано на рис.39, то оба эти пути, вместе взятые, ограничили бы некоторую область, со всех сторон окруженную нетронутыми плотинами и внутрь которой, следовательно, вода никогда не смогла бы проникнуть. Из данного исходного пункта можно достигнуть любой другой вершины только единственным, вполне определенным путем. При этом, прежде чем попасть в вершину, нужно пройти всякий раз некоторый определенный отрезок (плотину), и, наоборот, по прохождении каждого отрезка (плотины) достигается некоторая вершина – конечный пункт этого отрезка. Следовательно, таких конечных точек существует столько же, сколько остается нетронутых плотин. Так как кроме них в общее число вершин входит еще вершина, служащая исходным пунктом, то количество нетронутых плотин в точности равно е – 1. Всего, значит, у нас будет f – 1 снятых и е – 1 неснятых плотин. Поэтому общее число плотин k = (f – 1) + (е – 1) = f + е – 2.

27 1.10. Теорема Эйлера V. Наиболее лаконичное доказательство теоремы Эйлера о плоском графе следующее. [1,24] Пусть граф – связный плоский граф без перегородок. Определим значение алгебраической суммы В – Р + Г для его произвольного плоского представления. Преобразуем данный граф в дерево, содержащее все его вершины. Для этого удалим некоторые рёбра данного графа, разрывая поочередно все Оглавление Рис.40 его простые циклы, причём так, чтобы граф оставался связным и без перегородок. Заметим, что при таком удалении одного рёбра число граней уменьшается на 1, так как при этом либо пропадёт один простой цикл, либо два простых цикла преобразуются в один. Следовательно, значение разности Р – Г при этом остаётся неизменным. На рис.40 рёбра, которые удаляем, выделены штриховой линией. В полученном дереве обозначим число вершин – В д, число рёбер – Р д, число граней – Г д. Справедливо равенство Р – Г = Р д – Г д. В дереве одна грань, т. е. Р – Г = Р д – 1. Вспомним, что операция удаления рёбер из графа не меняет число его вершин, т. е. В = В д. По теореме в дереве В д – Р д = 1. Отсюда В – Р д = 1, т. е. Р д = В – 1, а потому Р – Г = В – 2 или В – Р + Г = 2. Теорема Эйлера – очень сильный факт, и из него можно получить интересные следствия.

28 1.11. Следствия из теоремы Эйлера [3,163] Следствие 1. Для любого плоского графа справедливо неравенство 2Р 3Г. Доказательство. Каждая грань плоского графа ограничена не менее, чем тремя рёбрами. Каждое ребро принадлежит двум граням. Поэтому 2Р 3Г. Следствие 2. 1) Для плоского связного графа справедливо неравенство Р 3В – 6. 2) Для любого плоского графа (в том числе и несвязного) справедливо неравенство Р 3В – 6. Доказательство. 1) Согласно следствию 1: 2Р 3Г, Г Р.(*) По теореме Эйлера В – Р + Г = 2. Подставим в формулу соотношение (*). Получим: В – Р + Р 2 В – Р 2 Р 3В – 6 2) Для случая несвязного графа требуемое утверждение получается сложением неравенств для компонент связности графа. Следствие 3. Граф, имеющий 5 вершин, каждая из которых соединена ребром с любой другой, не является плоским. Доказательство. По условию В = 5, Р = 5 · 4 : 2 = 10. Для этого графа не выполняется неравенство Р 3В – 6, поэтому он не является плоским. Оглавление

29 1.11. Следствия из теоремы Эйлера [3,163] Следствие 4. В любом плоском графе есть вершина, степень которой не превосходит 5. Доказательство. Так как граф плоский, то верно неравенство Р 3В – 6. Допустим, что утверждение неверно. Тогда у всех вершин графа степени больше 5 (или 6, или больше 6). Значит 2Р 6В или Р 3В. Последнее неравенство противоречит неравенству Р 3В – 6. Значит, наше предположение о том, что в плоском графе степени всех вершин больше 5, неверно. Следовательно, существует вершина, степень которой не превосходит 5. Теорема 1. Полный граф с числом вершин n будет плоским, если n 4. [7,40] Доказательство. В самом деле, по определению полный граф имеет n(n – 1)/2 ребер, а полный плоский граф с n вершинами имеет Зn – 6 ребер. Поскольку число ребер любого плоского графа не больше, чем число ребер полного плоского графа с тем же числом вершин, имеет место следующее неравенство: или n 2 – 7n Решив это неравенство, получим, что n 4. Итак, если полный граф имеет 5 и более вершин, он плоским быть не может. Оглавление n(n – 1) 3n – 6, 2

30 1.11. Следствия из теоремы Эйлера [3,163] Доказательство. Граф, соответствующий условию теоремы, будет иметь только четырехугольные грани (рис.41). Действительно, если предположить, что он имеет хотя бы одну треугольную грань, то из трех ее вершин две будут принадлежать одному и тому же множеству, что противоречит условию теоремы. Аналогично можно доказать, что этот граф не может иметь грань с числом ребер больше четырех. В противном случае в нем не будут проведены все возможные дуги, соединяющие точки множества А и В. Оглавление Рис.41 Теорема 2. Пусть на плоскости даны два множества точек: А = {X 1, X 2,..., Х n } и В = {Y 1, Y 2,..., Y m }, где n 2 и m 2. Соединим отрезками (или дугами) все возможные пары точек X i (2 i n) и Y j (2 j m) так, чтобы соединяющие их отрезки (или дуги), кроме этих точек, других точек пересечения не имели. Полученный граф будет иметь m + n – 2 граней. [7,42] Итак, все грани графа, соответствующего условию теоремы, четырехугольные. Тогда 4Г = 2Р, или Р = 2Г. С другой стороны, так как граф плоский, то имеет место соотношение В – Р + Г = 2. Подставив в эту формулу значение В = m + n, получим: Г = 2 + 2Г – (m + n), или Г = m + n – 2. Ясно, что в этом случае Р = 2(m + n – 2).

31 1.12. Приложение формулы Эйлера к географии [2,258] Рассмотрим приложение формулы Эйлера к географической задаче о соотношении числа гор, долин и перевалов на любой планете (разумеется, не покрытой океаном, – для Земли мы будем учитывать также и подводные «горы» или «низины» («долины»)). Гора (вершина) – это некая точка, в которой достигается локальный максимум высоты, а долина (низина или яма) – это некая точка локального минимума высоты. Каждая из таких точек окружена системой вложенных контуров (линий постоянной высоты). Перевал – это точка, где линии постоянной высоты пересекаются; он характеризуется тем, что в одном направлении рассматриваемая точка представляется «самой высокой» (направление подъема на перевал и спуска с него), а в другом – самой низкой (направление того горного хребта, к которому относится перевал). Если разделить пополам углы, образованные пересекающимися линиями постоянной высоты, то мы как раз получим четыре направления, в каждом из которых можем продвигаться вдоль линий (наибольшего) наклона, либо вверх к возвышенности вдоль водораздела, либо вниз к долине (впадине) вдоль русла. Ясно, что вершины (горы) и пары соединяющих их водоразделов можно рассматривать как вершины и границы некоторой карты, каждая «страна» (долина) которой окружает одну из долин. Следовательно, если имеется В долин, Р перевалов и Г горных вершин, то всегда В – Р + Г = 2. Аналогично впадины и соединяющие их русла – это вершины и границы двойственной карты, каждая «страна» («плато») которой окружает одну из горных вершин. Оглавление

32 1.13. Теорема Эйлера и правильные многогранники Многогранники, известные из курса геометрии, принадлежат к числу многогранников, называемых простыми. Многогранник называется простым, если его каким-либо образом можно деформировать в сферу. Рассмотренная ранее теорема Эйлера имеет место и для простых многогранников. Проверим ее справедливость для правильных многогранников: для тетраэдра (рис.42, а): – 6 = 2; для куба (рис.42, б): – 12 = 2; для додекаэдра (рис.42, в): – 30 = 2; для октаэдра (рис.42, г): – 12 = 2; для икосаэдра (рис.42, д): – 30 = 2. Убедиться в справедливости этой теоремы для любого выпуклого многогранника можно с помощью следующего рассуждения. [7,60] Удалим одну из граней данного многогранника и, мысленно деформируя его (например, растягивая), сделаем частью плоскости (рис.43). Получится плоский граф с тем же числом вершин и ребер, что и данный многогранник; число же граней графа будет на единицу меньше числа граней данного многогранника. Поскольку ранее было доказано, что теорема Эйлера имеет место для плоского графа (учитывая его внешнюю грань), то эта теорема имеет место и для данного многогранника. С помощью теоремы Эйлера мы можем показать, что существует пять и только пять различных топологически правильных многогранников. Оглавление Теорема Эйлера и правильные многогранники б) Рис.42 в) д) г) а) B C A D A B C D S Рис.43 S

33 1.13. Теорема Эйлера и правильные многогранники Допустим, что из каждой вершины многогранника исходит по q ребер и каждая грань имеет r сторон. Тогда Вq = 2Р = Гr (1) Преобразуя равенство (1), используя формулу Эйлера, получим:,. откуда С другой стороны, поскольку В, Р и Г – натуральные числа, имеет место следующее неравенство: 2q + 2r – qr > 0 (3) или (q – 2) (r – 2) < 4 (4) Решив неравенство (4), получим допустимые пары значений q и r: (3, 3), (4, 3), (3, 4), (5, 3), (3, 5). Таким образом, существует только пять типов топологически правильных многогранников: тетраэдр, куб, октаэдр, додекаэдр, икосаэдр (на рис.42 изображены названные многогранники и соответствующие им плоские графы). В – Р + Г = 4qr 1 – q + 2r – qr q2r Оглавление Теорема Эйлера и правильные многогранники В = Р = Г 111 q2r В = 4r4r, Р = 2qr2qr, Г = 4q4q. 2q + 2r – qr Рис.44 С помощью теоремы Эйлера мы можем показать, что существует пять и только пять различных топологически правильных многогранников. Заметим, что многогранник называют топологически правильным, если из всех его вершин исходит одинаковое число ребер и каждая грань имеет одинаковое число ребер (рис.44). Пусть В – число вершин, Г – число граней и Р – число ребер произвольного выпуклого многогранника.

34 1.13. Теорема Эйлера и правильные многогранники Из теоремы Эйлера следует еще один интересный факт: не существует многогранника, у которого не было бы либо треугольных, либо четырехугольных, либо пятиугольных граней. Важным и интересным вопросом теории многогранников является вопрос их классификации. Так, все выпуклые многогранники считаются многогранниками нулевого рода. Существуют многогранники первого, второго и т. д. рода. Например, многогранник, изображенный на рисунке 45, является многогранником первого рода; он гомеоморфен тору (рис.46). Многогранник, изображенный на рисунке 47, является многогранником второго рода. Нетрудно показать, что род многогранника равен числу сквозных отверстий, имеющихся на нем. Иначе, если многогранник имеет р отверстий, то и род его равен р. В этом случае между числами его вершин В, ребер Р и граней Г имеет место следующее соотношение: В – Р + Г = 2 – 2p. Так, для многогранника, изображенного на рисунке 45, имеем: В = 16, Р = 32, Г = 16. Подставив эти значения в формулу В – Р + Г = 2 – 2 р, получим 16 – = 2 – 2p, откуда р = 1. В частности, если р = 0, получаем теорему Эйлера для простых многогранников (В – Р + Г = 2). Число 2 – 2 р называют эйлеровой характеристикой многогранника. Оглавление Теорема Эйлера и правильные многогранники Рис.45 Рис.46 Рис.47

35 Часть II Теорема Эйлера о плоском графе и задачи по математике Оглавление

36 Задача 1 Внутри выпуклого 100-угольника выбрано 30 точек так, что никакие 3 из них не лежат на одной прямой. 100-угольник разрезан на треугольники так, что совокупность вершин всех точек этих треугольников состоит из 30 выбранных точек и 100 вершин первоначального многоугольника. Сколько имеется треугольников? Решение. С п о с о б I. В основе традиционного решения лежит теорема о сумме углов треугольника – 180º. Углы треугольников, имеющие вершину в одной из 30 внутренних точек, в сумме дают 360º. Сумма углов выпуклого 100-угольника ищется по формуле 180º (n – 2), где n – число сторон. Значит общая сумма углов 360º º (100 – 2) = 28440º. Тогда число треугольников 28440º : 180º = 158. С п ос о б II. Применим к условию задачи аппарат теории графов. Составим плоский граф, в котором: В = = 130 вершин и Р = 3В – 6 – (100 – 3) = 3В – 103 рёбер, т. е. Р = – 103 = 287. В полном плоском графе число рёбер Р = 3В – 6. Во внешней области многоугольника, чтобы дополнить его до полного графа, проводят n – 3 рёбер, где n – число вершин выпуклого многоугольника. Согласно теореме Эйлера В – Р + Г = 2, тогда: Г = Р – В + 2, Г = 287 – = 159 – число граней с учётом внешней бесконечной области. Следовательно, треугольных областей 159 – 1 = 158. Ответ. Имеется 158 треугольников. Оглавление

37 Задача 2 Оглавление Рис.48 Рис.49 Внутри треугольника взяли n различных точек. Их соединили между собой и с вершинами треугольника так, что никакие два отрезка не имеют общих внутренних точек. Докажите, что число полученных отрезков не зависит от расположения точек, и найдите это число. всего получится 3(n – 1) + 3 = 3n внутренних отрезков. Это число не зависит от расположения точек. С п о с о б II. В основе решения лежит метод нахождения суммы всех углов. Сумма углов с вершиной во внутренней точке 360º, таких точек n. Сумма всех углов исходного треугольника 180º. Общая сумма углов будет равна (360n + 180)º. Внутренняя область всевозможными отрезками разбивается на треугольники. Число треугольников: Число сторон одного треугольника – 3, без учёта сторон исходного треугольника получим отрезков внутри исходного треугольника. Решение. С п о с о б I. Задачу можно решить, пользуясь методом математической индукции по числу внутренних точек n. База индукции n = 1 (рис.48). Если соединить точку с вершинами треугольника, то получим 3 новых отрезка, т. е. число отрезков будет равно 3 1. Индукционный переход (рис.49). Пусть внутри треугольника имеются n – 1 точек, удовлетворяющие условию задачи и они образуют 3(n – 1) отрезков. Добавим ещё одну внутреннюю точку. Эта точка окажется внутри какого–то треугольника. Соединим её отрезками с вершинами этого треугольника. Новых отрезков будет 3, значит, (360n + 180)º = 2n º 3(2n + 1) – 3 = 3n 2

38 Задача 2 С п о с о б III. Эту задачу можно решить с помощью графов. Рассмотрим плоский граф, в котором число вершин В = 3 + n. Так как внутренние области треугольные, то их число равно Г 3 = 3 + 2n – 2 = 2n + 1. Вместе с внешней областью их будет Г = 2n + 2. По теореме Эйлера В – Р + Г = 2, откуда: Р = В + Г – 2, Р = 3 + n + 2n + 2 – 2 = 3n +3. Не учитывая стороны исходного треугольника число внутренних отрезков будет равным 3n +3 – 3 = 3n. Оглавление Выводы. 1. Применение к решению олимпиадных задач 1 и 2 аппарата теории графов и теоремы Эйлера существенно сократило время их решения за счёт исключения громоздких вычислений (способ подсчёта углов) и обоснования решения (метод индукции). 2. Знания теоремы Эйлера и её следствий позволяют легко решать сложные математические задачи. 3. Далее рассматриваются задачи, встречающиеся на олимпиадах и конкурсах по математике. [1,3,4,6,7,9] Задачи решены с помощью теоремы Эйлера о плоском графе. Список задач приводится с учётом возрастания уровня их сложности. Ряд задач содержат обобщения большого круга подобных заданий. Результатом решения этих задач служит общая формула.

39 Задачи 3 и 4 На плоскости даны 6 прямых, из которых никакие две не параллельны и никакие три не проходят через одну точку. На сколько областей разбивают плоскость эти прямые? Решение. Рассмотрим плоский граф, в котором вершины – это точки пересечения прямых, рёбра – отрезки их соединяющие. Каждая прямая должна пересекаться с пятью другими прямыми и при этом она делится на 6 частей. Подсчитав число вершин и ребер полученного графа, найдем: Из формулы Эйлера получим: Г = 2 + Р – В или Г = – 15=23. Считая плоскость областью, получим окончательный результат: 23 – 1 = 22 (области). Ответ. 22 области. На какое наибольшее число частей разбивается плоскость при пересечении двух треугольников? Решение. Так как число получившихся частей должно быть наибольшим, Оглавление Рис.50 В = 5 · 6 = 15, Р = 6 · 6 = Решение. Так как число получившихся частей должно быть наибольшим, то каждая сторона одного треугольника будет пересекать 2 стороны второго треугольника (рис.50). Рассмотрим плоский граф, соответствующий условию задачи. Вершинами графа будут вершины треугольников – 6, и все точки пересечения сторон – 3 2, а рёбрами – отрезки, их соединяющие.Тогда: В = = 12, Р = = 18. Согласно теореме Эйлера о плоском графе В – Р + Г = 2, т. е. 12 – 18 + Г = 2, откуда Г = 8. Ответ. Наибольшее число частей 8.

40 Задачи 5 и 6 На какое наибольшее число частей разбивается плоскость при пересечении двух четырехугольников? Решение. Так как число получившихся частей должно быть наибольшим, то каждая сторона одного четырёхугольника будет пересекать 2 стороны второго четырёхугольника (рис. 51). Переведём условие задачи на язык теории графов. Тогда: В = = 16, Р = = 18. Так как граф плоский, то Г = Р – В + 2, т. е. Г = 24 – = 10. Ответ. Наибольшее число частей 10. Оглавление Рис.51 На сторонах четырехугольника взято соответственно 5, 6, 7 и 8 точек (не считая вершин четырехугольника), которые соединены друг с другом так, что никакие два отрезка, кроме этих точек, других общих точек не имеют. На какое наибольшее число частей разбивается этот четырехугольник данными отрезками? Решение. Мы можем составить плоский граф, который отвечает условию задачи. Он будет иметь В = = 30 вершин и Р = ЗВ – 6 – (В – 3) = 2В – 3 рёбер. В нашем случае В = 30, поэтому Р = 2 30 – 3 = 57, и по формуле Эйлера получим: Г = 29 (включая внешнюю грань). Значит число частей 29 – 1=28. Ответ. 28 частей.

41 Задача 7 В квадрате отметили 20 точек и соединили их непересекающимся отрезками друг с другом и с вершинами квадрата так, что квадрат разбился на треугольники. Сколько получилось треугольников? Решение. Будем считать отмеченные точки и вершины квадрата вершинами, а соединяющие их отрезки и стороны квадрата – рёбрами плоского графа. Для каждого куска, на которые этот граф разбивает плоскость, подсчитаем число ограничивающих его рёбер, и все полученные числа сложим. Каждое ребро разделяет два куска, поэтому мы получим удвоенное число рёбер 2Р. Так как все куски, кроме внешнего – треугольники, а внешний кусок ограничен 4 рёбрами, то получим: 2Р = 3(Г – 1) + 4, Р = 1,5(Г – 1) + 2, В = = 24. По теореме Эйлера В – Р + Г = 2, т. е. 24 – 1,5(Г – 1) – 2 + Г = 2, Г – 1,5(Г – 1) = – 20, – 0,5Г = – 21,5, Г = 43 (включая внешнюю грань). Ответ. Число треугольников равно 42. Оглавление

42 Задача 8 Задачу 7 можно обобщить следующим образом. Если внутри n-угольника взять m произвольных точек и соединить их друг с другом и вершинами n-угольника так, чтобы, кроме этих точек, не было бы никаких других точек пересечения, то внутренняя область многоугольника разобьётся на n + 2m – 2 треугольника. Решение. Возьмем n-угольник и в нем m произвольно расположенных точек. Соединим эти точки друг с другом и вершинами n-угольника (рис.52). Получим граф. Если проведем всевозможные непересекающиеся ребра во внешней области графа (одно из них изображено на рис.52 штриховой линией), то получим полный плоский граф с числом вершин m + n (и числом проведенных рёбер n – 3). Оглавление Рис.52 n m Согласно доказанному ранее следствию 2.1 этот граф будет иметь 3(n + m) – 6 рёбер. Если из числа ребер полного плоского графа вычтем n – 3, то получим число ребер данного графа; оно равно 2n + 3m – 3. Обозначив число треугольных областей через Г3, получим: n + 3Г 3 = 2(2n + 3m – 3), или Г 3 = n + 2m – 2, что и требовалось доказать.

43 Задача 9 Внутри выпуклого 20-уголъника взяты 8 точек, которые соединены отрезками друг с другом и вершинами многоугольника так, что эти отрезки других общих (кроме данных) точек не имеют. Сколько отрезков проведено внутри этого многоугольника? Решение. Результат решения предыдущей задачи позволит нам вычислить число всех треугольных областей: Г 3 = – 2 = 34. Вместе с внешней областью их будет = 35. Тогда В = m + n = 28, и по теореме Эйлера имеем: Р = – 2 = 61, Р 1 = Р – 20 = 41. Ответ. 41 отрезок. Оглавление

44 Задача 10 Внутри n-угольника взяли m произвольных точек и соединили их друг с другом и вершинами n-угольника так, чтобы, кроме этих точек, не было бы никаких других точек пересечения. 1. Для того, чтобы n-угольник можно было разбить на четырёхугольные области (необязательно выпуклые), необходимо, чтобы n было чётным. 2. Тогда число четырёхугольников будет равно: Решение. Ситуации, определенной условием задачи, соответствует плоский граф, изображенный на рисунке 53. Обозначив в этом графе число ребер через Р, число вершин через В, число граней через Г, а число четырехугольников через Г 4, получим: 2Р = 4Г 4 + n, В = m +n, Г = Г Поскольку граф является плоским, имеет место следующее соотношение: В – Р + Г = 2. Подставив в это равенство соответствующие значения Р, В и Г, найдем: 2(m +n) + 2(Г 4 + 1) – 4Г 4 – n = 4, откуда Так как Г 4 и m – целые числа, то n должно быть четным числом, что и требовалось доказать. Оглавление Рис.53 Г 4 = n + m – 1. 2 n 2

45 Задача 11 Для того чтобы m-угольник непересекающимися (кроме как в вершине) диагоналями разделился на k-угольные области, необходимо и достаточно, чтобы m было числом вида n(k – 2) + 2, где n – любое натуральное число. Решение. Пусть в m-угольнике можно провести p непересекающихся диагоналей, которыми его внутренняя область делится на k-угольники. Заметим, что в этом случае образуется p + 1 k-угольников. Следовательно, можем записать: 2P = k(p + 1) + m. С другой стороны, P = p + m. Подставляя значение Р из этого равенства в предыдущее, получим: 2(p + m) = k(p + 1) + m, откуда Кроме того, нам известно, что Г k = p + 1, или где Гk – число k-угольников. Поскольку p и Г – целые положительные числа, то числа также должны быть целыми. Значит, m – k = n(k – 2), или m = n(k – 2) + k, где n – натуральное число; с другой стороны, получаем, что m – 2 = n(k – 2), или m = n(k – 2) + 2. Заметим, что множество чисел m = n(k – 2) + 2 содержится в множестве чисел m = n(k – 2) + k; следовательно, можно взять значение m = n(k – 2) + 2, что и требовалось доказать. Оглавление Р = m – k. k – 2 Г k = m – 2, k – 2 m – k и m – 2 k – 2

46 Задачи 12 и 13 m-угольник с непересекающимися (кроме как в вершине) диагоналями разбит на 60 шестиугольных областей. Найти значение m. Решение. Используя результат решения предыдущей задачи, имеем: По условию имеем: откуда m = 242. Ответ. m = 242. При пересечении четырехугольника и треугольника плоскость разбивается самое большее на 8 частей. Каково наибольшее число точек пересечения, которые могут иметь эти фигуры? Решение. Рассмотрим граф, соответствующий условию данной задачи. Он имеет 8 граней. Так как граф плоский, то по теореме Эйлера: В – Р + Г = 2, В – Р – 8 = 2, Р – В = 6. Значит число новых точек пересечения 6. Ответ. 6 точек пересечения. Оглавление Г k = m – 2. k – 2 60 = m – 2, 6 – 2

47 Задача 14 В некотором выпуклом многоугольнике можно провести самое большее 13 непересекающихся диагоналей, которыми этот многоугольник разбивается на 14 треугольных областей. Сколько сторон имеет этот многоугольник? Решение. Переведём условие задачи на язык теории графов. Рёбра графа – это диагонали и стороны многоугольника, а грани – треугольные и внешняя области. Вершины графа (вершины многоугольника) обозначим за n. Тогда: В = n, Г = = 15, 2Р = n. Т. к. граф плоский, то по теореме Эйлера: n = 16. Ответ. 16 сторон. Оглавление n – 21 – n + 15 = 2, 2 n =n = 8, 2

48 Задача 15 Докажите, что каждый n-угольник разбивается на n – 2 треугольника, если в нем провести все непересекающиеся диагонали. Решение. Пусть n-угольник разбивается на х треугольников. Тогда соответствующий задаче граф имеет: В = n, Г = х + 1, 2Р = 3 х + n. Подставив данные значения в формулу Эйлера получим: n – х = 2, х = n – 2. Значит n-угольник разбивается на n – 2 треугольника, что и требовалось доказать. На плоскости дано n окружностей так, что любые две из них пересекаются и никакие три не проходят через одну точку. На сколько частей разбивают плоскость эти n окружностей? Решение. Так как всего n окружностей, и каждая пересекается с каждой в двух точках, всего можно составить n(n – 1) окружностей. Значит, число точек пересечения или число вершин графа В = n(n – 1), Р = 2В. По теореме Эйлера Г = Р – В + 2 = 2n 2 – 2n – n 2 + n + 2 = 2 – n + n 2 = n(n – 1) + 2. Ответ. n(n – 1) + 2 частей. Оглавление n –n – 3 х – n + х + 1 = 2, 22 n – х = 1, 22

49 Задача 17 На какое наибольшее число областей разделит плоскость выпуклый n-угольник, пересекающийся с окружностью? Решение. Будем рассматривать окружность, как выпуклый m-угольник, где m > n. Пусть вершины m-угольника и n-угольника и точки их взаимного пересечения являются вершинами графа. Тогда этот граф будет плоским и для него справедлива формула Л. Эйлера: В – Р + Г = 2. Обозначим: вершины m-угольник и n-угольника m + n = B 1 ; число точек пересечения многоугольников – X. Тогда: В = В 1 + Х, 2P = 4X + 2B 1, так как степень каждой вершины многоугольника равна 2, а степень каждой точки пересечения равна 4. Подставим значения В и Р в формулу Эйлера, получим: B 1 + Х – 2Х – B 1 + Г = 2, откуда Г = Х + 2. Значение Г максимально, если максимально значение X. Так как Х 2n (каждая сторона n-угольника пересекает сторону m-угольника не больше, чем в двух точках), то ясно, что значение Г будет максимальным при Х = 2n. Тогда Г = 2n + 2. Ответ. 2n + 2 частей. Оглавление

50 Задача 18 m-угольник расположен в n-угольнике; соединены отрезками всевозможные их вершины и, кроме этих точек, других точек пересечения у этих отрезков нет. На сколько областей разделится при этом плоскость? Решение. В графе, соответствующем задаче, m + n вершин. Если граф полный, то число его рёбер Р = 3(m + n) – 6. Уберём рёбра из внешней области n-угольника (их n – 3), тогда: Р = 3m + 3n – 6 – n + 3 = 2n + 3m – 3. Так как граф плоский, то по теореме Эйлера В – Р + Г = 2. Подставив значения В и Р, получим: m + n – 2n – 3m Г = 2, Г = n + 2m – 1. Ответ. n + 2m – 1 областей. Оглавление

51 Задача 19 Оглавление Семиугольник разбит на выпуклые пяти- и шести- угольники, причём так, что каждая его вершина является вершиной по крайней мере двух многоугольников разбиения. Тогда число пятиугольников разбиения не менее 13. Докажите это. Решение. 1. Обозначим количество пятиугольников через a, шестиугольников через b. Тогда, учитывая внешнюю грань, граф будет иметь Г = a + b + 1 граней. 2. Каждое ребро разделяет 2 грани, значит. При подсчёте получится удвоенное число рёбер 2Р. Так как все грани, кроме внешней пяти- и шести- угольники, а внешняя грань ограничена 7 рёбрами, то получаем: 2Р = 5a + 6b По условию задачи каждая вершина является вершиной по крайней мере двух многоугольников разбиения, тогда из каждой вершины выходят не менее трёх рёбер. Значит 2Р 3В, или В Р (*), где В – число вершин графа. 4. Данный граф плоский, значит для него справедлива формула Эйлера В – Р + Г = 2. Подставим неравенство (*) в формулу Эйлера. Получим: Р – Р + Г 2, –Р + Г 2, Р Г – 2, Р 3Г – 6, или 2Р 6Г – 12 (**). 5. Подставим в последнее неравенство (**) выражения для 2Р и Г (пункты 1, 2). 5a + 6b + 7 6(a + b + 1) – 12, a 13. Значит число пятиугольников разбиения не меньше 13, что и требовалось доказать.

52 Задача 20 На какое наибольшее возможное число областей могут разбить плоскость два пересекающихся выпуклых многоугольника, имеющих соответственно m и n сторон (n m)? Решение. Пусть вершины многоугольников и точки их взаимного пересечения являются вершинами графа. Тогда этот граф будет плоским и для него справедлива формула Л. Эйлера. Установим число вершин и ребер этого графа. В = В 1 + Х, где B 1 = m + n; X число точек пересечения многоугольников. 2P = 4X + 2B 1, так как степень каждой вершины многоугольника равна 2,а степень каждой точки пересечения равна 4. Подставим В и Р в формулу Эйлера, получим: B 1 + Х – 2Х – B 1 + Г = 2, откуда Г = Х + 2. Значение Г максимально, если максимально значение X. Так как Х 2n (каждая сторона n- угольника пересекает сторону m-угольника не больше, чем в двух точках), то ясно, что значение Г будет максимальным при Х = 2n. Тогда Г = 2n + 2. Покажем, что для любых m и n (n m) можно сконструировать такие многоугольники, для которых имеет место соотношение Г = 2n + 2. Проведем произвольную окружность и возьмем на ней m различных точек. Соединив их последовательно, получим вписанный m-угольник. Начиная с какой-нибудь дуги (стягивающей сторону m-угольника), отметим n точек (по одной на дуге), не совпадающих с вершинами m-угольника. Соединив эти точки последовательно, получим вписанный в ту же окружность n-угольник. Устранив окружность, получим искомую ситуацию деления плоскости на 2n + 2 областей. Ответ. 2n + 2 областей. Оглавление

53 Задача 21 На плоскости даны 1000 точек, никакие три из которых не лежат на одной прямой. Будем последовательно соединять точки непересекающимися отрезками до тех пор, пока не останется ни одной пары точек, которые можно было бы соединить непересекающимися отрезками. Каковы границы изменения числа отрезков в зависимости от расположения этих точек на плоскости? Решение. Используя соотношение, полученное в ходе решения задачи 8, имеем (для графа, соответствующего данной задаче): Р = 2n + 3m – 3. По условию m + n = Тогда Р = 3(m + n) – n – 3, откуда Р = 2997 – n. Число n – число сторон многоугольника, поэтому 3 n Максимальное значение Р будет при минимальном значении n (т. е. при n = 3), а минимальное значение Р будет при максимальном значении n (т. е. при n = 1000). Поэтому 1997 Р Ответ Р 2994 – границы изменения числа отрезков. Оглавление

54 Задача 22 На плоскости дано n прямых, из которых никакие две не параллельны и никакие три не проходят через одну точку. а) В скольких точках пересекаются эти прямые? б) Найдите число прямых, если число замкнутых областей равно 21. Решение. а) Т. к. каждая прямая пересекается с остальными n – 1 прямыми, то число точек пересечения будет равным: б) Плоский граф, соответствующий условию задачи имеет: Т. к. каждая прямая пересекается с каждой, т. е. делиться на n частей, и нам нужны только замкнутые области, то у каждой прямой мы не считаем 2 луча, и число рёбер графа равно: Р = n(n – 2) По теореме Эйлера Г = Р – В + 2, т. е. число граней включая внешнюю: Число замкнутых граней: Т. к. по условию таких граней 21, то мы получим уравнение: n 2 – 3n – 40 = 0, n = 8. Ответ. 8 прямых. Оглавление В = n (n – 1) Г = n 2 – 2n – n2n2 + n + 2 = n 2 – 3n n 2 – 3n n 2 – 3n + 2 = 21, 2

55 Задачи 23 и 24 Даны три концентрические окружности и на них взяты соответственно m, n и k точек. Эти точки соединены отрезками (или дугами) так, что других точек пересечения (кроме данных точек) друг с другом они не имеют. На какое максимальное число треугольных областей разобьется эта фигура? Решение. Рассмотрим граф, соответствующий условию задачи. Вершинами данного графа будут все точки, взятые на окружностях; рёбрами – отрезки, их соединяющие, и дуги, на которые точки делят окружности; гранями – полученные треугольники, внешняя и внутренняя грани. Тогда: В = m + n + k, Г = Г Т. к. граф плоский, для него справедливо равенство В – Р + Г = 2. Подставив значения В, Р и Г, получим: 2n + m + k – Г 3 = 0, Г 3 = 2n + m + k. Ответ. Максимальное число треугольных областей 2n + m + k. Внутри треугольника взято m точек, которые соединены друг с другом и вершинами треугольника. Докажите, что число треугольников образующегося графа четное. Решение. Так как в графе, соответствующем данной задаче, все образующиеся и внешняя грани – треугольники, то для него справедливо равенство: 2Р = 3Г, из которого следует, что Г – чётное число, что и требовалось доказать. Оглавление m + n + k – 3 Г 3 – m + k + Г = 2, 22 Р = 3Г 3 + m + k, 2

56 Доказанные утверждения В ходе решения задач были доказаны следующие утверждения 1. Если внутри n-угольника взять m произвольных точек и соединить их друг с другом и вершинами n-угольника так, чтобы, кроме этих точек, не было бы никаких других точек пересечения, то внутренняя область многоугольника разобьется на: 1) n + 2m – 2 треугольника, или 2) n/2 + m – 1 четырёхугольника (причём n должно быть чётным числом). 2. Для того, чтобы m-угольник непересекающимися (кроме как в вершине) диагоналями разделился на k-угольные области, необходимо и достаточно, чтобы m было числом вида n (k – 2) + 2, где n – любое натуральное число. В этом случае число непересекающихся диагоналей будет равно а k-угольных граней Г k будет 3. Два пересекающихся выпуклых n- и m-угольника (n m) могут разбить плоскость самое большое на 2n + 2 областей. 4. n окружностей, каждые две из которых пересекаются и никакие три не проходят через одну точку, разбивают плоскость на n(n – 1) + 2 частей. 5. Выпуклый n-угольник, пересекающийся с окружностью, разделяет плоскость самое большое на 2n + 2 областей. 6. n прямых, из которых никакие две не параллельны и никакие три не проходят через одну точку, пересекаются в n(n – 1)/2 точках. p = m – k, k – 2 Г k = m – 2. k – 2

57 Выводы I. Изучение теоретического материала показало, что: 1. Теория графов имеет широкие направления развития. 2. Для изучения данной темы не требуется специальных предварительных знаний. 3. Теорема Эйлера о плоском графе имеет огромное значение для развития математики в целом и наиболее молодого её направления – топологии. 4. С помощью теоремы Эйлера существенно упрощается решение многих нестандартных задач по математике (олимпиадных задач) II. 1. Составленный комплект дидактического материала с подробным решением математических задач с помощью теоремы Эйлера о плоском графе призван помочь учащимся общеобразовательных и профильных математических классов получить знания и умения в решении задач новыми методами. 2. Слайд-лекция по теме: «Теория графов. Теорема Эйлера» призвана расширить знания всех желающих по перспективному разделу математики «Теория графов» и помочь организовать и проводить работу школьного математического общества. Оглавление

58 Литература 1. Березина Л.Ю. Графы и их применение. – М.: Просвещение, Болл У., Коксетер Г.Математические эссе и развлечения. – М.: Мир, Генкин С.А., Итенберг И.В., Фомин Д.В. Ленинградские математические кружки. – Киров: АСА, Гусев В.А. Внеклассная работа по математике. – М.: Просвещение, Курант Р., Роббинс Т. Что такое математика. Перевод с англ. А.Н. Колмогорова. – М.: МЦНМО, Радемахер Г., Теплиц О. Числа и фигуры. – М.: Наука, Саркисян А.А., Колягин Ю.М. Познакомьтесь с топологией. – М.: Просвещение, Смирнов С.Г. Прогулки по замкнутым поверхностям. (Серия: «Библиотека «Математическое просвещение»» Вып. 27). – М.: МЦНМО, Фарков А.В. Учимся решать олимпиадные задачи. Геометрия. 5–11 классы. – М.: Айрис–пресс, Оглавление