Rappresentazione grafica algoritmo per partita Nodi

Question

Dato un grafo orientato, ciò è un algoritmo che può utilizzare per trovare un sottoinsieme casuale dei suoi bordi in modo che ogni nodo ha esattamente un ingresso ed esattamente un bordo di uscita?

Ad esempio, questo potrebbe essere il grafico mi viene data:

E questo sarebbe un grafico di uscita valido:

Questo è valido perché:

• contiene tutti i nodi sull'ingresso grafico
• Tutti i suoi bordi sono anche sul grafico ingresso
• Ogni nodo ha esattamente un bordo lasciandolo ed un bordo venendo ad esso (e che non può essere lo stesso bordo, nessun cicli sono ammessi, ogni nodo deve collegarsi ad almeno un altro nodo).

Se non v'è alcuna soluzione possibile che deve essere rilevato.

C'è un algoritmo efficiente per risolvere questo?

Grazie!

Answer 1

E 'un problema di copertura del nodo cicli. Esso può essere risolto come massimo abbinamenti in bipartito grafici .

In breve:

1. Split ogni nodo due, ciascuno in una partizione di un grafico, in modo che tutti i bordi vanno da P1 a P2 partizione partizione. Nel campione, i nodi A e D si trasformerà in nodi A1, D1 a partizione P1 e A2, D2 in P2. Bordo A-D si trasformerà in A1-D2, e D-A -. A D1-A2
2. poi trovare un accoppiamento massimo, esistono alcuni algoritmi.
3. Quindi unire i nodi indietro, e hai ottenuto una copertura ciclo.

Answer 2

Si sta cercando di scomporre un grafico in una serie di cicli.

Questo collegamento che punta a algoritmo di Tarjan per la ricerca di cicli in un grafico.

Dopo di che, avrete bisogno di un po 'di strategia di ricerca (alcune scelte di cicli non possono portare a una soluzione dato i vostri vincoli).