Научно -исследовательская работа Авторы: Быстрякова Наталья, Шайахметова Алина ученицы 9 В класса МАОУ « СОШ9» г.Нурлат, РТ Руководитель: Мустафина Наталья.

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



Advertisements
Похожие презентации
Домашнее задание «Применение графа» ВСПОМНИМ… Граф Простейшая модель системы.Отображает элементарный состав системы и структуру связей Сеть Граф с возможностью.
Advertisements

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

Научно -исследовательская работа Авторы: Быстрякова Наталья, Шайахметова Алина ученицы 9 В класса МАОУ « СОШ9» г.Нурлат, РТ Руководитель: Мустафина Наталья Викторовна, учитель информатики МАОУ « СОШ9» г.Нурлат, РТ 2012 г

ВПЕРВЫЕ ПОНЯТИЕ «ГРАФ» ВВЕЛ В 1936 г. ВЕНГЕРСКИЙ МАТЕМАТИК ДЕННИ КЁНИГ. НО ПЕРВАЯ РАБОТА ПО ТЕОРИИ ГРАФОВ ПРИНАДЛЕЖАЛА ПЕРУ ВЕЛИКОГО ЛЕОНАРДА ЭЙЛЕРА И БЫЛА НАПИСАНА ЕЩЕ В 1736 г.

ТОЧКИ НАЗЫВАЮТСЯ ВЕРШИНАМИ, ИЛИ УЗЛАМИ, ГРАФА, ЛИНИИ – РЕБРАМИ ГРАФА. GH E C D F A B C A B a b c d e A B C D E u p s t r q Граф - это множество точек (для удобства изображения - на плоскости) и попарно соединяющих их линий (не обязательно прямых). В графе важен только факт наличия связи между двумя вершинами. От способа изображения этой связи структура графа не зависит.

* Изолированная вершина вообще не имеет ребер (ее степень равна 0). Любому ребру соответствует ровно две вершины, а вот вершине может соответствовать произвольное количество ребер, это количество и определяет степень вершины.

Длина пути - количество ребер, из которых этот путь состоит. Например, длина уже упомянутых путей adbc и abc - 3 и 2 соответственно. Расстояние между между вершинами u и v - это длина кратчайшего пути от u до v. Из этого определения видно, что расстояние между вершинами a и c в графе на рис. равно 2. * Цикл - это замкнутый путь. Все вершины в цикле, кроме первой и последней, должны быть различны. Например, циклом является путь abda в графе на рисунке.

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

ПУТЬ, КОТОРЫЙ СОДЕРЖИТ ВСЕ РЕБРА ГРАФА ТОЛЬКО ОДИН РАЗ НАЗЫВАЕТСЯ ЭЙЛЕРОВЫМ ЦИКЛОМ. ГРАФ ЯВЛЯЕТСЯ ЭЙЛЕРОВЫМ ТОГДА И ТОЛЬКО ТОГДА, КОГДА ОН – СВЯЗНЫЙ ГРАФ, ИМЕЮЩИЙ ВСЕ ЧЕТНЫЕ ВЕРШИНЫ эйлеров граф Другими словами, эйлеров граф – это граф,который можно нарисовать одним росчерком ГРАФ, ОБЛАДАЮЩИЙ ЭЙЛЕРОВЫМ ЦИКЛОМ, НАЗЫВАЕТСЯ ЭЙЛЕРОВЫМ.

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

* 1. Нарисовать граф, где вершины – острова и берега, а ребра – мосты. * 2. Определить степень каждой вершины и подписать возле нее. * 3. Посчитать количество нечетных вершин. * 4. Обход возможен: * a. ЕСЛИ все вершины – четные, и его можно начать с любого участка. * b. ЕСЛИ 2 вершины – нечетные, но его нужно начать с одной из нечетных местностей. * 5. Обход невозможен, если нечетных вершин больше 2. * 6. Сделать ВЫВОД. * 7. Указать Начало и Конец пути.

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

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

А, B, C, D. Нечетные вершины: А, B, C, D. А В С Д Какие вершины четные, а какие нечетные? Подпишем степени вершин. Ответ: обход невозможен

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

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

Найти кратчайший путь из города Нурлат в населенный пункт Тюрнясево ?

Нурлат Караульная Гора БурметьевоВишневая Поляна Тюрнясево Нурлат23,821,819,232 Караульная Гора 23,82018,613 Бурметьево 21,8205,826,8 Вишневая Поляна 19,218,65,821,4 Тюрнясево ,821,4 23, ,8 18,6 21,4 19,2 5,8 26,8

23, ,8 18,6 21,4 19,2 5,8 26,8 Вывод: Кратчайший путь равен 32 км НБТ = 21,8+26,8=48,6 НВПТ= 19,2+21,4=40,6 НВПБТ= 19,2+5,8+26,8=51,8 НТ=32 НКГТ=23,8+13=36,8 НКГВПТ=23,8+1,6+21,4=63,8