Граф Джи задан диаграммой 1)Составьте для него матрицу смежности 2) постройте матрицу и инцидентности 3) кажите степени вершин графа
Привет! Давайте шаг за шагом решим твою задачу по теории графов.
- Составление матрицы смежности
Матрица смежности графа – это квадратная матрица размером \(n \times n\), где \(n\) – количество вершин в графе. Значения в матрице указывают, есть ли ребро между парами вершин. Если есть, ставим 1, если нет – 0.
Для графа на картинке:
- Вершины \(V_1\) связаны с \(V_2\), \(V_4\), \(V_5\), \(V_6\).
- Вершины \(V_2\) связаны с \(V_1\), \(V_3\), \(V_5\), \(V_6\).
- Вершины \(V_3\) связаны с \(V_2\), \(V_4\), \(V_5\), \(V_6\).
- Вершины \(V_4\) связаны с \(V_1\), \(V_3\), \(V_5\), \(V_6\).
- Вершины \(V_5\) связаны с \(V_1\), \(V_2\), \(V_3\), \(V_4\).
- Вершины \(V_6\) связаны с \(V_1\), \(V_2\), \(V_3\), \(V_4\).
Таким образом, матрица смежности будет выглядеть так (вершины ведут отсчет от \(V_1\) до \(V_6\)):
| V1 | V2 | V3 | V4 | V5 | V6 | |
|---|---|---|---|---|---|---|
| V1 | 0 | 1 | 0 | 1 | 1 | 1 |
| V2 | 1 | 0 | 1 | 0 | 1 | 1 |
| V3 | 0 | 1 | 0 | 1 | 1 | 1 |
| V4 | 1 | 0 | 1 | 0 | 1 | 1 |
| V5 | 1 | 1 | 1 | 1 | 0 | 0 |
| V6 | 1 | 1 | 1 | 1 | 0 | 0 |
- Построение матрицы инцидентности
Матрица инцидентности – это матрица размером \(n \times m\), где \(n\) – количество вершин, а \(m\) – количество рёбер в графе. Для каждой вершины \(V_i\) и каждого ребра \(E_j\) в матрице стоит 1, если вершина инцидентна ребру, и 0 – в противном случае.
Учитывая, что у нас \(9\) ребер (обозначим их как \(x_1\) до \(x_9\)), матрица инцидентности для неориентированного графа будет выглядеть следующим образом:
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | |
|---|---|---|---|---|---|---|---|---|---|
| V1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| V2 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |
| V3 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 |
| V4 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
| V5 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
| V6 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 |
- Степени вершин графа
Степенью вершины в неориентированном графе называется количество рёбер, которые в ней сходятся. Для нашего графа:
- Степень \(V_1\) - \(4\) (ребра \(x_1, x_4, x_6, x_8\)).
- Степень \(V_2\) - \(4\) (ребра \(x_2, x_5, x_7, x_9\)).
- Степень \(V_3\) - \(4\) (ребра \(x_3, x_4, x_8, x_9\)).
- Степень \(V_4\) - \(4\) (ребра \(x_1, x_3, x_5, x_7\)).
- Степень \(V_5\) - \(4\) (ребра \(x_2, x_3, x_6, x_5\)).
- Степень \(V_6\) - \(4\) (ребра \(x_1, x_2, x_6, x_5\)).
Все вершины графа имеют степень \(4\), это достаточно легко проверить визуально, посчитав количество рёбер у каждой вершины.
Надеюсь, эта информация помогла тебе! Если возникнут ещё вопросы по графам или другим темам – обращайся!
