Ориентированный граф задан матрицей смежности. Можно ли для данного графа построить Эйлеров маршрут?

Для того чтобы определить, можно ли построить Эйлеров маршрут в ориентированном графе, необходимо проверить выполнение двух условий:

1. Связность: Граф должен быть связным (если рассматривать его как неориентированный, то все вершины с ненулевой степенью должны принадлежать одной компоненте связности).
2. Степени вершин: Для каждой вершины $v$ графа её полустепень захода $d_{in}(v)$ должна быть равна её полустепени исхода $d_{out}(v). Примечание: Если мы ищем Эйлеров путь (а не цикл), то допускается, чтобы для двух вершин $u$ и $v$ выполнялось $d_{out}(u) - d_{in}(u) = 1$ и $d_{in}(v) - d_{out}(v) = 1$, а для всех остальных вершин $d_{in} = d_{out}$.

Шаг 1: Анализ степеней вершин

Матрица смежности $...