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

Орграф задан матрицей смежности A(G) .pdf

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

Условие

Орграф задан матрицей смежности A(G). Требуется: а) нарисовать граф; б) выделить компоненты сильной связности; в) в ассоциированном графе найти эйлерову цепь (или цикл) AG=100001000001011100010101001000010111

Решение

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

А) Изобразим граф на плоскости
б) Для того чтобы найти компоненты сильной связности, найдем матрицу достижимости
A2G=110111010111011101010111011100011111, A3G=111111011111011111011111011101011111, A4G=A5(G)=111111011111011111011111011111011111
A*G=sign100000010000001000000100000010000001+100001000001011100010101001000010111+110111010111011101010111011100011111+111111011111011111011111011101011111+111111011111011111011111011111011111=111111011111011111011111011111011111
Найдем матрицу сильной связности:
SD=A*G& A*TG=111111011111011111011111011111011111&100000111111111111111111111111111111=100000011111011111011111011111011111
Множество вершин первой компоненты сильной связности: {1}
Множество вершин второй компоненты сильной связности: {2,3,4,5,6}
в) Построим ассоциированный граф
Запишем степени вершин:
deg1=1, deg2=3,deg3=3,deg4=3,deg5=2,deg6=4
В ассоциированном графе имеется более двух вершин нечетной степени (это вершины 1,2,3,4), значит, эйлеровой цепи в данном графе не существует.

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

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

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