Презентация урока по вероятности и статистике в 7 классе по теме "Графы, вершина и рёбра графа"

Тема урока: Графы. Вершина и рёбра графа Вероятность и статистика 7 класс М С В А К

Девиз урока: Чем невозможнее кажется задача, тем интереснее её решать. Цитата из сериала «Легенда об Искателе»

Цели урока: Познакомиться с понятием «граф», «вершина графа», «ребро графа» Научиться решать задачи с помощью графов

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

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

Линия, выходящая из некоторой вершины и входящая в неё же, называется петля. дуга ребро петля А В С Точки - А,В,С – вершины графа Основные понятия Направленная линия (со стрелкой) называется дуга. Линия ненаправленная (без стрелки) называется ребро.

Основоположники теории графов. Леонард Эйлер (1707-1782), российский математик, швейцарец по происхождению, академик Петербургской и Берлинской академии наук Густав Роберт Кирхгоф (1824-1871), иностранный член-корреспондент Петербургской академии наук разработал теорию деревьев

Задача, для решения которой Эйлер впервые применил графы, - это задача о мостах Кенигсберга. В XVIII веке город Кенигсберг (сейчас Калининград) был расположен на берегах реки и двух островах. Различные части города были соединены семью мостами. Можно ли совершить прогулку, пройдя по каждому мосту ровно один раз? Задача Эйлера

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

Получился следующий граф: Задача Эйлера

В итоге Эйлер доказал общее утверждение: для того чтобы обойти все рёбра графа по одному разу и вернуться в исходную вершину, необходимо и достаточно выполнения следующих двух условий: 1. Из любой вершины графа должен существовать путь по его рёбрам в любую другую вершину (граф должен быть связным); 2. Из каждой вершины должно выходить чётное количество рёбер. Если отбросить условие возвращения в исходную вершину, то можно допустить наличие двух вершин, из которых выходит нечётное количество рёбер. В этом случае начинать движение следует с одной из этих двух вершин, а заканчивать - в другой. Задача Эйлера

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

Графы в современном мире

Медицина Медицина Кибернетика Информатика Химия Физика Транспорт Строительство Прикладная математика Экономика Науки, опирающиеся на знание теории графов:

Науки, опирающиеся на знание теории графов: Примеры различных графов:

Решение задач М С В А К А В С К М А В С К М А В С К М А - 1 1 0 0 В 1 - 1 1 1 С 1 1 - 1 0 К 0 1 1 - 1 М 0 1 0 1 -