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

Презентация:



Advertisements
Похожие презентации
Рисунок одним росчерком пера. Проект по элективному курсу по математике «Круги Эйлера. Графы.» на тему Выполнила ученица 9Б класса средней школы 9 Миронова.
Advertisements

Впервые основы теории графов появились в работах Леонарда Эйлера ( ; швейцарский, немецкий и российский математик), в которых он описывал решение.
Математика вокруг нас. Какая наука может быть более благородна, более восхитительна, более полезна для человечества, чем математика? (Франклин).
Научно -исследовательская работа Авторы: Быстрякова Наталья, Шайахметова Алина ученицы 9 В класса МАОУ « СОШ9» г.Нурлат, РТ Руководитель: Мустафина Наталья.
Теория графов Основные определения. Задание графов Графический способ – Привести пример графического задания графа, состоящего из вершин А, В и С, связанных.
Задача о максимальном потоке в сети Алгоритм Фалкерсона-Форда.
АЛГОРИТМЫ НАХОЖДЕНИЯ КРАТЧАЙШИХ ПУТЕЙ НА ГРАФАХ..
Графы Степень вершины Подсчет числа ребер графа. Разминка… Вставьте недостающие слова в предложения (граф, титул, ребро, вершина) Всем известно, что слово.
ГРАФЫ … ГРАФЫ ??? ГРАФЫ ??? ГРАФЫ !!! ГРАФЫ !!!. Задача 1 Между девятью планетами Солнечной системы установлено космическое сообщение. Рейсовые ракеты.
ВЫПОЛНИЛ: УЧЕНИК 11 КЛАССА «А» ЛОБЖА АРТЕМ ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ: ОУ СОШ 51 Образовательное учреждение: г. Комсомольск – на – Амуре, 2012 год.
Теория Графов Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год), хотя термин «граф» впервые ввел в 1936 году венгерский математик Денеш.
ТЕОРИЯ ГРАФОВ ЗАДАЧА КОММИВОЯЖЕРА Гамильтоновы графы применяются для моделирования многих практических задач. Основой всех таких задач служит классиче.
ПРАВОСЛАВНЫЙ СВЯТО-ТИХОНОВСКИЙ БОГОСЛОВСКИЙ УНИВЕРСИТЕТ (БОГОСЛОВСКИЙ ФАКУЛЬТЕТ) Презентация по математике на тему: Элементы теории графов.
Решение логических задач Грицунов Максим учащийся 6 «Б» класса МОУ гимназия 1 г. Белгород.
Домашнее задание «Применение графа» ВСПОМНИМ… Граф Простейшая модель системы.Отображает элементарный состав системы и структуру связей Сеть Граф с возможностью.
I тур 1. Какой граф называется неполным? 2. Какой граф называется связным? 3. Какой граф называется плоским? 4. Какой граф называется нулевым? 5. Какой.
Муниципальное бюджетное общеобразовательное учреждение Кабановская СОШ Как измерить расстояние между родственниками Автор: Ученица 5б класса Балабойко.
Графы Граф – совокупность точек и линий, в которой каждая линия соединяет две точки. Точки – вершины графа Линии – рёбра графа Вершины, соединенные ребром,
Тем, кто учит математику, Тем, кто любит математику, Тем, кто ещё не знает, Что может полюбить математику, Этот «Час математики» посвящается!
Задачи, решаемые с помощью графов. 1. Утверждают, что в одной компании из пяти человек каждый знаком с двумя и только двумя другими. Возможна ли такая.
Транксрипт:

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

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

Чтобы помочь принцу, нужно найти такой маршрут, по которому он сможет обойти все дома и найти Золушку:

или

или Видно, что существует много способов отыскать нужную дорогу ! Такую процедуру математики называют поиском в графе!!!

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

и Такой путь назвали гамильтоновым в честь великого математика Уильяма Роуана Гамильтона.

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

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

Мы увидели, что математика может помочь нашему принцу поскорее найти Золушку. Вопросы, которые мы рассматривали уже давно известны в этой науке. Можно сделать вывод: