Постройте матрицы смежности и инциденций графа. Бесплатный доступ к решению задач

Реферат.Справочник
Решенные задачи по высшей математике
Постройте матрицы смежности и инциденций графа

Постройте матрицы смежности и инциденций графа .pdf

Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥

Условие

Постройте матрицы смежности и инциденций графа. Постройте эйлеров и гамильтонов циклы или докажите, что соответствующий цикл не существует. Найдите хроматическое число и оптимальную раскраску вершин графа. Все графы имеют множество вершин {1, 2, 3, 4, 5, 6}. Ребра определяются в варианте задания. Для краткости они указываются без скобок и запятых. 14. Ребра 12, 14, 15, 23, 26, 35, 36, 45.

Решение

Потяни, чтобы посмотреть

Это неорграф. В графе 8 ребер и 6 вершин. Матрица смежности (если вершины соединены ребром, то на пересечении строки и столбца ставим 1, иначе 0):
1 2 3 4 5 6
1 0 1 0 1 1 0
2 1 0 1 0 0 1
3 0 1 0 0 1 1
4 1 0 0 0 1 0
5 1 0 1 1 0 0
6 0 1 1 0 0 0
Матрица инциденций (это матрица 6 х 8 - если вершина инцидентна ребру, то в соответствующую клетку ставим 1, иначе 0):
12 14 15 23 26 35 36 45
1 1 1 1 0 0 0 0 0
2 1 0 0 1 1 0 0 0
3 0 0 0 1 0 1 1 0
4 0 1 0 0 0 0 0 1
5 0 0 1 0 0 1 0
6 0 0 0 0 1 0 1 1
Построим граф:
Согласно теореме, доказанной Эйлером, эйлеров цикл существует тогда и только тогда, когда граф связный или будет являться связным, если удалить из него все изолированные вершины, и в нём отсутствуют вершины нечётной степени . В данном графе вершина 1 имеет нечетную степень, а именно 3, следовательно, эйлерова цикла в графе нет.
Гамильтоновым циклом ( путем ) называют простой цикл (путь), содержащий все вершины графа

50% задачи недоступно для прочтения

Переходи в Кампус, регистрируйся и получай полное решение

Получить задачу