Графы

Слайд 1

Московский департамент образования Северо-Западный учебный округ. Конкурс «Искатели». Творческо - исследовательская работа. Секция: «Математика». Тема: «Графы» Выполнили: Сербул Анна, Вольнова Анастасия, Ходина Виктория Студентки 12 группы ПК № 18 «Митино» г. Москвы. Научный руководитель: Изместьева Раиса Жаматдиновна . Город Москва 2014 год.

Слайд 2

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

Слайд 3

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

Слайд 4

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

Слайд 5

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

Слайд 6

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

Слайд 7

Смежность и инцидентность. Вершины, соединенные ребром или дугой называются смежными. Ребра или дуги, имеющие общую вершину, называются смежными . Инцидентность – это принадлежность вершины графа к ребру или дуге графа. Ребро (дуга) и любая принадлежащая ему вершина - инцидентны.

Слайд 8

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

Слайд 9

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

Слайд 10

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

Слайд 11

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

Слайд 12

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

Слайд 13

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

Слайд 14

Информатика В информатике с помощью графов мы строим блок схемы .

Слайд 15

Этот пример относится к медицине. Известно, что у раз­ных людей кровь отличается по группе. Существуют четыре группы крови. Оказывается, что при переливании крови от одного человека к другому не все группы совместимы. Граф показывает возможные варианты переливания крови. Группы крови — это вершины графа с соответствующими номерами, а стрелки указывают на возможность переливания одной группы крови человеку с другой группой крови. Например, из этого графа видно, что кровь 1-й группы можно переливать любому человеку, а человек с первой группой крови воспринимает только кровь своей группы. Видно также, что человеку с 4-й группой крови можно переливать любую, но его собственную кровь можно переливать только в ту же группу.

Слайд 16

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

Слайд 17

Задача о Кенигсбергских мостах. Город Кенигсберг (ныне Калининград) расположен на берегах и двух островах реки Прегель ( Преголи ). Различные части города соединены семью мостами, как показано на рисунке. В воскресные дни горожане совершают прогулки по городу. Можно ли выбрать такой маршрут, чтобы пройти один и только один раз по каждому мосту и притом вернуться в начальную точку пути? Решение. Составим план данного города. Покажем 4 части города зеленым цветом, речку голубым и 7 мостов желтым цветом. Т.к. граф имеет больше двух нечётных вершин, то его не возможно начертить одним росчерком, а следовательно, искомого маршрута не существует.

Слайд 18

Между девятью планетами солнечной системы установлено космическое сообщение . Рейсовые ракеты летают по следующим маршрутам: Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Вене; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса ? Теперь сразу видно, что долететь с Земли до Марса нельзя.

Слайд 19

Лабиринт - это граф. А исследовать его - это найти путь в этом графе. Попробуем начертить граф одним росчерком, начав с любой вершины

Слайд 20

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

Слайд 21

Любую задачу в одно действие можно изобразить в виде следующей граф – модели: Задачи: А) Поезд шел со скоростью 50 км/ч. Сколько км прошел поезд за 4 часа? Б) Толя с бабушкой ходили по грибы. Придя домой они сосчитали, сколько грибов собрал каждый. Оказалось, что бабушка собрала 69, а Толя 43 гриба. Сколько грибов они собрали вместе? В) Человек прошел расстояние 100 м. Сколько шагов он сделал, если длина его шага ровна 0,8 м? (Закрашенные кружочки - это данные задачи, а не закрашенные - это результат действия )

Слайд 22

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

Слайд 23

Список используемой литературы. 1. Э. Фрид, И. Пастор, И. Рейман, П. Реверс, И Ружа Малая математическая энциклопедия. 2. С. М. Никольская Энциклопедия «Школьная математика». 3. В.А.Гусев , А.И.Орлов , А.Л.Розенталь «Внеклассная работа по математике 7-9 классах». 4. В.В. Коннов , Г. А. Клековкин , Л.П. Коннова «Геометрическая теория графов». 5. Дж. Авндо-Бодино «Применение в экономике теории графов». 6. А.П.Савин «Энциклопедический словарь юного математика». 7. Сведения из Интернета.