Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Представления графов






Из определения графа следует, что каждый граф G=(V, E) можно задать, непосредственно перечислив его множество вершин V и множество ребер E. Однако такое представление неудобно для решения многих задач о графах. Например, чтобы проверить наличие ребра между двумя вершинам и, придется, вообще говоря, просмотреть все множество E. Хорошее представление, по крайней мере, должно позволить легко переходить от вершины к ее соседу и перечислять всех ее соседей.

В этом параграфе мы рассмотрим три разных способа представления графов, которые более эффективны при решении типичных для теории графов задач.

Матрица (таблица) смежности

Определение 9.5. Матрицей смежности ориентированного (или неориентированного) графа G=(V, E) с n вершинам и V= { v1,..., vn} называется булева матрица AG размера n x n с элементами

Это представление позволяет легко проверять наличие ребер между заданными парами вершин. Для поиска всех соседей, в которые ведут ребра из вершины vi, необходимо просмотреть соответствующую ей i -ю строку матрицы AG, а чтобы найти вершины, из которых ребра идут в vi, необходимо просмотреть ее i -ый столбец. Требуемая для AG память - по порядку n2 битов - не может быть уменьшена для графов, у которых " много" ребер. Но для разреженных графов с числом ребер существенно меньшим по порядку n2 в матрице смежности много " ненужных" нулей. Для таких графов более эффективными могут оказаться другие представления.

Матрица (таблица) инцидентности

Определение 9.6. Матрицей инцидентности ориентированного (или неориентированного) графа G=(V, E) с n вершинам и V= { v1,..., vn} и m ребрами E={e1,..., em} называется матрица BG размера n x mс элементами

Таким образом, в матрице инцидентности BG любому ребру ej = (vi, vk) соответствует j -ый столбец, в котором в i -ой строке стоит 1, а в k -ой - -1. Ребра -петли выделяются числом 2. Для проверки наличия ребра между двумя вершинам и vi и vk требуется просмотреть i -ю и k -ую строки BG, поиск всех соседей вершины требует просмотра соответствующей строки. Если m > > n, то это требует существенно больше времени, чем при использовании матрицы смежности. Поэтому при практическом решении задач на графах матрица инцидентности почти не используется.


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

mylektsii.su - Мои Лекции - 2015-2024 год. (0.006 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал