Ориентированный граф G = (V, X) с множеством вершин V = {1,2,3,4,5,6,7} задан списком дуг X: X = {(1,4),(2,1),(4,3),(4,5),(2,6),(2,6),(7,1),(7,6),(3,2), (5,4), (3,4),(2,2),(6,2),(5,5)};
1) Постройте реализацию графа G.
2) Постройте матрицу инцидентности графа G.
3) Постройте матрицу смежностиG.
4) Задайте соответствующий неориентированный граф матрицей смежности
5) Укажите степени вершин полученных графов, найдите цикломатическое число графа G.
1) Построение реализации графа G:
Для этого нам потребуется нарисовать вершины и дуги, соединяющие эти вершины в соответствии с заданным списком дуг X.
1---->4
| ^
v |
2--->1 6
| / ^
v / |
7--->6|
| ^ |
v | |
3-- 2
| ^
v |
5--->4
|
v
5
2) Построение матрицы инцидентности графа G:
Матрица инцидентности - это квадратная матрица размером V x X, где V - количество вершин, а X - количество дуг. Каждый столбец матрицы соответствует ребру, а каждый столбец - вершине. Значение элемента матрицы равно 1, если вершина и ребро инцидентны, и равно 0 в противном случае.
Для заданного графа G:
1 2 3 4 5 6 7
------------------
1 | - 1 0 1 0 0 -
2 | 1 - 1 0 0 1 -
3 | 0 1 - 1 0 0 -
4 | 0 0 1 - 1 0 -
5 | 0 0 0 1 - 0 -
6 | 0 0 0 0 1 - -
7 | 1 0 0 0 0 1 -
3) Построение матрицы смежности графа G:
Матрица смежности - это квадратная матрица размером V x V, где V - количество вершин. Значение элемента матрицы равно 1, если вершины смежные, и равно 0 в противном случае.
Для заданного графа G:
1 2 3 4 5 6 7
------------------
1 | - 1 0 1 0 0 1
2 | 1 - 1 0 0 1 0
3 | 0 1 - 1 0 0 0
4 | 1 0 1 - 1 0 0
5 | 0 0 0 1 - 0 0
6 | 0 1 0 0 0 - 1
7 | 1 0 0 0 0 1 -
4) Соответствующий неориентированный граф матрицей смежности:
В неориентированном графе матрица смежности является симметричной относительно главной диагонали. Каждый элемент матрицы соответствует наличию ребра между соответствующими вершинами и принимает значение 1, если ребро есть, и 0, если ребра нет.
Отсутствуют петли в графе.
1 2 3 4 5 6 7
------------------
1 | -