К₅ К₆ К₇

г) д) е)

Рис.10

Подсчитать число ребер полного графа Кn очень просто: каждая вершина должна соединяться с n – 1 вершиной. Число вершин равно n. Следовательно, значение выражения n*(n - 1) будет равно удвоенному числу ребер (так как каждое ребро соединяет две вершины). Поэтому общее число ребер будет равно n(n - 1)/2 – биномиальному коэффициенту (n/2), равному числу ребер и n является квадратичной, следовательно, число ребер Kn будет возрастать очень быстро.

---

Задача 1. В государстве 100 городов, из каждого выходит 2 дороги, кроме столицы, откуда выходит 5 дорог о города Горный, откуда выходит одна единственная дорога. Сколько всего дорог в государстве?

Решение: сложим количество дорог, выходящих из всех городов: 982+5+1=202. Это число – количество концов всех дорог. Поскольку каждая дорога имеет 2 конца, то количество дорог будет вдвое меньше, а именно 101.

Ответ: 101

Задача 2. На остров Коневец завезли 13 телефонов. Настоятель хочет организовать такую схему телефонной связи, чтобы соединить каждый телефон ровно с 7-ю другими. Удастся ли ему это решить?

Решение: Посчитаем, сколько проводов нужно, чтобы осуществить такую схему. Концов проводов будет 137=91, а самих проводов – вдвое меньше, то есть 45,5 штук. Это означает такая схема связи невозможна.
2.4.2. Плоские графы
Определив вершины графа, их можно соединить ребрами так, как показано на рисунке 11.

A

А В

E B



D C D C

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

---

В A B




С

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, не является планарным. Еще один простой пример не планарного графа – это полный граф К₅ в форме пятиугольника с пятиугольной звездой внутри, изображенный на рисунке 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можно изобразить p^p-2 разных деревьев (формула Кэли). Понятие дерева впервые ввел Кэли в 1857 году. Деревья образуют очень важный класс графов, так как в них все вершины соединены минимально возможным числом ребер.

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

«Граф G является деревом тогда и только тогда, когда между любыми двумя различными его вершинами u и vсуществует единственный путь. Это равносильно следующему утверждению: G является связным графом, если он имеетp вершин и p – 1 ребро».

Несмотря на простоту этой теоремы, число возможных деревьев по мере увеличения pвозрастает очень быстро.

Рассмотрим задачу, которую можно решить с помощью деревьев.

Даны n городов А₁, А2,…, А_n . Зная затраты на установление сообщения между каждой парой городов (стоимость строительства дорог, прокладки водо- и газопровода, линий электропередачи, телефонных линий), определите, как можно соединить города самым дешевым способом. Очевидно, что сеть «экономических связей» будет деревом, так как все города должны быть связаны друг с другом и не должно существовать циклов. Если бы в этой сети существовал цикл, можно было бы удалить одно из его ребер и все города по-прежнему были бы соединены между собой, но уже при меньших затратах.

Следовательно, дерево связей между n городами будет иметь n – 1 ребро. Соединим два города, для которых стоимость прокладки всех коммуникаций будет наименьшей. Затем соединим один из них с третьим городом, для которого стоимость коммуникаций будет минимальной, и так далее. Множество различных графов, которые являются деревьями, называется лесом. Вопреки известной пословице, в теории графов за деревьями лес виден.

Задача 5: Сколько четырехбуквенных слов можно составить, используя только буквы А и Б?

Решение: Составим дерево для всех комбинаций четырехбуквенных слов из букв А и Б.

А

Б

А

Б

А

Б

А

Б

А

Б

А

Б

А

Б

А

Б

А

Б

А

Б

А

Б

А

Б

А

Б

А

Б

А

Б

Ответ: 16 слов.
2.2.4. Эйлеровы графы

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

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

Эйлер доказал, что эти условия являются также и достаточными.

Теорема 1. Связный граф, степени всех вершин которого четны, обладает эйлеровой линией.

Доказательство. Предположим, что мы начинаем цепь Z из некоторой вершины А и продолжаем ее настолько далеко, насколько это возможно, проходя каждый раз по ребру, еще не пройденному ранее. Ввиду конечности числа ребер этот процесс когда-нибудь закончится. Но так как в каждой вершине – четное число ребер, то из каждой вершины, за исключением начальной, будет возможен и выход. Следовательно, цепьZ должна кончаться в вершине А.

Если Z проходит через все вершины графа, то мы уже получили требуемую эйлерову линию. Если это не так, найдется вершина В, принадлежащаяZ₁, инциндентная некоторому ребру, не входящему в цепьZ. Так как Zимеет в вершине В четное число ребер, то число ребер, выходящих из В и не принадлежащих Z, также четно; это верно и относительно всех других вершин.

Теперь мы начнем новую цепь К из вершины В, используя на этот раз только ребра, не принадлежащие Z. Ясно, что эта цепь должна оканчиваться в точке В. А тогда мы можем получить больший цикл, начинающийся в А: сначала следуем по Z от А к В, затем пройдем по циклу К и вернувшись в В, пройдем оставшуюся часть Z обратно к точке А. если мы еще не обошли весь граф, мы можем снова расширить этот путь – и так до тех пор, пока мы не получим требуемую эйлерову линию.

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

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






Решение: А

Е В

С – Е – В – Д – Е – А – В – С – Д

Д С

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



Решение: Нельзя нарисовать такую фигуру одним росчерком, так как она имеет четыре нечетных узла.

---

Глава 3. Результаты и их обсуждения

1. 
   Изучив литературу по теме исследования, я составила схему «Виды графов».
   

«Виды графов»

Схема № 1.

Графы



Полные Эйлеровы

Геометрические Плоские Деревья

2. 
   В ходе своего исследования мной было проведено анкетирование среди учащихся 7 – 9 классов для выявления их осведомленности о графах и решении задач с помощью графов. В опросе участвовало 60 обучающихся. Результаты своего анкетирования я занесла в таблицу.
   

№	Вопрос	Кол-во учащихся		%
		Да	Нет	Да	Нет
1	Слышали вы задачу: начертить конвертик, не отрывая карандаша от бумаги и не проводя ни одной линии дважды?	58	2	97	3
2	Смогли вы ее решить?	20	40	33	67
3	Знакомо ли вам понятие граф?	48	12	80	20
4	Надо ли знакомить учащихся с графами?	53	7	88	12

Многим учащимся стало интересно узнать, как можно применить граф к решению задач.

3. 
   На предметной неделе – неделе точных наук – я провела в 8-х классах информационный час «Решаем с помощью графов». Сделала небольшую историческую справку о возникновении графа, привела несколько примеров, показала, как решаются задачи с помощью графов. Далее я предложила ребятам решить самим подобные задачи. Им очень понравились задачи на эйлеровы графы и на составление деревьев.
   
4. 
   Итогом моей работы стало наглядное пособие «Решаем с помощью графов» (См. Приложение 1).
   

---

Заключение

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

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

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

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

Мне было интересно работать над данной темой. Сложность возникла в том, что практически все чертежи приходилось строить самой. Просматривая источники, я встретила задачу части В из ЕГЭ, которая решается методом графов. Но я не стала останавливаться на ней, так как в своей работе большее внимание уделила логическим задачам. Я думаю, что продолжу работать над данной темой, где рассмотрю уже не логические задачи, а практические, например, на движение, на нахождение скорости, пути и времени, и другие, необходимые мне при подготовке к ЕГЭ, которые можно решить с помощью графов.

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


Список используемой литературы

1. 
   О.Оре. Графы и их применение. – М.: Мир, 1965.
   
2. 
   Ф.Харари. Теория графов. – М.: Едиториал УРСС, 2003.
   
3. 
   Мир математики в 40 т. Т.11: Клауди Альсина. Карты метро и нейронные сети. Теория графов. – М.: Де Агостини, 2014.
   
4. 
   М.И.Зайкин. математический тренинг: Развиваем комбинационные способности. – М.: ВЛАДОС, 1996.
   
5. 
   «Математика для школьников» - научно-практический журнал №3, 2011.
   

---

Смотрите также файлы

• Данный вариант состоит из 6 заданий, включающие вопросы с множественным выбором ответов, требующие краткого и развернутого ответов.docx

• Шыыс азастан облысы білім басармасы скемен аласы бойынша білім беру бліміні 6 орта мектебі кмм 5 А сыныбында ткізілетін Отбасы баыт мекені.doc

• Опишите что такое биг дата Для чего можно использовать На какие характеристики разделяют Big Data.docx

• 11сынып аза тілі бжб аза тілі пнінен 4тосан бойынша жиынты баалау тапсырмалары.doc

• Программа среднего профессионального образования 46. 02. 01 Документационное обеспечение управления и архивоведение Дисциплина математика Практическое задание 2.doc