Representación gráfica de algoritmo para nodos del partido

Question

Dado un grafo dirigido, lo que es un algoritmo que puede utilizar para encontrar un subconjunto aleatorio de sus bordes para que cada nodo tiene exactamente una entrada y exactamente un arco de salida?

Por ejemplo, esto podría ser la gráfica estoy dado:

Y esto sería un gráfico de salida válida:

Esto es válido, ya que:

• Contiene todos los nodos en la entrada gráfica
• Todos sus bordes también están en el gráfico de entrada
• Cada nodo tiene exactamente un borde dejando un borde y viniendo a él (y que no puede ser el mismo borde, no hay bucles están permitidos, cada nodo tiene que conectarse a al menos otro nodo).

Si no hay una posible solución que debe ser detectado.

¿Existe un algoritmo eficiente para resolver esto?

Gracias!

Answer 1

It's a node cycles coverage problem. It can be solved as Maximum matchings in bipartite graphs.

In short:

1. Split every node in two, each in one partition of a graph, so that all edges go from partition P1 to partition P2. In your sample, nodes A and D will turn into nodes A1, D1 in partition P1 and A2, D2 in P2. Edge A-D will turn into A1-D2, and D-A - to D1-A2.
2. Then find a maximum matching, some algorithms exist.
3. Then merge the nodes back, and you got a cycle coverage.

Answer 2

You're trying to decompose a graph into a set of cycles.

This link points you to Tarjan's algorithm for finding cycles in a graph.

After that, you'll need some search strategy (some choices of cycles may not lead to a solution given your constraints).