Теоретические сведения

Рассмотрим конечный граф G=(V, E), где |V|=n, |E|=m.

Способами аналитического представления графа являются:

1. Матрица инциденций.

Ориентированный граф задается прямоугольной матрицей B(n´m), элементы которой определяются по правилу:

Кроме нерационального использования памяти (n×m единиц) недостатком этого способа представления является неудобный доступ к информации. Например, для ответа на вопросы:

а) существует ли ребро (дуга) (vi, vj);

б) к каким вершинам ведут ребра (дуги) из вершины vi

требуется, в худшем случае, перебор n×m элементов, т.е. порядка n×m шагов алгоритма.

2. Матрица смежности.

Элементы квадратной матрицы A(n´n) определяются следующим образом:

Проверка существования ребра (дуги) (vi, vj) осуществляется за один шаг, в отличие от матрицы инциденций, однако, проверка свойств графа на основе такого представления требует, в худшем случае, порядка n2 шагов алгоритма.

3. Матрица ребер.

Она представляет собой матрицу размером m´2, каждая строка которой содержит вершины инцидентные i-му ребру (i-ой дуге). Для работы со взвешенными графами нужно добавить к матрице столбцы, соответствующие весам ребер (дуг).

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

4. Списки инцидентности.

Для каждой вершины viÎV создается список записей, характеризующих ребра (дуги), инцидентные этой вершине.

Таким образом, это представление использует объем памяти порядка (n+m), поиск вершины смежной с данной требует порядка (n+m) шагов, проверка свойств графа осуществляется за число шагов порядка. Поэтому остановимся подробнее на этом способе задания графа.








Дата добавления: 2017-02-20; просмотров: 311;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.005 сек.