Лекция 11: Графы и деревья



Скачать 243.47 Kb.
страница1/6
Дата20.04.2013
Размер243.47 Kb.
ТипЛекция
  1   2   3   4   5   6
Лекция 11: Графы и деревья


Элементы теории графов: основные понятия и определения. Способы представления графов и деревьев. Примеры применения деревьев в программировании.






Чуть-чуть истории


Теория графов - довольно молодая наука (по сравнению, скажем, с геометрией). В 1736 году Санкт-Петербургская академия наук опубликовала труд Леонарда Эйлера, где рассматривалась задача о кенигсбергских1) мостах ("Можно ли, пройдя все городские мосты ровно по одному разу, вернуться в исходную точку?"). Это была первая работа по будущей теории графов.

Особенно приятно то, что в данном случае Россия - родина пусть и не новой породы слонов, но зато нового научного направления!

Графы: определения и примеры


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

Неориентированные графы


Граф - это двойка , где V - непустое множество вершин, а Е - множество ребер, соединяющих эти вершины попарно2). Две вершины, связанные между собой ребром, равноправны, и именно поэтому такие графы называются неориентированными: нет никакой разницы между "началом" и "концом" ребра.

Таблица 11.1.
Примеры неориентированных графов


Граф

Вершины

Ребра

Семья

Люди

Родственные связи

Город

Перекрестки

Улицы

Сеть

Компьютеры

Кабели

Домино

Костяшки

Возможность

Дом

Квартиры

Соседство

Лабиринт

Развилки и тупики

Переходы

Метро

Станции

Пересадки

Листок в клеточку

Клеточки

Наличие общей границы

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

Например, три графа на рис. 11.1 совпадают, а два графа на рис. 11.2 - различны.


Рис. 11.1.  Три способа изображения одного графа

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

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


Рис. 11.2.  Пример двух разных графов


Рис. 11.3.  Псевдограф

Любому ребру инцидентно ровно две вершины, а вот вершине может быть инцидентно произвольное количество ребер, это количество и определяет степень вершины. Изолированная вершина вообще не имеет инцидентных ей ребер (ее степень равна 0).

Две вершины называются смежными, если они являются разными концами одного ребра (иными словами, эти вершины инцидентны одному ребру). Аналогично, два ребра называются смежными, если они инцидентны одной вершине.

Путь в графе - это последовательность вершин (без повторений), в которой любые две соседние вершины смежны. Например, в графе, изображенном на рис. 11.1, есть два различных пути из вершины a в вершину с: adbc и abc.

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

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

Компонента связности - это максимальный связный подграф. В общем случае граф может состоять из произвольного количества компонент связности. Заметим, что любая изолированная вершина является отдельной компонентой связности. На рис. 11.4 изображен граф, состоящий из четырех компонент связности: [abhk], [gd], [c] и [f].

Длина пути - количество ребер, из которых этот путь состоит. Например, длина уже упомянутых путей adbc и abc (см. рис. 11.1) - 3 и 2 соответственно.


Рис. 11.4.  Несвязный граф

Говорят, что вершина v принадлежит k-му уровню относительно вершины u, если существует путь из u в v длиной ровно k ребер. Одна и та же вершина может относиться к разным уровням. Например, в графе, изображенном на рис. 11.1, относительно вершины a существует 4 уровня:

  • 0) a;

  • 1) b, d;

  • 2) b, d, c (пути adb, abd, abc);

  • 3) c (путь adbc).

Расстояние между вершинами u и v - это длина кратчайшего пути от u до v. Из этого определения видно, что расстояние между вершинами a и c в графе на рис. 11.1 равно 2.

Цикл - это замкнутый путь. Все вершины в цикле, кроме первой и последней, должны быть различны. Например, циклом является путь abda в графе на рис. 11.1.

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


Рис. 11.5.  Граф Эйлера

Гамильтонов граф - это граф, в котором существует путь или цикл (без повторений), содержащий все вершины графа (см. рис. 11.5; искомый цикл: abdfca).
  1   2   3   4   5   6

Похожие:

Лекция 11: Графы и деревья iconРабочая программа дисциплины "Теория конечных графов и ее приложения" Направление подготовки 010300. 62 «фиит»
Графы ориентированные и неориентированные. Изоморфизм графов. Маршруты, цепи, циклы. Деревья. Помеченные графы. Плоские и планарные...
Лекция 11: Графы и деревья iconПояснительная записка: Требования к студентам : курс «Дискретные математические модели»
ЕН. Ф. 01. Плоские графы; эйлеровы графы; гамильтоновы графы; орграфы; сетевые графики; сети Петри
Лекция 11: Графы и деревья iconЗанятие №30 Графы. Деревья. 25. 04. 09
Определение Граф называется связным если из любой его вершины по ребрам можно дойти до любой другой
Лекция 11: Графы и деревья iconНеобычные деревья Какие деревья не похожи на обычные?
Среди самых необычных африканские баобабы и родственные им австралийские бутылочные деревья. Необычайно раздутые стволы тех и других...
Лекция 11: Графы и деревья iconВ вопроснике просьба только пометить указанный ниже номер графы. Не указывайте полного названия графы

Лекция 11: Графы и деревья iconЗанятие Деревья. Двудольные, эйлеровы и гамильтоновы графы >36. Составьте коды для данных деревьев: Т
Завуч школы должен составить расписание одного учебного дня для одного класса (все 4 предмета в расписании должны быть разные) с...
Лекция 11: Графы и деревья iconОбрабатываемые объекты: цепочки символов, числа, списки, деревья, графы
В примерной программе основного общего образования по информатике и информационным технологиям на раздел Алгоритмы и исполнители...
Лекция 11: Графы и деревья iconЛекции Содержание лекции Курсовая работа 1 01. 09 1 0 3
Деревья (леса) и бинарные деревья: определения, спецификация, соответствие лесов и бинарных деревьев
Лекция 11: Графы и деревья iconЛекции Содержание лекции Курсовая работа 1 01. 09 1 0 3
Деревья (леса) и бинарные деревья: определения, спецификация, соответствие лесов и бинарных деревьев
Лекция 11: Графы и деревья iconИспользование квадро-деревьев
Квадро-деревья это деревья с полустепенью исхода(out-degree) То есть у каждого узла может быть до 4 сыновей
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org