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

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

2

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

4 ТОЧКИ НАЗЫВАЮТСЯ ВЕРШИНАМИ, ИЛИ УЗЛАМИ, ГРАФА, ЛИНИИ – РЕБРАМИ ГРАФА. 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 Граф - это множество точек (для удобства изображения - на плоскости) и попарно соединяющих их линий (не обязательно прямых). В графе важен только факт наличия связи между двумя вершинами. От способа изображения этой связи структура графа не зависит.

5

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

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

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

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

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

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

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

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

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

15

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

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

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

19

20 Нурлат Караульная Гора БурметьевоВишневая Поляна Тюрнясево Нурлат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

21 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

22

23