Информационные модели в виде графов

1.

Конкурс интерактивных презентаций «Интерактивная мозаика»
Информационные модели
в виде графов

2.

Содержание
Повторение
Понятие «граф»
Примеры графов
Характеристики графов
Применение графов
Граф-дерево
Задачи
Выход

3.

Вспомним:
Модель – это упрощенное представление
реального объекта
Информационная модель – это модель
объекта, представленная в виде информации,
описывающей существенные характеристики
объекта для определенного случая.
Информационные модели нельзя потрогать
или увидеть, они не имеют материального
воплощения .

4.

Выберите правильные ответы:
C
C
C
C
C
C
Зубная щетка – это реальный объект
Проверка двигателя автомобиля на стенде – модель
процесса
Мобильный телефон – информационная модель
Басня И. А. Крылова «Стрекоза и муравей» информационная модель
Нотная запись мелодии «Гимна России» информационная модель
Испытание нового лекарства на добровольцах –
информационная модель
ПРОВЕРИТЬ

5.

Понятие «Граф»
Графы –это схемы, состоящие из точек и соединяющих
эти точки отрезков прямых или кривых
Точки – вершины графа; линии, которые соединяют
вершины – ребра графа.
Научные графы с дворянским титулом «граф» связывает
общее происхождение от латинского слова «графио» - пишу.

6.

Понятие «Граф»
Нечетные вершины – вершины, из которых выходит
нечетное количество ребер
Четные вершины – вершины, из которых выходит
нечетное количество ребер

7.

Понятие «Граф»
При изображении графов на рисунках или схемах
отрезки могут быть прямолинейными или
криволинейными.
Длины отрезков и расположение точек произвольны.
На рисунке изображен один и тот же граф:

8.

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

9.

Примеры графов
Модель управления предприятием (школой,
театральным коллективом и т. д.) очень удобно
представлять в виде графа.
Всем хорошо известно понятие «родословное
дерево» и вы можете изобразить в такой форме
ваши родственные отношения.
Система «Школьный урок», состоящая из
следующих элементов: ученик, учитель, учебник,
тетрадь, классный журнал, классная доска, мел,
парта, учительский стол, классная комната.
Круговорот воды в природе.

10.

Примеры графов

11.

Примеры графов
Познакомимся с основными понятиями теории графов
при решении задачи.
Задача:
Аркадий, Борис, Владимир, Григорий и
Дмитрий при встрече обменялись
рукопожатиями (каждый пожал руку каждому
по одному разу). Сколько всего рукопожатий
было сделано?
Пусть каждому из пяти молодых людей
соответствует определенная точка на
плоскости, названная первой буквой его
имени, а производимому рукопожатию —
отрезок или часть кривой, соединяющая
конкретные точки — имена.

12.

Примеры графов
1. Ситуация, соответствующая
моменту, когда рукопожатия еще
не совершались, представляет
собой точечную схему
2. Ниже изображен граф,
соответствующий всем
совершенным рукопожатиям.
Этот граф является полным
графом
Количество ребер графа соответствует количеству рукопожатий,
совершенных молодыми людьми. Их - 10.

13.

Примеры графов
Известно, что людям можно переливать кровь или только своей группы, или
меньшей по номеру. Составим граф переливания крови.
●Чтобы указать, что ребра ориентированы, ставят стрелки, тогда ребра
называются дугами, а граф – ориентированным.
●Петля это дуга, начальная и конечная вершина которой совпадают.

14.

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

15.

История появления теории
Годом зарождения теории графов
считается 1736-й, когда математик
Леонард Эйлер опубликовал в
Санкт-Петербургской Академии
наук работу, посвящённую семи
мостам города Кёнигсберга.

16.

Мосты Кёнигсберга
В XVI веке в Кёнигсберге были построены 7 мостов,
соединяющих разные части города.
Среди горожан известна загадка о том, как пройти по
всем мостам лишь однажды.

17.

Мосты Кёнигсберга
Для решения этой задачи Эйлер вводит понятие «графа»
как множества непересекающихся рёбер или связей,
соединяющих пары вершин.

18.

Мосты Кёнигсберга
Эйлер доказал, что решения не существует.

19.

Характеристики графа
Часто дугам или вершинам приписывают
количественную характеристику - “вес”. Это позволяет
выполнять в модели не только качественный, но и
количественный анализ.
В примере вес ребра является расстоянием между
городами.
76
Кострома
Ярославль
95
57
102
Иваново
87
Углич
Ростов
Великий

20.

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

21.

Граф - дерево
Слово «дерево» в теории графов
означает граф, в котором нет циклов,
то есть в котором нельзя из некоторой
вершины пройти по нескольким
различным ребрам и вернуться в ту
же вершину.
Деревья особенно часто возникают на
практике при изображении
различных иерархий.
Генеалогическое дерево будет
деревом и в смысле теории графов,
если в этом семействе не было браков
между родственниками.

22.

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

23.

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

24.

Задания
Задание 1.
Начертите граф , на котором были бы изображены
высказывания: «8 кратно 2» «9 кратно 4» «8 кратно 8», «4
кратно 2» «4 кратно 4» «4 кратно 1», «2 кратно 1», «4
кратно 4», «2 кратно 2». Каждая стрелка графа должна
обозначать «кратно».
Задание 2.
Представьте в виде графа схему питания для системы,
состоящей из следующих организмов: трава, кролики,
волки, травоядные насекомые, воробьи, ястребы, жукинавозники

25.

Задания
Задание 3.
Жители пяти домов поссорились друг с другом и, чтобы не
встречаться у колодцев, решили, что хозяин каждого дома будет
ходить к «своему» колодцу по «своей» тропинке. Удастся ли им это
сделать?
Задание 4.
Во дворе, который окружён высоким забором, находятся три
домика: красный, жёлтый и синий. В заборе есть три калитки:
красная, жёлтая и синяя. От красного домика проведите дорожку к
красной калитке, от жёлтого домика – к жёлтой калитке, от синего –
к синей так, чтобы эти дорожки не пересекались.

26.

Логическая игра «Четыре краски»
Американец Стивен Барр предложил
логическую игру на бумаге для двух
игроков, основанную на теории графов.
Для этой игры нужны четыре цветных
карандаша. Первый игрок чертит
произвольную область, второй игрок
раскрашивает её в любой из этих 4-х цветов
и присоединяет свою область. Первый
игрок в свою очередь раскрашивает
область второго игрока и добавляет новую
область, и далее каждый игрок
раскрашивает область соперника и
добавляет свою. При этом области,
имеющие общую границу, должны быть
раскрашены в разные цвета. Проигрывает
тот, кто на своём ходу вынужден будет взять
пятую краску.

27.

Источники картинок
http://school-sector.relarn.ru
http://ru.wikipedia.org/
ordinat.ru
gifakt.ru
http://ru.wikipedia.org/
http://wiki.saripkro.ru/index.php/Учебная_тема:_Эйлеровы_гр
афы
http://dvo.sut.ru/libr/himath/w163rabk/10.htm

28.

Источники информации
Л. Босова «Информатика и ИКТ», учебник 7 класс, БИНОМ, 2010
Л. Босова «Информатика и ИКТ», рабочая тетрадь 7 класс, БИНОМ,
2010
http://school-sector.relarn.ru
http://rusedu.info
http://maps.mail.ru/
А.В. Самохин. Проблема четырех красок: неоконченная история
доказательства. Соросовский образовательный журнал. 2000, 7
http://ru.wikipedia.org/
Энциклопедический словарь юного математика\Сост.А.П.Савин.М.: Педагогика, 1989
М. Гарднер «Математические досуги»М.: Мир, 1972