Схема Эйлера в ориентированном графе

Question

Как проверить, является ли ориентированный граф эйлеровым?

1) Все вершины ненулевой степени принадлежат одной компоненте сильной связности.

2) In-степень равна исходящей степени для каждой вершины. Источник: geeksforgeeks

Вопрос: В данных двух условиях строгое ли первое? Я имею в виду, почему действительно необходимо, чтобы граф был "сильно" связным графом? Что делать, если граф просто связан?

Я узнал, что условие 1 можно заменить на слабосвязный граф. Опять же, что, если граф просто связан, а не слабо связан?Буду рад увидеть несколько примеров.

PS: Учтите, что условие 2 всегда выполняется в приведенном выше обсуждении. И под словом "только что связанный" я подразумеваю, что в графе существует вершина, из которой достижимы все остальные вершины.

Answer 1

Это интересный вопрос. Насколько мне известно, не существует стандартизованного значения термина "связанный" в контексте ориентированного графа. Два общих понятия связности в ориентированном графе:

• сильная связность, где для любой пары узлов u и v существует путь от u к v и путь от v к u, и
• слабая связность, когда подключается неориентированный граф, сформированный игнорированием направленности стрелок.

Ваша версия ориентированного графа, являющегося "только что связанным", немного отличается от этих определений, но связана с сильной связностью. Узлы любого ориентированного графа могут быть разделены на сильно связанные компоненты (SCC), группы узлов, которые могут достигать друг друга. Эти компоненты с сильной связью образуют группу DAG, где каждый компонент с сильной связью является узлом, и есть ребро от одного SCC к другому, если один из узлов в первом SCC имеет ребро к узлу во втором SCC.

Ваше определение графа как "только что подключенного" может быть закреплено следующим образом:

• "только что подключено": группа DAG SCC имеет исходный узел, который может достигать всех остальных узлов.

Обратите внимание, что "только что подключено" означает слабое подключение, но не наоборот.

Оказывается, в этом случае, если у вас есть граф, в котором степень каждого узла совпадает с его исходящей степенью, тогда, если граф "просто связан", то он имеет схему Эйлера. Если ваш график "просто связан", значит, он слабо связан. Затем мы собираемся утверждать, что любой слабо связный граф со степенями, равными исходящим степеням, также должен быть сильно связным. Чтобы увидеть это, выберите любой SCC в DAG SCC без входящих ребер. Любое ребро, входящее в любой из узлов в этом SCC, должно происходить из этого SCC. В результате, если мы пройдем через каждый узел в SCC и сложим количество ребер, выходящих из этого узла, это общее количество будет соответствовать количеству входящих ребер в каждый узел в SCC. Но тогда, поскольку сумма степеней выхода узлов равна сумме исходящих степеней узлов, может 'Тогда t будет любыми ребрами, начинающимися в этом SCC и заканчивающимися другим, поскольку учитываются все ребра. Следовательно, этот SCC не имеет выходящих из него ребер.

Мы только что показали, что любой исходный SCC не должен иметь границ с другими SCC. А поскольку в некотором исходном SCC есть узел, который может достигнуть каждого узла, это означает, что в графе нет других SCC, поэтому граф имеет только один SCC и, следовательно, сильно связан.