Преобразовать неориентированный граф в ориентированный граф с определенным условием
Дается неориентированный граф, имеющий M ребер и N вершин, мы должны преобразовать каждое ребро из uv в u->v или v->u так, чтобы степень каждой вершины была четной. Какой метод или алгоритм подходит для наименьшей сложности времени.
3 ответа
Вот другой подход - я не думаю, что вы хотите выполнить исключение по Гауссу с n=100000, поэтому я выполнил поиск в сети для связанных проблем.
Если у графа более одного связного компонента, вы можете рассмотреть их отдельно, поэтому давайте предположим, что у него есть только один.
Создайте связующее дерево на своем компоненте и отметьте одну из вершин как корень этого дерева. Зафиксируйте направления ребер не на остовном дереве, как вам нравится. Возьмите каждую вершину по одному, начиная с листьев, имея дело со всеми потомками вершины, прежде чем иметь дело с этой вершиной. Для каждой вершины выберите направление ребра дерева до его родителя, чтобы его собственная степень была четной, и игнорируя последствия для его родителя. Каждая вершина, кроме корня, имеет ребро, соединяющее ее с родителем, поэтому для каждой вершины, кроме корня, вы можете быть уверены, что ее степень четна.
Когда вы дойдете до корня, у вас не останется ребер с направлением, которое вы можете изменить, поэтому вы не можете изменить его степень, которая является четной или нечетной. Если это даже все хорошо - каждая вершина имеет даже степень. Если это нечетно, у вас есть одна вершина с нечетной степенью, а все остальные с четной степенью, поэтому сумма всех степеней нечетна. Но сумма всех степеней - это просто число ребер в графе, которое вы не можете изменить. Если число ребер в графе нечетное, всегда будет хотя бы одна вершина с нечетной степенью, и проблема все равно будет невозможной.
Вы можете сделать что-то вроде этого -> Единственное изменение, которое вам нужно будет сделать, это сделать MST, прежде чем делать топологическое
https://www.geeksforgeeks.org/assign-directions-to-edges-so-that-the-directed-graph-remains-acyclic/
Дайте каждому ребру произвольное направление и создайте переменную (в настоящее время неизвестную), которая говорит, нужно ли изменить направление этого ребра.
Для каждой вершины ребро поступает в соответствии с x или 1^x, где x является неизвестным для этого ребра, а 1 ^ x равно 1 XOR x = NOT x, в зависимости от того, было ли первоначальное направление, назначенное этому ребру, к этой вершине или нет.
Для каждой вершины число входящих ребер является четным, даже если результат сложения вместе результатов этих уравнений равен 0 - это то же самое, что сказать, что результат сложения их вместе mod 2 равен 0.
Таким образом, у вас есть система линейных уравнений mod 2, которая аналогична двоичным линейным уравнениям, и вы можете использовать исключение Гаусса, чтобы увидеть, есть ли решение.
(Там может быть более теоретический способ сделать это, но я думаю, что это решение).