|
Читайте также: |
Во многих задачах графы удобно задавать матрицами. Пусть граф G=(V, E) – граф c n вершинами и m ребрами, причем вершины и ребра занумерованы.
Матрицей инцидентности называется матрица A(G) размера m 
n, элементы которой имеют вид
Матрицей смежности графа называется матрица B(G) n n, которая имеет вид
B(G) i j = числу ребер, инцидентных одновременно i –той и j – ой вершинам.
П р и м е р.Задана матрица инцидентности графа (цифрами обозначены вершины, буквами – ребра графа).
. Требуется:
a) Восстановить граф по матрице инцидентности;
b) Выяснить, является ли граф связным;
c) Построить для данного графа матрицу смежности
Р е ш е н и е.
2
a) e1 e5
1 e2 4
e4
e6
e3
3
h
Более компактным описанием графа по сравнению с матрицей инцидентности является список ребер.
Ребро e1 инцидентно вершинам 1 и 2.
Ребро e2 инцидентно вершинам 1 и 2.
Ребро e3 инцидентно вершинам 1 и 3.
Ребро e4 инцидентно вершинам 2 и 3.
Ребро e5 инцидентно вершинам 2 и 4
Ребро h инцидентно вершинам 4 и 4
b).Граф является связным.
c) Матрица смежности имеет вид.
Дата добавления: 2015-07-20; просмотров: 66 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Элементы теории графов. | | | Некоторые общие понятия теории графов. |