Исследовательская работа по математике по теме _Графы и математи. Городского округа г. Выкса Нижегородской области Графы в математике Физикоматематическое отделение Секция математическая
 Скачать 0.57 Mb.
|
|
2.4. Виды графов 2.4.1.Геометрические и полные графы    Циклы – это очень простые маршруты, проходящие через все вершины, начальная и конечная точка которых совпадают. Примеры циклов представлены на рисунке 8а,б.         Рис.8,а Рис.8,б Подобными графами можно представить маршруты городских автобусов или маршруты патрулей. Число вершин V равно числу рёбер А. Совокупность циклов образует так называемый геометрический граф – плоскую фигуру из вершин (точек плоскости) и рёбер (линий, соединяющих некоторые пары вершин). Область, ограниченная рёбрами и не содержащая внутри себя вершин и рёбер графа, называется гранью. Подсчитать общее число вершин V и число рёбер А несложно. При подсчете числа граней С следует учитывать, что внешняя часть плоскости также образует грань, так как она тоже ограничена циклом из вершин и ребер графа. Таким образом, граф, изображенный на рисунке 9, имеет 10 вершин, 14 ребер и 6 граней.               Рис.9Графы, в которых любая пара вершин соединена ребром, называются полными. На следующих рисунках 10а,б,в,г,д,е приведены полные графы с числом вершин от 2 до 7. Полный граф с n вершинами обозначается Кn.     К2  К3 К4 а) б) в)                                К5 К6 К7 г) д) е) Рис.10 Подсчитать число ребер полного графа Кn очень просто: каждая вершина должна соединяться с n – 1 вершиной. Число вершин равно n. Следовательно, значение выражения n*(n - 1) будет равно удвоенному числу ребер (так как каждое ребро соединяет две вершины). Поэтому общее число ребер будет равно n(n - 1)/2 – биномиальному коэффициенту (n/2), равному числу ребер и n является квадратичной, следовательно, число ребер Kn будет возрастать очень быстро. Задача 1. В государстве 100 городов, из каждого выходит 2 дороги, кроме столицы, откуда выходит 5 дорог о города Горный, откуда выходит одна единственная дорога. Сколько всего дорог в государстве? Решение: сложим количество дорог, выходящих из всех городов: 982+5+1=202. Это число – количество концов всех дорог. Поскольку каждая дорога имеет 2 конца, то количество дорог будет вдвое меньше, а именно 101. Ответ: 101 Задача 2. На остров Коневец завезли 13 телефонов. Настоятель хочет организовать такую схему телефонной связи, чтобы соединить каждый телефон ровно с 7-ю другими. Удастся ли ему это решить? Решение: Посчитаем, сколько проводов нужно, чтобы осуществить такую схему. Концов проводов будет 137=91, а самих проводов – вдвое меньше, то есть 45,5 штук. Это означает такая схема связи невозможна. 2.4.2. Плоские графы Определив вершины графа, их можно соединить ребрами так, как показано на рисунке 11.   A   А В   E B D C D C Рис.11 Однако эти графы можно изобразить иначе: сохранить прежние связи между вершинами, но избежать пересечений ребер в точках, которые не являются вершинами графа, как в двух предыдущих случаях. Новые изображения представлены на рисунке 12:        СD D C Рис.12 Граф называется планарным, если его можно изобразить на плоскости так, что его ребра будут пересекаться в вершинах графа (такое изображение называется плоским графом). Заметим, что для анализа планарности графа нужно определить, существует ли эквивалентный (изоморфный) ему граф, который можно изобразить без ненужных пересечений ребер. Задача о колодцах и враждующих семьях Задача звучит так: в трёх домах a,b,c живут три семьи, враждующие между собой. Рядом с их домами находятся три колодца e,f,g. Один из колодцев всегда полон, два других пусты. Соседи хотят проложить дорожки так, чтобы из каждого дома можно было попасть к каждому колодцу. Никакие две дорожки не должны пересекаться, чтобы каждый мог избежать встреч с соседями. Можно ли проложить девять дорожек таким способом? На рисунке 13,а показана первая попытка соединить дома a,b,c и колодцы e,f,g. Такой граф обозначается К3,3. Получилось множество нежелательных пересечений. На рисунке 13,б тот же граф изображен иначе, но избежать пересечений по-прежнему не удалось. Заметим, что если убрать дорожку от дома b к колодцу g, то можно проложить восемь дорожек без пересечений.         a b c e    a b e f g g f а) c б) Рис.13 Можно ли добавить к этому графу недостающее ребро так, чтобы не пересекать остальные? Будет уместно привести одно интуитивно понятное утверждение (любопытно, что доказать его непросто): если простая плоская замкнутая непрерывная кривая делит плоскость на две части (внешнюю и внутреннюю), то любая непрерывная кривая, соединяющая точку внешней части и точку внутренней части, пересечет данную кривую минимум один раз. Это утверждение носит название теоремы Жордана. Посмотрим снова на рисунок 13 и увидим, что в обоих случаях точка g находится внутри непрерывной замкнутой кривой, а точка b – вне её. Следовательно, задача о колодцах не имеет решения. Единственный способ, которым можно проложить дорожку из дома b к колодцу g - это построить мост, проходящий поверх одной из дорожек. В задаче о колодцах представлен первый пример не планарного графа. Граф, который мы обозначили К3,3, не является планарным. Еще один простой пример не планарного графа – это полный граф К5 в форме пятиугольника с пятиугольной звездой внутри, изображенный на рисунке 14:       Рис.14 Рассмотрим примеры задач. Задача 3. Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Венера; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса? Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.      З Н С   М   П  У ЮВ Марс Ответ: долететь с Земли до Марса нельзя. 2.2.3. Деревья, за которыми виден лес Дерево – это очень простой граф, все вершины которого соединены так, что отсутствуют циклы, как, например, на рисунке 15:    Рис.15 В дереве можно проложить маршрут между любыми двумя вершинами. Последовательность чисел, обозначающих количество всех возможных деревьев для каждого числа вершин, выглядит так: 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159… Если дерево имеет p вершин, то в нем всегда будет p – 1 ребер, но для каждого значения pможно изобразить pp-2 разных деревьев (формула Кэли). Понятие дерева впервые ввел Кэли в 1857 году. Деревья образуют очень важный класс графов, так как в них все вершины соединены минимально возможным числом ребер. Следующая простая и красивая теорема дает характеристику деревьям, а также имеет крайне важное практическое значение: «Граф G является деревом тогда и только тогда, когда между любыми двумя различными его вершинами u и vсуществует единственный путь. Это равносильно следующему утверждению: G является связным графом, если он имеетp вершин и p – 1 ребро». Несмотря на простоту этой теоремы, число возможных деревьев по мере увеличения pвозрастает очень быстро. Рассмотрим задачу, которую можно решить с помощью деревьев. Даны n городов А1, А2,…, Аn . Зная затраты на установление сообщения между каждой парой городов (стоимость строительства дорог, прокладки водо- и газопровода, линий электропередачи, телефонных линий), определите, как можно соединить города самым дешевым способом. Очевидно, что сеть «экономических связей» будет деревом, так как все города должны быть связаны друг с другом и не должно существовать циклов. Если бы в этой сети существовал цикл, можно было бы удалить одно из его ребер и все города по-прежнему были бы соединены между собой, но уже при меньших затратах. Следовательно, дерево связей между n городами будет иметь n – 1 ребро. Соединим два города, для которых стоимость прокладки всех коммуникаций будет наименьшей. Затем соединим один из них с третьим городом, для которого стоимость коммуникаций будет минимальной, и так далее. Множество различных графов, которые являются деревьями, называется лесом. Вопреки известной пословице, в теории графов за деревьями лес виден. Задача 5: Сколько четырехбуквенных слов можно составить, используя только буквы А и Б? Решение: Составим дерево для всех комбинаций четырехбуквенных слов из букв А и Б.
Ответ: 16 слов. 2.2.4. Эйлеровы графы Изложив решение задачи о кёнигсбергских мостах, Эйлер в своей работе перешел к следующей общей проблеме теории графов: на каких графах можно найти цикл, содержащий все ребра графа, причем каждое ребро в точности по одному разу? Такой цикл называется эйлеровой линией, а граф, обладающий эйлеровой линией, - эйлеровым графом. Для того, чтобы граф имел эйлерову линию, он должен быть связным. Как и в задаче о кёнигсбергских мостах, ясно, что каждая эйлерова линия должна входить в каждую вершину и выходить из нее одно и то же число раз, т.е. степени всех вершин графа должны быть четными. Мы получили два необходимых условия для того, чтобы на графе имелась эйлерова линия, - связность и четность степеней всех его вершин. Эйлер доказал, что эти условия являются также и достаточными. Теорема 1. Связный граф, степени всех вершин которого четны, обладает эйлеровой линией. Доказательство. Предположим, что мы начинаем цепь Z из некоторой вершины А и продолжаем ее настолько далеко, насколько это возможно, проходя каждый раз по ребру, еще не пройденному ранее. Ввиду конечности числа ребер этот процесс когда-нибудь закончится. Но так как в каждой вершине – четное число ребер, то из каждой вершины, за исключением начальной, будет возможен и выход. Следовательно, цепьZ должна кончаться в вершине А. Если Z проходит через все вершины графа, то мы уже получили требуемую эйлерову линию. Если это не так, найдется вершина В, принадлежащаяZ1, инциндентная некоторому ребру, не входящему в цепьZ. Так как Zимеет в вершине В четное число ребер, то число ребер, выходящих из В и не принадлежащих Z, также четно; это верно и относительно всех других вершин. Теперь мы начнем новую цепь К из вершины В, используя на этот раз только ребра, не принадлежащие Z. Ясно, что эта цепь должна оканчиваться в точке В. А тогда мы можем получить больший цикл, начинающийся в А: сначала следуем по Z от А к В, затем пройдем по циклу К и вернувшись в В, пройдем оставшуюся часть Z обратно к точке А. если мы еще не обошли весь граф, мы можем снова расширить этот путь – и так до тех пор, пока мы не получим требуемую эйлерову линию. Задачи на проведение эйлеровых линий, т.е. задачи о воспроизведении изображенных линий без повторений и без отрыва карандаша от бумаги, являются излюбленной темой математических развлечений. Задача 6: Начертить фигуру, изображенную на рисунке, не отрывая карандаша от бумаги и не проводя ни одной линии дважды.     Решение: А Е В С – Е – В – Д – Е – А – В – С – Д Д С Задача 7: Можно ли начертить фигуру, изображенную на рисунке, не отрывая карандаша от бумаги и не проводя ни одной линии дважды.        Решение: Нельзя нарисовать такую фигуру одним росчерком, так как она имеет четыре нечетных узла. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
А
Б
А
Б
А
Б
А
Б
А
Б
А
А