Ho un grafico con un ciclo Euleriano e nessun Cicli hamiltoniani . Vorrei dividere questo grafico in cicli semplici.
I bordi non possono essere ripetuti in cicli semplici.
Come si può fare?
Ho un grafico con un ciclo Euleriano e nessun Cicli hamiltoniani . Vorrei dividere questo grafico in cicli semplici.
I bordi non possono essere ripetuti in cicli semplici.
Come si può fare?
Segui il tuo ciclo Euleriano. Ogni volta che arrivi a un vertice in cui sei stato in precedenza, la parte tra le due visite è un ciclo semplice. Smontalo e salvalo nella lista dei cicli semplici, segna tutti i vertici usati in quel modo, eccetto quello che sei ora, come non visitato. Continua fino a quando tutti i bordi sono stati usati.
Per trovare un ciclo di Eulero, il metodo di Hierholzer è efficiente.
Se non conosci già il ciclo di Eulero, utilizza l'algoritmo di Hierholzer .
(Modificato per mostrare come trovare ogni ciclo semplice nella rete, non solo quelli contenuti nella CE. È questo che voleva l'interrogante?)
Supponendo che tu conosca già un ciclo Euleriano, quindi segui semplicemente il ciclo Euleriano. Ogni volta che visiti un nodo che hai già visitato, hai trovato un ciclo . Dovresti controllare che sia un ciclo semplice assicurandoti che non ci siano altre ripetizioni in questo ciclo. Ad esempio
A -> B -> C -> D -> B -> E -> A
A ... A è un ciclo e B -> B è un ciclo, ma solo quest'ultimo è un ciclo semplice
Inoltre, due semplici cicli potrebbero condividere molti nodi e bordi tra loro. Ad esempio,
A -> X -> B -> Y -> A -> Z -> B
A ... A e B ... B sono semplici cicli che condividono nodi e bordi tra loro.
= Ricerca di ogni ciclo semplice nel grafico =
Ogni ciclo semplice sarà contenuto con il Ciclo Euleriano (CE), o sarà distribuito in tutta la CE. Ad esempio di cosa intendo per 'spread out', possiamo vedere il semplice ciclo A -> B -> C -> A all'interno di questo EC:
D -> A ==> B -> E -> F -> B ==> C ==> A -> D
dove ho evidenziato alcuni bordi rendendoli più lunghi. Questi bordi fanno parte del ciclo semplice. Quindi, dato e EC e l'obiettivo di trovare un ogni ciclo semplice, è una questione di enumerazione di tutti i sottoinsiemi dei bordi nell'EC.
Ma puoi accelerare notevolmente le cose con una semplice osservazione. Se decidi di includere A->B nel tuo ciclo semplice candidato , allora il lato successivo che decidi di includere deve iniziare da B e puoi saltare molti dei seguenti bordi. Questo dovrebbe rendere più facile ignorare molte parti grandi dell'albero di ricerca.
In effetti, penso che questo algoritmo sia praticamente l'efficienza ottimale per trovare tutti i cicli semplici. Qualche idea?
Questo problema è difficile quanto trovare un ciclo Hamiltoniano. Non penso che tu possa usare il fatto che il grafico ha un ciclo Euleriano.
Puoi usare l'ovvio algoritmo O(n!) : per ogni permutazione dei nodi, passa alla lista e vedi se il percorso che fai è un partizionamento in grafici semplici.
Ma probabilmente puoi fare meglio usando la programmazione dinamica.
Leggi altre domande sui tag algorithms graph