СКИДКА 40% НА ДЕЙСТВИТЕЛЬНО ИНТЕРЕСНЫЕ И ПОЛЕЗНЫЕ ВЕБИНАРЫ И КУРСЫ ОТ УРОК.РФ – АКЦИЯ ДЕЙСТВУЕТ ДО 31 ДЕКАБРЯ 2019
12+  Свидетельство СМИ ЭЛ № ФС 77 - 70917
Лицензия на образовательную деятельность №0001058
Пользовательское соглашение     Контактная и правовая информация
 
Педагогическое сообщество
УРОК.РФУРОК
Материал опубликовал
Побережнюк Сергей Владимирович608
учитель в школе
Россия, Свердловская обл., Екатеринбург

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

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

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

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

Элементы графа: Вершины — это компоненты системы изображаемые кругами, овалами, прямоугольниками. Ребра — это линии (стрелки), связывающие компоненты между собой определенным образом.

Структуры графа: 1) линейный – вершины соединены последовательно (схема Екатеринбургского метро, схема состава поезда) 1 2 3

2) дерево —граф, предназначенный для отображения подчиненности между объектами. Каждая вершина связана только с верхней и не связана больше ни с чем (цепная реакция, генеалогическое дерево);

3) сеть — это граф, в котором вершины связаны между собой по принципу «многие ко многим» (компьютерная сеть);

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

Теория графов и Леонард Эйлер Загадка о 7 мостах через реку Преголь (Кёнигсберг). В XVIII веке задача заинтересовала математика Леонарда Эйлера и он смог найти правило, пользуясь которым, легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них.

Выводы Эйлера: 1) Число нечётных вершин (к которым ведёт нечётное число рёбер) графа должно быть чётно (нет графа, который имел бы нечётное число нечётных вершин). 2) Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф (можно начинать с любой вершины и завершить граф в той же вершине). 3) Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.

Созданная Эйлером, при решении загадки, теория графов нашла широкое применение в транспортных системах (составление оптимальных маршрутов доставки грузов), экономике, банковской сфере, химии, медицине, криминалистике и т.д. и т.п.).