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

Цели урока:

• расширить представления о видах информационных моделей;
• составить представление об организации  информации в виде графа, сети;
• научиться решать задачи ЕГЭ методом построения  графов.

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

—В 1736 году  Леонард Эйлер нашел решение головоломки «Проблема кёнигсбергских мостов». Река Прегель, протекающая через Кенигсберг омывает два острова. Берега реки связаны мостами так, как это показано на рисунке. Требовалось  найти маршрут, проходящий по всем четырем участкам суши по одному разу, а конец и начало пути должны совпадать. Эйлер доказал, что такого маршрута не существует, и разработал свою теорию решения головоломок. 1736 год принято считать годом рождения теории графов.

Граф - - это средство для наглядного представления состава и структуры системы.

Элементы  структуры графа:

Граф состоит из вершин, связанных линиями.

Вершины графа изображаются кругами, овалами, прямоугольниками и пр.

Дуга –  это направленные линии (стрелки), вершины.

Ребра –  это ненаправленные линии, связывающие вершины.

—Граф называется неориентированным, если его вершины соединены ребрами.

—Граф называется ориентированным, если его вершины соединены дугами.

—Граф называется взвешенным, если его вершины или рёбра (дуги) характеризуются весом.

—Цепь – это путь по вершинам и ребрам (дугам) графа не более одного раза

—Цикл – это цепь, у которой начальная и конечная вершины совпадают.

Граф с циклом называется сетью.

Семантическая сеть – это граф, на котором отражены объекты и связи  между ними.

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

Цели урока:

• расширить представления о видах информационных моделей;
• составить представление об организации информации в виде графа, сети;
• научиться решать задачи ЕГЭ методом построения графов.

Ответьте на вопросы:

• что такое схема?
• приведите примеры схем, представляющих внешний вид объекта, его структуру;
•   что такое чертёж?
•   где применяют чертежи?

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

Колесо истории

• В 1736 году Леонард Эйлер нашел решение головоломки «Проблема кёнигсбергских мостов». Река Прегель, протекающая через Кенигсберг омывает два острова. Берега реки связаны мостами так, как это показано на рисунке. Требовалось найти маршрут, проходящий по всем четырем участкам суши по одному разу, а конец и начало пути должны совпадать. Эйлер доказал, что такого маршрута не существует, и разработал свою теорию решения головоломок. 1736 год принято считать годом рождения теории графов.

Маша дружит с Костей и Таней, Марина дружит с Таней и с Машей, Костя дружит с Таней и Сашей. Таня дружит с Машей. Изобразите графически систему отношений между детьми.

Костя

Маша

Таня

Саша

Марина

Таким образом, мы построили граф.

Граф

- это средство для наглядного представления состава и структуры системы.

Элементы структуры графа:

• Граф состоит из вершин , связанных линиями.
• Вершины графа изображаются кругами, овалами, прямоугольниками и пр.
• Дуга – это направленные линии (стрелки), вершины.
• Ребра – это ненаправленные линии, связывающие вершины.

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

Генеалогическое древо Романовых

Структурная формула нитробензола имеет вид

Схему московского метрополитена можно рассмотреть как граф. Вершинами являются станции метро, линии отражают рельсовую связь между станциями.

Первичное закрепление изученного материала. Задание 1. Назовите элементы графа

вершина

дуга

Типы графов

• Граф называется неориентированным, если его вершины соединены ребрами.

• Граф называется ориентированным, если его вершины соединены дугами.

Типы графов

• Граф называется взвешенным , если его вершины или рёбра (дуги) характеризуются весом .

• Цепь – это путь по вершинам и ребрам (дугам) графа не более одного раза

• Цикл – это цепь, у которой начальная и конечная вершины совпадают.

Граф с циклом называется сетью .

Семантическая сеть – это граф, на котором отражены объекты и связи между ними.

: Описать граф - это значит, ответить на вопросы

• Сколько вершин?
• Есть ли рёбра?
• Есть ли направление?
• Все ли вершины соединены рёбрами?

На каких школьных предметах вы встречались с графами, приведите примеры?

Задание 2. Определите типы графов:

А)

Б)

неориентированный

ориентированный

В)

26

15

31

взвешенный

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

• §2.10 (стр.101-104)

• 8,9*(стр114 учебника)