На этом шаге мы перечислим другие способы представления графов с помощью матриц.
Перечислим ещё несколько способов представления графов с помощью матриц:
(1) [1, с.30] матрица контрдостижимостей Q=[qij] определяется как матрица, элементы которой определяются так:
⌈ 1, если из вершины vj можно достичь вершину vi;
qij ⇔
⌊ 0, в противном случае.
Из приведённого определения следует, что Q=PT, где PT - матрица, транспонированная к матрице достижимости P;
(2) матрицей сильной связности S ориентированного графа G называется квадратная матрица порядка n с элементами
⌈ 1, если вершина vi достижима из vj;
sij ⇔ 1, если вершина vj достижима из vi;
⌊ 0, в противном случае.
Если обозначить P матрицу достижимости ориентированного графа G, то S=P&PT, где T - обозначение операции транспонирования матрицы.
Единицы i-й строки или i-го столбца матрицы сильной связности ориентированного графа G, соответствуют вершинам компоненты сильной связности ориентированного графа G, в которую входит вершина vi.
Напомним, что компонентом сильной связности в ориентированном графе называется такой его подграф, в котором любые две вершины взаимно достижимы и который не содержится в другом подграфе, удовлетворяющем этому условию;
(3) для произвольного неориентированного графа определим матрицу соседства рёбер C=[Cij], где
⌈ 1, если i-е и j-е ребро инцидентны;
Cij ⇔
⌊ 0, в противном случае (учтите, что Cii=0).
(4) цикломатическая матрица [2, с.113],
(5) матрица вложенности [2, с.113-114],
(6) матрица весов [3, с.354],
(7) матрица циклов [1, с.183-186],
(8) матрица Кирхгофа [4, с.30-31],
(9) матрица разрезов [5, с.144-149].
Замечание [5, с.158]. До сих пор мы занимались задачами построения и описания различных матриц, соответствующих графам. Обратная задача построения графа, соответствующего заданной матрице, в общем случае, или тривиальна, или весьма сложна. Первый случай легко проиллюстрировать с помощью матрицы, которая имеет в точности два единичных элемента в каждом столбце и нули во всех остальных местах.
Граф всегда можно построить, если заданная матрица является матрицей инцидентности. Задача построения графа по матрице циклов не является столь же простой в силу того, что ребро может принадлежать более чем двум циклам или двум разрезам.
(1)Кристофидес Н. Теория графов. Алгоритмический подход. - М.: Мир, 1978. - 432 с.
(2)Евстигнеев В.А. Применение теории графов в программировании. - М.: Hаука, 1985. - 352 с.
(3)Рейнгольд Э., Hивергельт Ю., Део H. Комбинаторные алгоритмы. Теория и практика. - М.: Мир, 1980. - 476 с.
(4)Лекции по теории графов / Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. - М.: Наука, 1990. - 384 с.
(5)Басакер Р., Саати Т. Конечные графы и сети. - М.: Наука, 1974. - 368 с.
На следующем шаге мы приведем перечень задач для самостоятельного решения.
