Лекция. Тема: Понятие о графах и деревьях

Тема. Структура информации. Списки, графы, деревья.

1. ПОНЯТИЕ О ГРАФАХ

Основы теории графов как математической науки заложил в 1736г. Леонардо Эйлер, рассматривая задачу о Кёнигсбергских мостах. Сегодня эта задача стала классической.

Давайте её рассмотрим. Это, пожалуй, самая известная головоломка, придуманная аж в XVIII веке, и захватившая умы человечества на многие годы. Называется она задача о семи Кёнигсбергских мостах.

В Кёнигсберге начиная с XIV было построено 7 мостов: Медовый мост, Лавочный мост, Зелёный мост, Рабочий мост, Кузнечный мост, Деревянный мост и Высокий мост, соединяющий остров и полуострова в единый город. Тогда и возникла головоломка: «Как пройти по всем мостам, не проходя ни по одному дважды?»

Десятилетиям жители города пытались решить эту задачу как практически (гуляя по городу), так и теоретически.

И только Леонард Эйлер, введя новое понятие — ГРАФ, смог решить ее раз и навсегда.

Графом называется конечное множество точек, некоторые из которых соединены линиями

Графы делятся на (виды):

• Граф, содержащий только ребра, называется неориентированным.

• Граф, содержащий только дуги, называется ориентированным или орграфом.

• Если рёбра графа имеют направление, то оно отображается стрелками, а граф называется ориентированным (направленным).

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

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

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

Цепь – путь по вершинам и ребрам, включающий любое ребро графа не более одного раза.

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

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

Количество ребер, выходящих из вершины графа, называется степенью вершины.

Изолированная вершина – степень, которой равна 0

Конечная вершина графа – степень, которой равна 1

Вершина графа, имеющая нечетную степень, называется нечётной, а чётную степень - чётной

Свойства граф:

Эйлер установил, что:

1. Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно или не может существовать граф, который имел бы нечётное число нечётных вершин.

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

3. Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.

ВЫВОД: пройти только один раз по каждому мосту невозможно.

Информационные модели в виде графов широко используются в повседневной жизни.

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

Так с помощью взвешенных графов удобно изображать дороги между населенными пунктами. Например, в приведенном примере указана протяжённость дорог в километрах.

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

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

По таким графам удобно, например, прогнозировать загрузку дорог и находить оптимальные транспортные маршруты.

Ещё одним примером является схема метрополитена. Вершинами в графе в этом случае являются станции метро.

2. ПОНЯТИЕ О ДЕРЕВЬЯХ

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

1 2

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

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

В этом случае между любыми двумя вершинами существует только один путь.

Т.е. Деревом называется граф, который состоит только из простых путей.

При этом надо учитывать, что дерево – это граф иерархической структуры.

Например:

Структура видов ЭВМ

У дерева выделяется одна главная вершина, которую называют корнем.

Каждая вершина дерева, исключая корень, может иметь только одного предка (вершина верхнего уровня),

но при этом может порождать множество потомков, отображаемых вершинами нижнего уровня.

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

Высотой дерева называется длина самого длинного пути от корня дерева до листа.

Одним из известных применений графов является генеалогическое или родословное дерево, на котором отображаются родственные связи.

Или схема спортивных соревнований:

№1

Впишите в текст недостающее слово.

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

№2

К каждой иллюстрации подберите подходящую подпись.

1)   2) 3) 

Взвешенный граф

Направленный граф

№3

Вставьте недостающие слова в определение.

Цепь, у которой совпадают начальная и конечная _____ , называется ________ .

вершины

сетью

циклом

линии (рёбра)

графом

№4

Укажите все правильные ответы.

При представлении иерархической системы с помощью дерева используются понятия:

Предок

Цикл

Корень

Потомок

Все перечисленные

Лист

№5

Укажите все правильные ответы.

Семантическая сеть может быть представлена для:

дерево игры

мультфильма

сериала

все перечисленные

учеников класса

семейной родословной

№6

№7

№8

Поставьте каждой из приведенных ниже причин соответствующее изображение.

Деревья

Сети

1 2 3

4 5

№9

Укажите все правильные ответы.

№10

Выберите правильный ответ.

№11

№12

ВАЖНО! Подведем итоги

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

Получили представление об ориентированных и неориентированных графах.

Выяснили чем графы и деревья отличаются между собой.

8