Преобразовать неориентированный граф в ориентированный граф с определенным условием

Question

приведен неориентированный граф с M ребрами и N вершинами. Мы должны преобразовать каждое ребро из uv в u-> v или v-> u так, чтобы степень каждой вершины была четной. Какой метод или алгоритм подходит для наименьшего временисложность.

Answer 1

Вот другой подход - я не думаю, что вы хотите выполнить исключение по Гауссу с n = 100 000, поэтому я выполнил поиск в Интернете связанных проблем.

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

Постройте остовное дерево на вашем компоненте и отметьте одну из вершин как корень этого дерева.Зафиксируйте направления ребер не на остовном дереве, как вам нравится.Возьмите каждую вершину по одному, начиная с листьев, имея дело со всеми потомками вершины, прежде чем иметь дело с этой вершиной.Для каждой вершины выберите направление ребра дерева до его родителя, чтобы его собственная степень была четной, и игнорируя последствия для его родителя.Каждая вершина, кроме корня, имеет ребро, соединяющее ее с родителем, поэтому для каждой вершины, кроме корня, вы можете быть уверены, что ее степень четна.

Когда вы приходите к корню, у вас нет ребероставив направление, которое вы можете изменить, так что вы не можете изменить его степень, которая является четной или нечетной.Если это даже все хорошо - каждая вершина имеет даже степень.Если это нечетно, у вас есть одна вершина с нечетной степенью, а все остальные с четной степенью, поэтому сумма всех степеней нечетна.Но сумма всех степеней - это просто число ребер в графе, которое вы не можете изменить.Если число ребер в графе нечетное, всегда будет хотя бы одна вершина с нечетной степенью, и проблема все равно будет невозможна.

Answer 2

Вы можете сделать что-то вроде этого -> Единственное изменение, которое вам нужно будет сделать, это сделать MST перед выполнением топологического

https://www.geeksforgeeks.org/assign-directions-to-edges-so-that-the-directed-graph-remains-acyclic/

Answer 3

Дайте каждому ребру произвольное направление и создайте переменную (в настоящее время неизвестную), которая говорит, нужно ли изменить направление этого ребра.

Для каждой вершины ребро поступает в соответствии с x или 1 ^ xгде x является неизвестным для этого ребра, а 1 ^ x равно 1 XOR x = NOT x, в зависимости от того, было ли исходное направление, назначенное этому ребру, к этой вершине или нет.

Для каждой вершины числовходящих ребер, даже если результат ксерокопирования результатов этих уравнений равен 0 - это то же самое, что сказать, что результат сложения их вместе мод 2 равен 0.

Таким образом, у вас есть система линейныхуравнения mod 2, то же самое, что и двоичные линейные уравнения, и вы можете использовать исключение Гаусса, чтобы увидеть, есть ли решение.

(Возможно, существует более теоретический способ сделать это, но ядумаю, что это решение).