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

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

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

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

Определение 9.5. Матрицей смежности ориентированного (или неориентированного) графа G=(V,E) с n вершинами V= { v₁, …, v_n} называется булева матрица A_G размера n × n с элементами

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

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

Определение 9.6. Матрицей инцидентности ориентированного (или неориентированного) графа G=(V,E) с n вершинами V= { v₁, …, v_n} и m ребрами E={e₁, …, e_m} называется матрица B_Gразмера n × m с элементами

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