Ориентированные графы

  • 26 сент. 2011 г.
  • 5040 Слова
Ориентированные графы

Задан ориентированный граф G:
А={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
В={ (2,1), (3,1), (1,4), (6,4), (5,4), (5,3), (5,2), (7,2), (7,5), (7,6), (6,8), (9,6), (12,9), (8,12), (8,11), (8,7), (10,7), (10,11), (10,13), (14,11), (14,13), (12,14), (15,14)}

Требуется:
1) Построить геометрическую интерпретацию. Обозначить вершины и дугиграфа. Определить количество вершин и дуг.
2) Построить множество правых и левых инциденций.
3) Определить полу степени вершин исхода и захода.
4) Построить матрицы смежности и инциденций.

Решение:

Ориентированный граф G:

Рисунок 1.1-Ориентированный граф

1) Определим количество вершин (i) и дуг (b) графа.
i=15,b=24.
2) Определим множество правых (G+1(i)) и(G-1(i)) левых инциденций:
G+1 (i) - множество правых инциденций
G-1 (i) - множество левых инциденций
3) Определим полу степени вершин исхода и полу степени вершин захода для каждой из вершин: р+ (i) - полустепени вершин исхода р- (i) - полустепени вершин заходaТаблица 1.1. Множество правых и левых инциденции, полустепени вершин исхода и захода.

Таблица 1.1. Множество правых и левыхинциденции, полустепени вершин исхода и захода.
|I |G+1 (i) |G-1 (i) |р+ (i) |р- (i) |
|1 |{ 4 } |{ 2, 3 } |1 |2 |
|2 |{ 1 } |{ 5, 7 } |1 |2 |
|3|{ 1 } |{ 5 } |1 |1 |
|4 |Ø |{ 1, 5, 6 } |0 |3 |
|5 |{ 2, 3, 4 } |{ 7 } |3 |1 |
|6 |{ 4, 8 } |{ 7,9 } |2 |2 |
|7 |{ 2, 5, 6 } |{ 8, 10 } |3 |2 |
|8 |{ 7, 11, 12 } |{ 6 } |3 |1 |
|9 |{6} |{ 12 } |1|1 |
|10 |{ 7, 11, 13 } |Ø |3 |0 |
|11 |Ø |{ 8, 10, 14 } |0 |3 |
|12 |{ 9, 14} |{ 8 } |2 |1 |
|13 |Ø|{ 10, 14 } |0 |2 |
|14 |{ 11, 13} |{12, 15} |2 |2 |
|15 |{ 14 } |Ø |1 |0 |

Строим матрицы смежности (Si,j) и инциденции (Ri,j)Матрица смежности:

|[Si,j]= | |10 |20 |
|1 |{ 2, 7 } |6 |8 |
|2 |{ 3, 4 } |2|3 |
|3 |{ 4 } |1 |2 |
|4 |Ø |0 |1 |
|5...
tracking img