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

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

Постройте Эйлеров и Гамильтонов циклы или докажите .pdf

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

Условие

Постройте матрицы смежности и инциденций графа. Постройте Эйлеров и Гамильтонов циклы или докажите, что соответствующий цикл не существует. Найдите хроматическое число и оптимальную раскраску вершин графа. 15. Ребра 12, 14, 23, 24, 25, 26, 35, 45.

Нужно полное решение этой работы?

Решение

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

Изобразим наш граф:
Строим матрицу смежности:
aij=1, если вершины i,j-смежны0, иначе
Тогда матрицасмежности A(G):
AG=010100101111010010110010011100010000
Матрица инциденций B(G)имеет размерность 6х8 по числу вершин и ребер графа соответственно и строится следующим образом:
bij=1, если ребро i и вершина j инидентны0, иначе
Тогда матрица инциденций B(G) (единицы в столбце указывают, какие вершины соединены данным ребром):
BG=110000001011110000100010010100010000101100000100
Эйлеров цикл – цикл, проходящий через каждое ребро один раз . Эйлеров цикл в графе существует тогда и только тогда, когда выполнены два условия: граф связан и степень каждой вершины четна. Т.к. в матрице смежности нашего графа есть строки с нечетным числом единиц, то не у всех вершин четные степени, а, значит, Эйлеров цикл построить нельзя.
Гамильтоновым называется цикл, проходящий ровно один раз через каждую вершину графа

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

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

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