Основные понятия теории графов



Скачать 396.01 Kb.
страница1/5
Дата11.10.2012
Размер396.01 Kb.
ТипЛекция
  1   2   3   4   5
Лекция 7

Динамические структуры данных. Графы и их представление.

Основные операции.

Основные понятия теории графов


Граф (graph) – объект, состоящий из множества кружков (точек) и множество соединяющих их линий. Кружки (точки) называются вершинами графа (nodes), линии со стрелками – дугами (arcs), без стрелок – ребрами (edges). Т.е. граф – это пара G=(V,E), где V - множество вершин, а E - семейство пар ребер ei=(vi1, vi2), vij принадлежит V. Вершины графа можно использовать для представления объектов, а дуги — для отношений между объектами.

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

Граф, в котором направление линий принципиально (линии являются дугами) называется ориентированным (орграф). В отличие от ребер, дуги соединяют две неравноправные вершины: одна из них называется началом дуги (дуга из нее исходит), вторая - концом дуги (дуга в нее входит). Пример: G=(V,E): V={1, 2, 3, 4, 5}; E={(1,2), (1,5), (3,1), (5,2), (5,3), (5,4)}.

Граф, в котором направление линий не выделяется (все линии являются ребрами), называется неориентированным (две вершины равноправны, нет никакой разницы между "началом" и "концом" ребра).

Чаще всего рассматривают графы, в которых все ребра имеют один тип – либо ориентированные, либо неориентированные.

Две вершины v и u называются смежными, если они соединены ребром (дугой) е: e=(v,u). Смежные вершины называются граничными вершинами соответствующего ребра (дуги), а это ребро (дуга) - инцидентным соответствующим вершинам. Любому ребру инцидентно ровно две вершины, а вершине может быть инцидентно произвольное количество ребер.

Два ребра называются смежными, если они инцидентны одной вершине.

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


Мультигаф – из одной вершины в другую можно перейти разными способами (граф с кратными ребрами).

П
утем
называется последовательность вершин v1, v2, …, vn, для которой существуют ребра (или дуги в орграфе) v1 v2, v2v3, ..., vn-1 vn. Этот путь начинается в вершине v1 и, проходя через вершины v2, v3, ..., vn-1, заканчивается в вершине vn. Длина пути— количество дуг (ребер), составляющих путь, в данном случае длина пути равна n – 1. Путь называется простым, если все вершины на нем, за исключением, может быть, первой и последней, различны. Для неориентированного графа на рис.рисунка путями будут adbc и abc.

Замкнутый путь без повторяющихся ребер называется циклом (или контуром в орграфе); без повторяющихся вершин (кроме первой и последней) - простым циклом.

Полным называется граф, в котором проведены все возможные ребра. Для графа, имеющего n вершин, таких ребер будет n(n-1)/2.

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

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

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

Компонента связности – это максимальный связный подграф. В общем случае граф может состоять из произвольного количества компонент связности. Любая изолированная вершина является отдельной компонентой связности. Например, в приведённом ниже графе содержится 4 компоненты связности: abhk, gd, c, f.



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

Длина пути во взвешенном графе – это сумма весов ребер (дуг), из которых состоит путь.
  1   2   3   4   5

Похожие:

Основные понятия теории графов iconЭлементы теории графов
...
Основные понятия теории графов iconТеория графов и ее приложения
Основные понятия. Графы неориентированные и ориентированные. Способы задания графов. Матрицы смежности и инцидентности графа. Понятие...
Основные понятия теории графов iconОсновные понятия теории графов
Д. Кенига только в 1936 г., но многочисленные прикладные задачи и головоломки (которые, кстати, поддавались формулировкам в терминах...
Основные понятия теории графов iconОсновные понятия теории графов граф и его виды
Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год), хотя термин «граф» впервые ввел в 1936 году венгерский математик...
Основные понятия теории графов iconВопросы к экзамену Основные понятия теории графов (определение графа, виды графов, смежность, инцидентность, кратность ребер, степень вершины). Примеры
Способы задания графов. Матричный способ задания. Свойства матриц смежности и инцидентности. Привести примеры
Основные понятия теории графов iconЛекция 11: Графы и деревья
...
Основные понятия теории графов iconVi. Элементы теории графов. Основные понятия теории графов. Определение Графом
Определение Графом называется совокупность 2-х множеств Х и У. Х это множество точек, называемых вершинами графа, а у это множество...
Основные понятия теории графов iconМетодические указания к самостоятельным и семинарским занятиям по теории графов Москва 2006
Предназначены для решения задач по теории графов как при самостоятельном изучении теории графов, так и при решении задач на семинарах...
Основные понятия теории графов iconГрафы 4 Основные понятия теории графов 4
Пример Метод модульно-ориентированного анализа и проектирования сложных систем 10
Основные понятия теории графов iconОб орграфах, имеющих минимальные вершинные 1-расширения с малым количеством дополнительных дуг
В работе используются основные понятия теории графов в соответствии с работой [1]
Разместите кнопку на своём сайте:
ru.convdocs.org


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