Схема Эйлера в ориентированном графе - PullRequest
Новая
       40

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

1 голос
/ 19 апреля 2020

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

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

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

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

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

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

1 Ответ

0 голосов
/ 21 апреля 2020

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

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

Ваша версия ориентированного графа «Просто подключен» немного отличается от этих определений, но это связано с сильной связностью. Любой ориентированный граф может иметь свои узлы, разбитые на сильно связанные компоненты (SCCs), группы узлов, которые все могут достигать друг друга. Эти сильно связанные компоненты образуют группу обеспечения доступности баз данных, где каждый сильно связанный компонент является узлом и существует ребро от одного S CC к другому, если один из узлов в первом S CC имеет ребро для узла во втором S CC.

Ваше определение «только что подключенного» графа можно затем закрепить так:

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

Обратите внимание, что «только что подключенный» подразумевает слабое подключение, но не наоборот.

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

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

...