Матрицы графов (стр. 2 из 2)
Сумма строк матрицы B(G) является нулевой строкой.
Любая строка матрицы B(G) является линейной комбинацией остальных строк.
Ранг матрицы B(G) равен p-1.
Определение 5. Матрицей смежности ребер неориентированного графа G называется квадратная матрица A*(G) = [a*ij] порядка q, элементы a*ij которой равны единице, если ребра ei и ej смежны, и нулю – в противном случае.
Для графа, изображенного на рис. 1, матрица смежности ребер имеет вид
| e1 | e2 | e3 | e4 | e5 | e6 | e7 | e8 | e9 | e10 | |||
| e1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | ||
| e2 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | ||
| e3 | 1 | 1 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ||
| e4 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | ||
| e5 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | ||
| A*(G) | = | e6 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 |
| e7 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | ||
| e8 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | ||
| e9 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | ||
| e10 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
Очевидно, что матрица A*(G) смежности ребер неориентированного графа обладает теми же свойствами, что и матрица A(G) смежности вершин графа G. Таким образом, можно найти граф G*, матрица смежности вершин которого равна матрице A*(G) смежности ребер графа G.
G(X,E) ® A*(G) º A(G*) ® G*.
Такой граф называется реберным, или сопряженным графом G. На рис. 3 приведен реберный граф (для неориентированного графа, показанного на рис.1).
Матрицы смежности вершин и смежности ребер неориентированного графа могут быть получены из матрицы инцидентности следующим образом.
Обозначим через BT(G) матрицу, полученную транспонированием матрицы инцидентности B(G). Квадратная матрица A = B(G)×BT(G) порядка p будет равна матрице смежности вершин графа, а квадратная матрица А* = BT(G)×B(G) порядка q – матрице смежности ребер.
По матрице смежности ребер графа (орграфа) всегда можно определить ребра графа (дуги орграфа) как пары инцидентных им вершин, а для графов с параллельными ребрами (дугами), кроме того, и кратности ребер (дуг).
Однако если ребра (дуги) были пронумерованы, то восстановить их номера по матрице смежности невозможно. В этом смысле матрица инцидентности оказывается более информативной, чем матрица смежности, поскольку позволяет получить полную информацию о ребрах (дугах), включая их нумерацию.
Рассмотренные в этом параграфе матрицы графов играют большую роль в теории графов. Существуют и другие матрицы графов, однако их роль менее значительна.
ЛИТЕРАТУРА
1. Белоусов А.И., Ткачев С.Б. Дискретная математика: Учебник для ВУЗов / Под ред. В.С. Зарубина, А.П. Крищенко.– М.: изд-во МГТУ им. Н.Э. Баумана, 2001.– 744 с. (Сер. Математика в техническом университете; Вып XIX).
2. Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика.– М.: Наука, Физматлит, 2000.– 544 с.– ISBN 5-02-015238-2.
3. Петрова В.Т. Алгебра и геометрия. Учебник для ВУЗов: в 2 ч.– М.: Гуманит. изд. центр ВЛАДОС.– ч. 1 – 312 с., ч. 2 – 344 с. ISBN 5-691-00077-2. ISBN 5-691-00238-4 (I), ISBN 5-691-00239-2 (II).
4. Зарубин В.С. Математическое моделирование в технике: Учеб. для ВУЗов / Под ред. В.С. Зарубина, А.П. Крищенко.– М.: Изд-во МГТУ им. Н.Э. Баумана, 2001.– 496 с. (Сер. Математика в техническом университете; вып. XXI, заключительный).