Всегда выбирайте самый трудный путь, на нем вы не встретите конкурентов! Шарль де Голль.

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



Advertisements
Похожие презентации
ИНФОРМАЦИОННЫЕ МОДЕЛИ НА ГРАФАХ. ПУТИ В ГРАФАХ. ABCDE A B291 C10934 D81311 E16411.
Advertisements

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

Всегда выбирайте самый трудный путь, на нем вы не встретите конкурентов! Шарль де Голль

ABCDE A B291 C10934 D81311 E16411 В таблице представлено расстояние между населенными пунктами в километрах. Определить кратчайшее расстояние между пунктами A и E.

Тема урока: «Информационная модель. Граф. Пути в графах»

Актуализация знаний, умений и навыков Что такое информационная модель? Приведите примеры информационных моделей объектов. Какую информационную модель называют описательной? Как применяют информационную модель на практике?

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

Ответ прост: Графическая модель

История возникновения Графы возникли в восемнадцатом столетии, когда известный математик, Леонард Эйлер, пытался решить теперь уже классическую задачу о Кенигсбергских мостах. В то время в городе Кенигсберге было два острова, соединенных семью мостами с берегами реки Преголь и друг с другом.

Что же такое граф? Граф это множество точек или вершин и множество линий или ребер, соединяющих между собой все или часть этих точек. Граф является информационной моделью некоторого объекта или системы объектов.

ГРАФЫ ориентированные неориентированные дуги рёбра

Взвешенный граф граф, каждому ребру или вершине которого поставлено в соответствие некое значение (вес).

Возвращаемся к условию задачи, озвученной в начале урока.

ABCDE A B291 C10934 D81311 E16411 В таблице представлено расстояние между населенными пунктами. Определить кратчайшее расстояние между пунктами A и E.

Еще раз проанализируем таблицу. Такую таблицу называют весовой матрицей. Какие особенности в таблице вы заметили? ABCDE A B291 C10934 D81311 E16411

Части таблицы, разделённые диагональю – симметричны, т.е. содержат одни и те же данные. Можно рассматривать данные любой половины таблицы, разделенной диагональю.

Приступим к построению графа ABCDE A B291 C10934 D81311 E16411 A B C E D

Определим все пути в графе и расстояние, пройденное на этом пути (вес-расстояние в км.) A B C E D Будем делать обход по графу в алфавитном порядке, т.е. сначала все пути через АВ, АС, AD и т.д. 1. ABCDE – 25 км 2. ABCE – 15 км 3. ABDCE – 10 км 4. ACBDE – 31 км 5. ACDE – 24 км 6. ACE – 14 км 7. ADCE – 15 км 8. ADE – 19 км 9. AE – 16 км

Кратчайший путь в данном графе : ABDCE – 10 км Кратчайший путь в данном графе : ABDCE – 10 км ABCDE A B291 C10934 D81311 E16411 A B C E D

Задача из демоверсии ГИА по информатике и ИКТ:

Решение: A B F D E AF=15 км 2.ABCDF=14 км 3.ACDF=13 км 4. ACEF=14 км 5.ABCEF=15 км C 5 5 2

По заданной таблице построить граф средствами, выписать все возможные пути и определить кратчайший из них. По заданной таблице построить граф средствами текстового процессора Open Office. Org. WRITER, выписать все возможные пути и определить кратчайший из них.

Подведем итоги: Мы вспомнили, что такое информационная модель Узнали, что такое граф Можем классифицировать графы по типам: ориентированный, неориентированный, взвешенный Можем на основе табличной информационной модели построить граф и определить все пути в нем На основе анализа всех путей в графе мы можем делать заключение о том, какой путь самый короткий.

Домашнее задание:

Всем спасибо! До свидания!