М
Молодежь
К
Компьютеры-и-электроника
Д
Дом-и-сад
С
Стиль-и-уход-за-собой
П
Праздники-и-традиции
Т
Транспорт
П
Путешествия
С
Семейная-жизнь
Ф
Философия-и-религия
Б
Без категории
М
Мир-работы
Х
Хобби-и-рукоделие
И
Искусство-и-развлечения
В
Взаимоотношения
З
Здоровье
К
Кулинария-и-гостеприимство
Ф
Финансы-и-бизнес
П
Питомцы-и-животные
О
Образование
О
Образование-и-коммуникации
ВладВишня
ВладВишня
11.06.2020 09:12 •  Математика

Ориентированный граф 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 | -
4,8(63 оценок)
Проверить ответ в нейросети
Новые ответы от MOGZ: Математика
logo
Вход Регистрация
Что ты хочешь узнать?
Спроси Mozg
Открыть лучший ответ