Титов Максим

1. Рассмотреть все маршруты Нижнегорского района.

2. По данным маршрутов составить новые маршруты.

3. Показать являются ли новые маршруты Эйлеровыми графами.

4. Построить матрицу смежности для новых маршрутов.

5. Найти кратчайшие расстояния от пгт.Нижнегорского до населенных пунктов.

Скачать:

Предварительный просмотр:

ВВЕДЕНИЕ ……………………………………………………………………………….3

РАЗДЕЛ 1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ ГРАФОВ …………………………………5

1. Основные понятия теории графов......…………………...……...…………5
2. Характеристика Эйлеровых графов …………………………...…………...7
3. Поиск кратчайшего расстояния в графе (Алгоритм Дейкстри)…………..8

РАЗДЕЛ 2. МАРШРУТЫ НИЖНЕГОРСКОГО РАЙОНА ……………………..……10

1. Маршруты Нижнегорского района …..…..……………………………….10
2. Исследование маршрутов Нижнегорского района ……..………………..11

ЗАКЛЮЧЕНИЕ ………………………………………………………………………….17

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ …………………………………….19

ВВЕДЕНИЕ

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

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

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

Цель работы – исследование транспортных путей Нижнегорского района.

Задачи работы:

1 . Рассмотреть все маршруты Нижнегорского района.

2 . По данным маршрутов составить новые маршруты.

3. Показать являются ли новые маршруты Эйлеровыми графами.

4. Построить матрицу смежности для новых маршрутов.

5. Найти кратчайшие расстояния от пгт.Нижнегорского до населенных пунктов.

Объектом исследования является карта транспортных путей Нижнегорского района.

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

Применяемые методы: поиск источников информации, наблюдение, сравнение, анализ, математическое моделирование.

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

При работе использовал ряд литературных источников: специальная литература по теории графов, познавательную литературу, различные научно-популярные, образовательные, специализированные журналы.

РАЗДЕЛ 1

ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ ГРАФОВ

1.1. Основные понятия теории графов

Граф представляет собой непустое множество точек и множество отрезков, оба конца которых принадлежат заданному множеству точек. (Рис.1.1.)

Рис.1.1.

Вершина графа - точка, где могут сходиться/выходить рёбра и/или дуги.

Ребро графа - ребро соединяет две вершины графа.

Степень вершины - количество рёбер, выходящих из вершины графа.

Вершина графа, имеющая нечётную степень, называется нечетной, а чётную степень – чётной.

Если направление связи имеет значение, то линии снабжают стрелками, и в этом случае граф называется ориентированным графом, орграфом. (Рис.1.2.)

Рис.1.2.

Взвешенный граф - граф, каждому ребру которого поставлено в соответствие некое значение (вес ребра). (Рис.1.3.)

Рис. 1.3.

Графы, в которых построены все возможные ребра, называются полными графами. (Рис.1.4.)

Рис. 1.4.

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

Матрица смежности – это матрица, элемент M[i] [j] которой равен 1, если существует ребро из вершины i в вершину j, и равен 0, если такого ребра нет (Рис.1.5. для графа на рис.1.1).

1.2. Характеристика Эйлеровых графов

Граф, который можно нарисовать, не отрывая карандаша от бумаги, называется эйлеровым. (рис.1.6.)

Такими графы названы в честь учёного Леонарда Эйлера.

Закономерность 1.

Невозможно начертить граф с нечетным числом нечетных вершин.
Закономерность 2.

Если все вершины графа четные, то можно не отрывая карандаш от бумаги («одним росчерком»), проводя по каждому ребру только один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине.
Закономерность 3.

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

Граф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком».
Фигура (граф), которую можно начертить, не отрывая карандаш от бумаги, называется уникурсальной.

Рис.1.6.

1.3. Поиск кратчайшего расстояния в графе (Алгоритм Дейкстри)

Задача: задана сеть дорог между городами, часть которых могут иметь одностороннее движение. Найти кратчайшие расстояния от заданного города до всех остальных городов (рис.1.7).

Та же задача: дан связный граф с N вершинами, веса ребер заданы матрицей W. Найти кратчайшие расстояния от заданной вершины до всех остальных.

Алгоритм Дейкстры (E.W. Dijkstra, 1959):

1. Присвоить всем вершинам метку ∞.

2. Среди нерассмотренных вершин найти вершину j с наименьшей меткой.

3. Для каждой необработанной вершины i: если путь к вершине i через вершину j меньше существующей метки, заменить метку на новое расстояние.

4. Если остались необработанны вершины, перейти к шагу 2.

5. Метка = минимальное расстояние.

Рис.1.7.

Рис.1.8. Решение задачи

РАЗДЕЛ 2

МАРШРУТЫ НИЖНЕГОРСКОГО РАЙОНА

2.1. Маршруты Нижнегорского района

Нижнегорский район находится в степной части на севере АР Крым. В состав Нижнегорского района входят пгт.Нижнегорский и 59 населенных пунктов.

Через Нижнегорский район проходят две трассы: 2Р58 и 2Р64. Существуют 8 маршрутов, следующие от А/С Нижнегорская до других населенных пунктов. В своей работе я буду рассматривать эти маршруты:

1 маршрут «Нижнегорск – Красногвардейск». Следует через: Нижнегорск – Плодовое – Митофановка – Буревестник – Владиславовка.

2 маршрут «Нижнегорск - Изобильное»: Нижнегорск – Семенное – Кирсановка – Лиственное – Охотское – Цветущее – Емельяновка – Изобильное.

3 маршрут «Нижнегорск - Великоселье»: Нижнегорк – Семенное – Двуречье – Акимовка – Лужки – Заливное – Степановка – Луговое – Чкалово – Великоселье.

4 маршрут «Нижнегорск – Белогорск (трасса 2Р64)»: Нижнегорск – Желябовка – Ивановка – Заречье – Серово – Садовое – Пены.

5 маршрут «Нижнегорск - Уваровка»: Нижнегорск – Семенное – Новоивановка – Уварвка.

6 маршрут «Нижнегорск - Любимовка»: Нижнегорск – Семенное – Двуречье – Акимовка – Лужки – Заливное – Степановка – Луговое – Коворово – Дворовое – Любимовка.

7 маршрут «Нижнегорск - Пшеничное»: Нижнегорск – Семенное – Двуречье – Акимовка – Лужки – Заливное – Степановка – Луговое – Коворово – Дворовое – Сливянка – Пшеничное.

8 маршрут «Нижнегорск – Зоркино (траса 2Р58)»: Нижнегорск – Разливы – Михайловка – Кунцево – Зоркино.

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

Маршруты «Нижнегорск - Уваровка» «Нижнегорск - Любимовка» «Нижнегорск - Пшеничное» изменить нельзя, так как по пути их следования, автобусы заезжают во все населенные пункты, поэтому эти маршруты я рассматривать не буду.

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

2.2. Исследование маршрутов Нижнегорского района

1 маршрут: Нижнегорск – Красногвардейск.

Нижнегорск – 1

Плодовое – 2

Митрофановка – 3

Червоное – 6

Буревестник – 4

Новогригорьевка – 7

Владиславовка – 5

Не заезжает в пункт 6, 7. Добавим в маршрут эти населенные пункты.

Рис.2.1.

Граф не является Эйлеровым. Новый маршрут выглядит так: Нижнегорск – Плодовое – Митрофановка – Буревестник – Новогригорьевка – Владиславовка. Добавилось село Новогригорьевка.

2 маршрут: Нижнегорск – Изобильное.

Нижнегорск – 1

Семенное – 2

Кирсановка – 3

Лиственное – 4

Охотское – 5

Цветущее – 6

Емельяновка – 7

Изобильное – 8

Кулички – 9

Родники - 10

Не заезжает в пункт 9,10. Добавим в маршрут эти населенные пункты.

Рис.2.2.

Граф не является Эйлеровым и связным, поэтому нельзя построить новый маршрут. Маршрут остается тот же.

3 маршрут: Нижнегорск - Великоселье

Нижнегорск – 1

Семенное – 2

Двуречье – 3

Акимовка – 4

Лужки – 5

Заливное – 6

Степановка – 7

Луговое – 8

Чкалово – 9

Великоселье – 10

Широкое - 11

Не заезжает в пункт 11. Добавим в маршрут этот населенный пункт.

Рис.2.3.

Граф не является Эйлеровым. Маршрут остается тот же.

4 маршрут: Нижнегорск - Белогорск (Трасса 2Р64)

Нижнегорск – 1 Косточковка - 12

Желябовка – 2 Фрунзе - 13

Ивановка – 3 Приречное - 14

Заречье – 4 Жемчужина - 15

Серово – 5

Садовое – 6

Пены – 7

Ломоносово – 8

Кукурузное – 9

Тамбовка – 10

Тарасовка - 11

Не заезжает в пункты 8-18. Добавим в маршрут эти населенные пункты.

Рис.2.4.

Граф не является Эйлеровым. Новый маршрут выглядит так: Нижнегорск – Желябовка – Ивановка – Заречье – Тамбовка – Тарсовка – Приречное – Жемчужина – Пены.

5 маршрут: Нижнегорск - Зоркино (Трасса 2Р58)

Нижнегорск – 1

Разливы – 2

Михайловка – 3

Кунцево – 4

Зоркино – 5

Уютное – 6

Нижинское – 7

Не заезжает в пункт 6,7. Добавим в маршрут эти населенные пункты.

Рис.2.5.

Граф не является Эйлеровым и связным, поэтому маршрут остается тот же.

ЗАКЛЮЧЕНИЕ

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

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

В процессе исследования была проделана следующая работа:

1. Проанализирована и проработана литература по теме исследования.

2. Рассмотрены и изучены различные виды фракталов.

3. Представлена классификация фракталов.

4. Собрана коллекция фрактальных образов для первичного ознакомления с миром фракталов.

5. Составлены программы для построения графического образа фракталов.

Лично для меня изучение темы «Неисчерпаемое богатство фрактальной геометрии» оказалось очень интересной и необычной. В процессе исследования я сам для себя сделал массу новых открытий, связанных не только с темой проекта, но и с окружающим миров в целом. Я испытываю огромный интерес к этой теме, и поэтому данная работа оказала исключительно положительное влияние на мое представление о современной науке.

Закончив свой проект, я могу сказать, что всё из того, что было задумано, удалось. В следующем году я продолжу работу над темой «фракталы», так как это тема очень интересна и многогранна. Думаю, что я решил проблему своего проекта, так как мной были достигнуты все поставленные цели. Работа над проектом показала мне то, что математика – это не только точная, но и красивая наука.

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. В.М. Бондарев, В.И. Рублинецкий, Е.Г. Качко. Основы программирования, 1998 г.

2. Н. Кристофидес. Теория графов: алгоритмический подход, Мир, 1978 г.

3. Ф.А. Новиков. Дискретная математика для программистов, Питер, 2001 г.

4. В.А. Носов. Комбинаторика и теория графов, МГТУ, 1999 г.

5. О. Оре. Теория графов, Наука, 1982 г.

Содержание:

I. Введение……………………………………………………………………2

II. Основная часть.

1.История возникновения теории графов…………………………………….4

2.Основные понятия теории графов…………………………………………..5

3.Некоторые задачи теории графов…………………………………………...6

3.1 Задачи о вычерчивании фигур одним росчерком………………………..8

3.2 Задачи с лабиринтами……………………………………………………..10

3.3 Логические задачи…………………………………………………………12

4.Применение теории графов в различных сферах деятельности…………..15

4.1.Графы и история……………………………………………………………17

4.2.Графы и химия……………………………………………………………...18

4.3. Графы и физика…………………………………………………………….19

III . Заключение………………………………………………………………..20

IV . Список литературы………………………………………………………21

Приложение 1………………………………………………………………….22

Приложение 2………………………………………………………………….25

Приложение 3…………………………………………………………………..26

I Введение

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

В этом году я был участником дистанционной олимпиады по математике. В ней была предложена такая задача:

«Почтальон Печкин разнёс почту во все дома деревни, после чего зашёл к дяде Фёдору выпить молока. На рисунке показаны все тропинки, которые проходил Печкин, причём как оказалось, ни одной из них он не проходил дважды. Каким маршрутом шёл почтальон Печкин? В каком доме живёт дядя Фёдор?»

Разбирая решение этой задачи, я задался вопросом: «Можно ли решить эти задачи не перебором, а другим, более быстрым, способом?»

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

Цель:

показать применение теории графов для решения различных видов задач.

Задачи:

Изучить элементы теории графов.

Разобрать решение различных видов задач.

Узнать о применении графов в науке и в различных сферах деятельности.

Методы исследования:

Поиск и анализ информации в литературе.

Поиск и изучение информации в интернет – ресурсах.

Моделирование.

II Основная часть

1. История возникновения теории графов.

Датой рождения теории графов принято считать 1736 год, когда Леонард Эйлер решил задачу о кенигсбергских мостах (Приложение 1.) .

Р
укава реки Прегель, на берегу которой расположен город Кенигсберг, образовывали два острова. В эту эпоху четыре образовавшихся участка суши (правый и левый берег и два острова) соединяло семь мостов так, как это показано на рисунке. Горожане, гуляя по городу, пытались составить маршрут, чтобы он проходил по каждому мосту ровно один раз. Это им не удавалось, а Эйлер доказал, что это принципиально невозможно.

Термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг. Широкое развитие теория графов получила в 50-х годах 20 века в связи со становлением кибернетики и развитием вычислительной техники.

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

2. Основные понятия теории графов.

В математике определение графа дается так: «графом называется конечное множество точек, некоторые из которых соединены линиями. Точки называются вершинами графа, а соединяющие линии – рёбрами».

Схема графа, состоящая из «изолированных» вершин, называется нулевым графом. (рис.2)

Графы, в которых не построены все возможные ребра, называются неполными графами. (рис.3)

Графы, в которых построены все возможные ребра, называются полными графами. (рис.4)

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

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

На рисунке 5 изображен граф с пятью вершинами. Степень вершины А обозначим Ст.А.

На рисунке 5: Ст.А = 1, Ст.Б = 2, Ст.В = 3, Ст.Г= 2, Ст.Д= 0.

рис.5

3. Некоторые задачи теории графов.

Эйлеров путь - путь в графе, проходящий через каждое ребро ровно один раз.

Граф, который можно нарисовать, не отрывая карандаша от бумаги, называется эйлеровым. (рис.6) Такими графы названы в честь учёного Леонарда Эйлера.

рис.6 (эйлеровы графы)

Закономерность 1 .

Если все вершины графа четные, то можно не отрывая карандаш от бумаги («одним росчерком»), проводя по каждому ребру только один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине.
Закономерность 2.

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

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

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

Алгоритм решения

Из предыдущих рассуждений мы получаем общий прием решения каждой подобной задачи о мостах:

преобразовать рисунок в граф (определить его вершины и рёбра);

определить степень каждой вершины;

сделать выводы:

а) заданный обход возможен, если

Все вершины чётные (его можно начать с любой вершины);

Две вершины нечётные (его нужно начать с одной из нечётных вершин);

б) заданный обход невозможен, если нечётных вершин больше двух;

указать начало и конец пути.

Я, изучив эти выводы, решил проверить их на примерах задач из раздела теории графов.

3.1. Решение задач о вычерчивании фигур одним росчерком

Задача №1 (О кенигсбергских мостах).

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

Решение.

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

Задача №2.

Можно ли нарисовать графы, изображенные на рисунках, не отрывая карандаш от бумаги и проводя каждое ребро ровно один раз?

Решение:

Можно, т. к. только 2 нечетные вершины.

Нельзя, т. к. 4 нечетные вершины.

Задача №3.

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

Решение. Да, потому что в данном случае мы имеем дело с вершинами четного порядка.

Задача №4. (Муха в банке).

Муха забралась в банку из-под сахара. Банка имеет форму куба. Сможет ли муха последовательно обойти все 12 ребер куба, не проходя дважды по одному ребру? Подпрыгивать и перелетать с места на место не разрешается.

Решение.

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

Задача №5. (Путь Печкина)

Решение. Нечётных вершин в условии задачи две – почта и дом, поэтому начинаться и заканчиваться маршрут может только в этих узлах. Почтальон Печкин начинает разнос писем с почты, поэтому его маршрут может заканчиваться в доме 5, там и живёт дядя Фёдор. Например, маршрут может быть таким: почта-1-3-2-1-7-почта-3-4-5-7-6-5.

1. 1. Задачи с лабиринтами

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

Происхождение задач о лабиринтах относится к глубокой древности и теряется во мраке времен. Слово «лабиринт» (греческое) означает «ходы в подземельях». Решению задачи о лабиринтах предпосылаются исторические справки – чтобы показать интерес к этой задаче и дать наглядное представление о существовавших и существующих лабиринтах.

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

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

Решение (т.е. маршрут, ведущий к цели) каждого лабиринта может быть найдено одним их трех сравнительно простых методов.

Первый метод – МЕТОД ПРОБ И ОШИБОК. Выбирайте любой путь, а если он заведет вас в тупик, то возвращайтесь назад и начинайте все сначала.

Второй метод – МЕТОД ЗАЧЕРКИВАНИЯ ТУПИКОВ. Начнем последовательно зачеркивать тупики, т.е. маршруты, не имеющие ответвлений и заканчивающиеся перегородкой. Незачеркнутая часть коридоров будет выходом или маршрутом от входа к выходу или к центру.

Третий метод – ПРАВИЛО ОДНОЙ РУКИ. Оно состоит в том, что по лабиринту надо двигаться, не отрывая одной руки (правой или левой) от стены.

Рассмотрим задачу общего вида:

М
ожно ли обойти все данные комнаты, пройдя через каждую дверь ровно один раз и выйти на улицу через комнату 1 или 10? С какой комнаты надо начинать?

Решение:

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

3.3 Логические задачи

Задача №1.

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

Решение:

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

Задача №2.

В
деревне 10 домов, и из каждого выходит по 7 тропинок, идущих к другим домам. Сколько всего тропинок приходит между домами?

Решение.

Пусть дома- вершины графа, тропинки- рёбра. По условию из каждого дома (вершины) выходит 7 тропинок (рёбер), тогда степень каждой вершины 7, сумма степеней вершин 7×10=70, а число рёбер 70: 2= 35. Таким образом, между домами проходит 35 тропинок.

Ответ. 35 тропинок

Задача №3.

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

По вечерам Андрей и токарь играют в домино против Сергея и электрика.

Определите профессию каждого из друзей.

Решение.

Составим граф из 4 друзей и 4 профессий. Пунктирными линиями отметим невозможные связи, а сплошной - соответствие имени и профессии. Если от каждой вершины выходить 3 пунктирных линии, то четвертая линия должна быть сплошной.

В С Н А

Ш С Т Э

Задача №4.

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

Петренко и Гришин никогда не держали в руках малярной кисти.

Иванов и Гришин собираются посетить мельницу, на которой работает их товарищ. Петренко и Капустин живут в одном доме с почтальоном.

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

Гришин и Капустин по субботам обязательно встречаются в парикмахерской, где работает их друг. Почтальон предпочитает бриться сам. Кто есть кто?

Решение.

Иванов Петренко Сидорчук Гришин Капустин

маляр мельник плотник почтальон парикмахер

4.Применение теории графов в различных сферах деятельности.

Ч

ем больше я изучал теорию графов, тем больше поражалась разнообразию применения этой теории.

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

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

Теория графов сейчас одна из самых развиваемых частей математики, так как современная жизнь требует появление новых профессий. Одна из них – специалист по логистике . (Приложение 3.) Менеджер по логистике занимается доставкой товаров, грузов, планирует транспортные маршруты, рассчитывает стоимость перевозок, организует хранение товаров, грузов и т.д. Одна из главных задач специалиста по логистике - анализ ситуации, поэтому он должен уметь хорошо считать, владеть теорией графов.

Инженер чертит схемы электрических цепей.

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

Историк прослеживает родословные связи по генеалогическому дереву.

Военачальник наносит на карту сеть коммуникаций, по которым из тыла к передовым частям доставляется подкрепление.

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

Графы применяются в различных отраслях науки. В последние десятилетия теория графов находит все новые области применения (физика, химия, генетика, психология, социология, экономика, лингвистика, электроника, теория планирования и управления). Именно запросы практики способствуют интенсивному развитию теории графов.

4.1.Графы и история .

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

Генеалогическое дерево А.С. Пушкина.

Моё генеалогическое дерево

4.1.Графы и химия .

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

При графическом изображении формул веществ указывается последовательность расположения атомов в молекуле с помощью, так называемых валентных штрихов (термин «валентный штрих» предложил в 1858 г. А. Купер для обозначения химических сил сцепления атомов), иначе называемых валентной чертой (каждая валентная черта, или валентный штрих, эквивалентны одной паре электронов в ковалентных соединениях или одному электрону, участвующему в образовании ионной связи).

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

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

М
олекулярные графы и деревья: а, б - мультиграфы этилена и формальдегида; в-молекулы изомеров пентана.

4.3.Графы и физика

Е

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

Печатной схемой называют пластинку из какого-либо диэлектрика (изолирующего материала), на которой в виде металлических полосок.

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

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

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

III Заключение.

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

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

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

IV . Литература.

1. Альхова З.Н., Макеева А.В. Внеклассная работа по математике. – Саратов: «Лицей», 2002 г.

2. Перельман Я.И. Одним росчерком. – Ленинград, 1940

3. Башмаков М. И. Математика в кармане «Кенгуру». - М.: Дрофа, 2010г.

4. Игнатьев Е. И. Математическая смекалка. - М.: «Омега», 1994г.

5. Подготовка школьников к олимпиадам по математике. 5-6 классы./сост. Григорьева Г.И. – М. : «Глобус», 2009 г.

Приложение 1.

Леонард Эйлер и мосты Кёнигсберга

Леонард Эйлер родился в швейцарском городе Базеле, где в 15 лет окончил университет, а в 17 лет получил степень магистра. Во время обучения в университете Эйлер брал уроки у одного из самых известных математиков того времени Иоганна Бернулли и подружился с его сыновьями Даниилом и Николаем, которые были приглашены для работы в только что созданную Петербургскую академию наук. Через год по их рекомендации туда же был приглашен и двадцатилетний Эйлер. Этот выбор оказался одним из самых удачных для России. Нет такой области математики, где Эйлер не сказал своего слова. Работал он сутками напролет в любой обстановке, опубликовал примерно 850 работ. Он легко обнаруживал новые задачи и методы их решения. Даже историю возникновения теории графов можно проследить по переписке великого ученого.

Вот перевод латинского текста, который взят из письма Эйлера к итальянскому математику и инженеру Маринони, отправленного из Петербурга 13 марта 1736 года:

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

В своём письме к Маринони Эйлер подробно описал ход своих рассуждений:

"Кенигсбергские же мосты расположены так, что их можно представить на рисунке, где A обозначает остров, а B, C и D – части континента, отделенные друг от друга рукавами реки. Семь мостов обозначены буквами a, b, c, d, e, f, g ".

Так можно ли обойти все Кенигсбергские мосты, проходя только один раз через каждый из этих мостов?

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

Поэтому, чтобы найти ответ, продолжим письмо Эйлера и посмотрим, какое же правило он нашел. Итак,

"Вопрос состоит в том, чтобы определить, можно ли обойти все эти семь мостов, проходя через каждый только однажды, или нельзя. Мое правило приводит к следующему решению этого вопроса. Прежде всего, нужно смотреть, сколько есть участков, разделенных водой, – таких, у которых нет другого перехода с одного на другой, кроме как через мост. В данном примере таких участков четыре – A, B, C, D."

Ход решения задачи будем представлять в виде графа , где вершины – острова и берега, а ребра – мосты.

"Далее нужно различать, является ли число мостов, ведущих к этим отдельным участкам, четным или нечетным. Так, в нашем случае к участку A ведут пять мостов, а к остальным – по три моста".

То есть нам нужно определить степень каждой вершины (количество рёбер, сходящихся в вершине) и узнать, какие вершины четные , а какие нечетные . Подпишем степени вершин в кружочках. И посчитаем количество нечетных вершин. Нечетные вершины: А, B, C, D.

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

Приложение 2

Разные задачи на вычерчивание одним росчерком

Приложение 3

Профессия логист

О
писание профессии:

Это специалист, который координирует движение товаров на пути от производства до точек реализации.

Название профессии происходит от английского слова logistics - снабжение, материально-техническое обеспечение.

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

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

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

Например, завезли слишком много какого-то товара - он попусту загромождает складские помещения и может прийти в негодность. А какой-нибудь другой товар, который следует привезти к вполне определенному сроку (например, елки к Новому году или цветы к 8 Марта), из-за неправильно оформленных сопроводительных документов застрянет на таможенном складе и поступит в продажу слишком поздно, когда уже окажется никому не нужен.

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

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

Кучин Анатолий Николаевич

Руководитель проекта:

Куклина Татьяна Ивановна

Учреждение:

МБОУ "Основная общеобразовательная школа" п. Троицко-Печорск Респ. Коми

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

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

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

Введение
Глава 1. Знакомимся с графами
1.1. История графов.
1.2. Виды графов
Глава 2. Возможности применения теории графов в различных областях повседневной жизни
2.1. Применение графов в различных областях жизни людей
2.2. Применение графов при решении задач
2.3. Генеалогическое древо – один из способов применения теории графов
2.4. Описание исследования и составление генеалогического древа моей семьи
Заключение
Использованная литература
Приложения

«В математике следует помнить не формулы,
а процесс мышления».
Е.И. Игнатьева

Введение

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

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

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

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

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

Объектом исследования является математические графы.

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

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

Для реализации поставленной цели, мною были выдвинуты следующие задачи:

1. познакомиться с историей теории графов;
2. изучить основные понятия теории графов и виды графов;
3. рассмотреть способы решения задач с помощью графов;
4. показать применение теории графов в различных областях жизни человека;
5. создать генеалогическое древо моей семьи.

Методы: наблюдение, поиск, отбор, анализ, исследование.

Исследование:
1. были изучены ресурсы сети Интернет и печатные издания;
2. выписаны области науки и жизнедеятельности человека, в которых используется метод графов;
3. рассмотрено решение задач с помощью теории графов;
4. изучена методика составления генеалогического древа моей семьи.

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

Чтобы убедится в этом, мной и руководителем было предложено учащимся 5-9 классов, участникам школьного и муниципального туров Всероссийской олимпиады школьников, 4 задачи, при решении которых можно применить теорию графов (Приложение 1 ).

Результаты решения задач таковы:
Всего 15 учащихся (5 класс – 3 ученика, 6 класс - 2 ученика, 7 класс – 3 ученика, 8 класс - 3 ученика, 9 класс - 4 ученика) применили теорию графов в 1 задаче – 1, во 2 задаче – 0, в 3 задаче – 6, в 4 задаче – 4 учащихся.

Практическая значимость исследования заключается в том, что результаты несомненно вызовут интерес у многих людей. Разве не пытался кто-то из вас построить генеалогическое дерево своей семьи? А как это сделать грамотно?
Оказывается они решаются при помощи графов легко.

Российская научно-социальная программа для молодежи и школьников

«Шаг в будущее»

ХV Районная научно-практическая конференция «Шаг в будущее»

Графы и их применение

Исследовательская работа

МБОУ «Шелеховский лицей», 10 класс

Руководитель: Копылова Н.П.

МБОУ «Шелеховский лицей»,

учитель математики.

Научный руководитель:

Постников Иван Викторович,

младший научный сотрудник

Института систем энергетики им. Л.А. Мелентьева

Сибирского отделения Российской академии наук

г. Шелехов - 2012

Введение, задачи, цель…………………………………………………………… 3

Основная часть……………………………………………………………………. 4

Заключение……………………………………………………………………..... 10

Список литературы…………………………………………………………….... 11

Введение.

Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов. Толчок к развитию теория графов получила на рубеже XIX и XX столетий, когда резко возросло число работ в области топологии и комбинаторики, с которыми её связывают самые тесные узы родства. Как отдельная математическая дисциплина теория графов была впервые представлена в работе венгерского математика Кёнинга в 30-е годы XX столетия.

В последнее время графы и связанные с ними методы исследований пронизывают на разных уровнях едва ли не всю современную математику. Графы используются в теории планирования и управления, теории расписаний, социологии, математической лингвистике, экономике, биологии, медицине. Как более жизненный пример можно взять использование графов в геоинформационных системах. Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередачи и т. п. - как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут. Теория графов быстро развивается, находит всё новые приложения и ждёт молодых исследователей.

Дать определение графов и его составляющих

Рассмотреть некоторые виды графов и их свойства

Рассмотреть основные положения теории графов, а также теоремы, лежащие в основе данной теории с доказательством

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

Определить области применения теории графов в окружающей действительности

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

Основная часть.

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

Точки иначе называют вершинами, отрезки – рёбрами графа.

Виды графов:

В общем смысле граф представляется как множество вершин, соединённых рёбрами. Графы бывают полными и неполными. Полный граф - это простой граф, каждая пара различных вершин которого смежна. Неполный граф – это граф, в котором хотя бы 2 вершины не смежны.

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

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

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

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

С вершинами графов связаны 4 теоремы, докажем их с помощью задач:

№1.Участники пионерского слёта, познакомившись, обменялись конвертами с адресами. Докажите, что:

1) всего было передано четное число конвертов;

2)число участников, обменявшихся конвертами нечетное число раз, четное.

Решение. Обозначим участников слёта А 1 , А 2 , А 3 …., А n – вершины графа, а ребра соединяют на рисунке пары вершин, изображающих ребят, которые обменялись конвертами:

1) Степень каждой вершины А j показывает количество конвертов, переданных участником А j своим знакомым, значит общее число переданных конвертов N равно сумме степеней всех вершин графа. N = степ. А 1 + степ. А 2 + … + степ. А n-1 + степ. А n , N = 2р (р – число ребер графа), то есть N – четное число. Из этого следует, что было передано четное число конвертов;

2) Мы доказали, что N – четное, а N = степ. А 1 + степ. А 2 + …. + степ. А n-1 + степ. А n , т.е N – количество участников. Мы знаем, что сумма нечетных слагаемых должна быть четной, а это возможно только в том случае, если число нечетных слагаемых четно. Значит, что число участников, которые обменялись конвертами нечетное число раз, четное.

В ходе решения задачи доказаны две теоремы.

В графе сумма степеней всех его вершин – число чётное, равное удвоенному числу рёбер графа. ∑ степ. А j = степ. А 1 + степ. А 2 + … + степ. А n = 2р, где р – число ребер графа Г, n – число его вершин.

Число нечётных вершин любого графа чётно.

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

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

Каждая вершина графа с девятью вершинами может иметь степень, равную 0, 1, 2, …, 7, 8. Предположим, что существует граф Г, все вершины которого имеют разную степень, т. е. каждое из чисел последовательности 0, 1, 2, …, 7, 8 является степенью одной и только одной из его вершин. Но этого не может быть. Действительно, если в графе есть вершина А со степенью 0, то в нем не найдется вершина В со степенью 8, так как эта вершина В должна быть соединена ребрами со всеми остальными вершинами графа, в том числе и с А. Иначе говоря, в графе с девятью вершинами не могут быть одновременно вершины степени 0 и 8. Следовательно, найдутся хотя бы две вершины, степени которых раны между собой.

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

Решение этой задачи почти дословно повторяется в ходе доказательства следующей теоремы (только число 9 приходится заменить произвольным натуральным числом n ≥ 2).

Во всяком графе с n вершинами, где n ≥ 2, всегда найдутся по меньшей мере две вершины с одинаковыми степенями.

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

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

В общем случае у графа с девятью вершинами степень каждой вершины может принимать одно из девяти значений: 0, 1, …, 7, 8. Но у такого графа степени вершин принимают только восемь разных значений, т.к. ровно две вершины имеют одинаковую степень. Следовательно, обязательно либо 0, либо 8 будет значением степени одной из вершин.

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

Допустим, что все же найдется граф с девятью вершинами, в котором ровно две вершины изолированные, а все остальные имеют разные между собой степени. Тогда, если не рассматривать эти две изолированные вершины, останется граф с семью вершинами, степени которых не совпадают. Но такого графа не существует (теорема 3). Значит это предположение неверное.

Теперь допустим, что существует граф с девятью вершинами, в котором ровно две вершины имеют степень 8, а все остальные несовпадающие степени. Тогда в дополнении данного графа ровно две вершины будут иметь степень 0, а остальные попарно различные степени. Этого тоже не может быть (теорема 3), т. е. и второе предположение неверное.

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

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

При решении этой задачи число 9 можно было заменить любым другим натуральным числом n › 2.

Из этой задачи можно вывести следующую теорему:

Если в графе с n вершинами (n 2) в точности две вершины имеют одинаковую степень, то в этом графе всегда найдётся либо в точности одна вершина степени 0, либо в точности одна вершина степени n-1.

Эйлеров путь в графе - это путь, проходящий по всем рёбрам графа и притом только по одному разу.

№4. Как вы помните, охотник за мертвыми душами Павел Иванович Чичиков побывал у известных вам помещиков по одному разу у каждого. Он посещал их в следующем порядке: Манилова, Коробочку, Ноздрева, Собакевича, Плюшкина, Тентетникова, генерала Бетрищева, Петуха, Констанжогло, полковника Кошкарева. Найдена схема, на которой Чичиков набросал взаимное расположение имений и проселочных дорог, соединяющих их. Установите, какое имение кому принадлежит, если ни по одной из дорог Чичиков не проезжал более одного раза.

Решение. По схеме видно, что путешествие Чичиков начал с имения Е, а кончил имением О. Замечаем, что в имения В и С ведут только по две дороги, поэтому по этим дорогам Чичиков должен был проехать. Отметим их жирной линией. Определены участки маршрута, проходящие через А: АС и АВ. По дорогам АЕ, АК и АМ Чичиков не ездил. Перечеркнем их. Отметим жирной линией ЕD; перечеркнем DК. Перечеркнем МО и МН; отметим жирной линией МF; перечеркнем FO; отметим жирной линией FH, HK и КО. Найдем единственно возможный при данном условии маршрут.

Подведем первый итог: задача решена в ходе преобразования картинки. С рисунка остается только считать ответ: имение Е принадлежит Манилову, D – Коробочке, С – Ноздреву, А – Собакевичу, В – Плюшкину, М – Тентетникову, F – Бетрищеву, H – Петуху, K – Констанжогло, O - Кошкареву.

№5. У Ирины 5 подруг: Вера, Зоя, Марина, Полина и Светлана. Она решила двух из них пригласить в кино. Укажите все возможные варианты выбора подруг. Какова вероятность, что Ирина пойдёт в кино с Верой и Полиной?

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

Некоторые варианты повторяются, и их можно исключить. Перечеркнем повторяющиеся ребра. Осталось 10 возможных вариантов, значит вероятность того, что Ирина пойдёт в кино с Верой и Полиной равна 0,1.

Представление о плоском графе

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

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

Плоский граф Плоское представление графа

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

При изучении плоского представления графа вводится понятие грани.

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

Рисунок

Грани () и () являются соседями, а грани () и () соседями не являются.

Ребро () является мостом, соединяющим циклы - перегородкой.

Простой цикл, ограничивающий грань - граница грани.

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

Всякое представление графа либо не имеет бесконечной грани,

либо имеет только одну.

В плоском представлении дерева или леса бесконечной гранью является вся плоскость рисунка.

Формула Эйлера

Для всякого плоского представления связного плоского графа без перегородок число вершин (в), число ребер (р), и число граней с учетом бесконечной (г) связаны соотношением: в – р + г =2.

Предположим, что граф А –связный плоский граф без перегородок. Для его плоского произвольного представления определим алгебраическое значение суммы в – р + г. Затем, данный граф преобразуем в дерево, которое содержит все его вершины. Для этого удалим некоторые ребра графа, разрывая при этом поочередно все его простые циклы, но так, чтобы граф остался связным и без перегородок. Обратим внимание, что при данном удалении одного ребра уменьшается число граней на 1, т.к. при этом либо 2 цикла преобразуются в 1, либо один простой цикл просто пропадает. Из этого следует, что значение разности р – г при этом удалении остается неизменным. Те ребра, которые мы удаляем, выделены пунктиром.

В получившемся дереве число вершин обозначим – вд, ребер – рд, граней – гд. Отматим равенство р – г = рд – гд. В дереве одна грань, значит р – г = рд – 1. Изначально мы задали условие, что при удалении ребер число вершин не меняется, т.е. в = вд. Для дерева справедливо равенство вд – рд = 1. Отсюда следует рд = в – 1, т.е р – г = в – 2 или в – р + г = 2. Формула Эйлера - доказана.

Кёнигсберг

Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам (через реку Преголя), не проходя ни по одному из них дважды? Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически, во время прогулок. Но никому это не удавалось, однако не удавалось и доказать, что это даже теоретически невозможно.

На упрощённой схеме части города (графе) мостам соответствуют линии (дуги графа), а частям города - точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам:

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

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

Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.

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

На карте старого Кёнигсберга был ещё один мост, появившийся чуть позже, и соединявший остров Ломзе с южной стороной. Своим появлением этот мост обязан самой задаче Эйлера-Канта.

Кайзер (император) Вильгельм славился своей прямотой, простотой мышления и солдатской «недалёкостью». Однажды, находясь на светском рауте, он чуть не стал жертвой шутки, которую с ним решили сыграть учёные умы, присутствующие на приёме. Они показали кайзеру карту Кёнигсберга, и попросили попробовать решить эту знаменитую задачу, которая по определению была нерешаемой. Ко всеобщему удивлению, Кайзер попросил перо и лист бумаги, сказав, что решит задачу за полторы минуты. Ошеломлённый немецкий истеблишмент не мог поверить своим ушам, но бумагу и чернила быстро нашли. Кайзер положил листок на стол, взял перо, и написал: «приказываю построить восьмой мост на острове Ломзе». Так в Кёнигсберге и появился новый мост, который так и назвали - мост Кайзера. А задачу с восемью мостами теперь мог решить даже ребёнок.

Заключение:

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

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

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

Список литературы:

1. «Графы и их применение» Л. Ю. Березина, издательство «Просвещение», Москва, 1979 г.

2. «Алгебра 9 класс» под редакцией С. А. Теляковского, издательство «Просвещение», Москва, 2010 г.