2. Матричное представление графов и сетей
Правила заполнения матрицы направленного графа:
Если нумерация вершин не задана для данного графического образа сети, то для единообразия и сопоставимости матриц мы будем определять ее следующим образом. Двигая линейку вертикально слева направо, нумеруйте вершины по мере их попадания на вертикальную линию сверху вниз.
Номер ячейки матрицы определяется парой чисел:
(номер строки i; номер столбца j) = (i; j)
Число, стоящее в ячейке (i; j) матрицы МК, означает число К-шаговых связей из вершины i в вершину j.
Если рассматривается сеть (двустороннее направление связей между любыми вершинами), то матрицы любой степени МК будут иметь симметричный вид относительно главной диагонали. Стрелочки связей в этом случае не рисуют.
2.1. По данной матрице связей графа восстановите его графический образ с обозначением вершин и направлением связей. Можно ли рассматривать его как сеть?
|
n1 |
n2 |
n3 |
n4 |
n5 |
|
n1 |
0 |
1 |
0 |
1 |
0 |
|
n2 |
1 |
0 |
0 |
0 |
1 |
|
n3 |
0 |
0 |
0 |
1 |
0 |
|
n4 |
1 |
0 |
1 |
0 |
0 |
|
n5 |
0 |
1 |
0 |
0 |
0 |
2.2. Восстановите графический образ, является ли он сетью?
|
n1 |
n2 |
n3 |
n4 |
n5 |
|
n1 |
0 |
1 |
1 |
1 |
0 |
|
n2 |
1 |
1 |
0 |
0 |
0 |
|
n3 |
0 |
0 |
1 |
1 |
0 |
|
n4 |
1 |
0 |
0 |
0 |
0 |
|
n5 |
0 |
0 |
0 |
0 |
1 |
2.3. Проверьте соответствие матрицы и направленного графа
|
n1 |
n2 |
n3 |
n4 |
n5 |
n1
n2
n4
n5
n3 |
n1 |
|
|
|
|
|
|
n2 |
|
|
|
|
|
|
n3 |
|
|
|
|
|
|
n4 |
|
|
|
|
|
|
n5 |
|
|
|
|
|
2.4. Заполните матрицу представления заданного орграфа
|
n1 |
n2 |
n3 |
n4 |
n5 |
n1
n5
n34
n4
n2 |
n1 |
|
|
|
|
|
|
n2 |
|
|
|
|
|
|
n3 |
|
|
|
|
|
|
n4 |
|
|
|
|
|
|
n5 |
|
|
|
|
|