Презентация к уроку по теме "Понятие графа. Простейшие свойства"
презентация к уроку по информатике и икт (10 класс) на тему

Слайд 1

Понятие графа. Простейшие свойства. Учитель информатики Трубачева М.В., вторая квалификационная категория

Слайд 2

Графы Кто может с уверенностью сказать, с чего началась теория чисел? С алгоритма, предложенного Евклидом ( IV – III вв. н.э.), или с принадлежащего ему же доказательства теоремы о бесконечности множества простых чисел? Или с работ Диофанта ( III в. н.э.) о решении уравнений в целых числах? Или с исследований Пьера Ферма ( XVII в. н .э.), в которых изучение свойств целых чисел было основной и, самое важное, осознанной целью? Кто может с уверенность сказать, когда возникло понятие функции и кем оно введено? Тоже никто.

Слайд 3

Диофант

Слайд 4

Теория графов Теория графов – одна из немногих математических теорий, для которых точно известен ее создатель, время и место создания: Леонард Эйлер, 1736 год, г. Петербург. Именно в этом году Л.Эйлером в «Записках Петербургской академии наук» была опубликована статья, в которой приводилось решение широко теперь известной задачи о Кенигсбергских мостах. В ней великий математик сформулировал и обосновал критерий, позволяющий отвечать на данный вопрос для любого графа.

Слайд 5

Задача о Кенигсбергских мостах Философ Иммануил Кант, гуляя по городу Кенигсбергу (сейчас этот город называется Калининград), поставил задачу (1736), известную в математике как задача о семи кенигсбергских мостах: можно ли пройти по всем этим мостам и при этом вернуться в исходную точку так, чтобы по каждому мосту пройти только один раз.

Слайд 6

Интерес к теории графов Однако эта статья была единственной в течение почти столетия. Лишь в середине XIX века возродился интерес к теории графов. Исследование электрических сетей, структур молекул и строения кристаллов, применения к решению проблем в биологии и психологии послужили мощным катализатором в становлении данного раздела математики. Графы оказались удобным средством для описания самых разнообразных систем и явились эффективным инструментом структурного анализа. Графы успешно применяются для решения разнообразных задач планирования – выбор оптимального маршрута (транспортная задача), построение сетевого графика, исследование потоков в сетях и т.п. Одной из самых знаменитых задач, которая вызвала фейерверк остроумных работ в области теории графов, была предложенная де Морганом (около 1850 г.) проблема четырех красок.

Слайд 7

Проблема четырех красок

Слайд 8

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

Слайд 9

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

Слайд 10

Лемма о рукопожатиях Количество вершин нечетной степени любого графа всегда четно.

Слайд 11

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

Слайд 12

Задание 1 Существует ли граф с пятью вершинами и следующим набором степеней вершин а) 0, 1, 2,3,4; б) 1, 1, 2, 3, 4; в) 1, 1, 2, 2, 4; г) 1, 1, 2, 3, 3? При ответе «Да» надо предъявить соответствующий граф, ответ «Нет» надо обосновать.

Слайд 13

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

Слайд 14

Домашнее задание Задача о Кенигсбергских мостах.