Информатика 9 класс
Урок№2 - Графы.

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

На прошлом уроке мы уже говорили о том, что одним из методов познания является моделирование, рассматривали различные классификации моделей и выделили в качестве предмета нашего рассмотрения информационные модели. Среди них можно выделить графические информационные модели, к которым относятся карты, чертежи, схемы, диаграммы, графики и предмет сегодняшнего рассмотрения — графы.

Если рассматривать группу объектов вместе с имеющимися между ними связями как единое целое, то можно говорить о системе. Мы можем графически изобразить объекты системы вершинами, а связи между ними линиями (рёбрами). В этом случае мы получим информационную модель системы в форме графа.
Если рёбра графа имеют направление, то оно отображается стрелками, а граф называется ориентированным (направленным).
Вершины графа могут отображаться точками, кругами, прямоугольниками и т.д.
Если вершины или ребра графа характеризуются некоторой дополнительной информацией — весом вершины или ребра, то такой граф называют взвешенным.
С помощью взвешенных графов удобно изображать дороги между населенными пунктами. Например, в приведенном примере указана протяжённость дорог в километрах.
Проведём путь, проходящий по вершинам и ребрам графа так, чтобы любое ребро входило в него не более одного раза. Такой путь называется цепью. Цепь, у которой совпадают начальная и конечная вершины, называется циклом.
Граф с циклом называется сетью.Если персонажей некоторого литературного произведения, мультфильма или сериала представить вершинами графа, а связи между ними изобразить рёбрами, то получится граф, который называют семантической сетью.
Информационные модели в виде графов широко используются в повседневной жизни.
Например, при проектировании нового жилого района можно здания обозначить как вершины графа, а дороги, коммуникации и т.д. — ребрами графа. По таким графам удобно, например, прогнозировать загрузку дорог и находить оптимальные транспортные маршруты. Другим примером является схема метрополитена. Вершинами в графе в этом случае являются станции метро.
Граф, в котором отсутствуют циклы, называется деревом.
В этом случае между любыми двумя вершинами существует только один путь.
С помощью дерева удобно представлять иерархическую систему.
У дерева выделяется одна главная вершина, которую называют корнем.
Каждая вершина дерева, исключая корень, может иметь только одного предка (вершина верхнего уровня), но при этом может порождать множество потомков, отображаемых вершинами нижнего уровня. Вершины, у которых отсутствуют порожденные вершины, называются листьями.
Одним из известных применений графов является генеалогическое или родословное дерево, на котором отображаются родственные связи.
Существуют задачи, которые удобно решать с помощью графов.
Например, если мы хотим отобразить все возможные варианты трехзначных чисел, которые могут получиться из цифр 7 и 8.
С помощью графов удобно решать задачи на определение выигрышной стратегии игроков.
Задача на анализ информации, представленной в виде графа, является одной из предлагаемых на государственной итоговой аттестации по информатике.
Итак, сегодня вы узнали о том, какие бывают графы и из каких элементов они состоят, для каких целей создаются. Получили представление об ориентированных и неориентированных графах, деревьях. Научились решать задачи на определение количества путей в графе, используемые при государственной итоговой аттестации. Закрепите полученные знания на практике, выполнив упражнения.
Вводятся понятия — Граф. Вершина, ребро, путь. Ориентированные и неориентированные графы. Длина (вес) ребра и пути. Дерево. Корень, лист, вершина.

свернуть