Generare un grafico diretto con n cicli

Question

Desidero generare un grafico diretto che contenga esattamente la quantità specificata di cicli con la rispettiva lunghezza. Ad esempio, il grafico dovrebbe contenere:

 
2 cycles of the size 3 
1 cycle of the size 5 

• Fa un tale algoritmo esiste già? In caso contrario, quale sarebbe il tuo approccio per risolvere questo problema? In particolare, si forniscono i seguenti parametri:

  1. il numero di vertici (ad esempio, 15)
  2. il numero di componenti (ad esempio, 2)
  3. i cicli che devono essere nel grafico (ad esempio , {3-ciclo, 3-ciclo, 5-ciclo})

• ho trovato solo diversi algoritmi (ad esempio, Tarjan) in grado di rilevare cicli in grafici esistenti. Pensi che sia possibile utilizzare anche gli algoritmi di rilevamento del ciclo su generare grafici con una quantità specifica di cicli?

Answer 1

Un algoritmo greedy che potrebbero fallire su alcuni casi, ha bisogno di revisione tra pari.

Si noti che, se abbiamo un ciclo di una certa lunghezza k:

1 -> 2 -> 3 -> ... -> k -> 1 

Possiamo fare un altro ciclo della stessa lunghezza con l'introduzione di un unico altro nodo:

1 -> 2 -> 3 -> ... -> k -> 1 
k' -> 1 -> 2 -> ... -> k - 1 -> k' 

O un ciclo della stessa lunghezza - 1:

Questo può andare avanti per rever introducendo sempre un nuovo nodo e collegandolo ad altri due nodi in un ciclo iniziale abbastanza grande.

Quindi, se puoi permetterti un numero infinito di nodi, fai questo, partendo dal ciclo più grande che ti serve.

Se si deve lavorare con un numero fisso di nodi, dovremmo cercare di ridurre al minimo il numero di nodi utilizzati per la costruzione dei cicli richiesti. Eventuali nodi rimanenti possono essere facilmente aggiunti in modo da non formare alcun ciclo.

Inizia con la più grande ciclo nuovamente:

1 -> 2 -> ... -> k -> 1 

non aggiungendo alcuna più nodi, si può ottenere da questo seguente:

1. k lunghezza 2 cicli: 2 -> 1, 3 -> 2, ... 1 -> k.

2. k - 2 lunghezza 3 cicli: 3 -> 1, 4 -> 2, ..., k -> k - 2.

3. In generale, k - p + 1 cicli p cicli.

Nessuno di questi genererà cicli aggiuntivi. Quindi l'intero algoritmo sarà:

1. Costruisci il tuo ciclo più grande richiesto.

   1.1. Se ne esiste più di uno, costruisci di più aggiungendo un singolo nuovo nodo per ciascuno. Si noti che ciò influisce sulla procedura descritta per la creazione di cicli più piccoli rispetto a quelli grandi non aggiungendo nuovi nodi, poiché si ottiene un nuovo ciclo di una certa dimensione. Ci saranno alcune sovrapposizioni, quindi non si può semplicemente raddoppiare il numero di soluzioni. Per quanto ne so, aumenta solo il numero di 1.

2. Costruisci i tuoi cicli minori non aggiungendo nuovi nodi.

3. se non fatto costruire i cicli necessari:

   3.1. Se hai ancora nodi, usali.

   3.2. Se non si dispone di nodi rimasti, emettere no solution.

4. se fatto cicli di costruzione:

   4,1. Se hai ancora nodi, aggiungili come lista collegata da qualche parte in modo che non ti infastidiscano.

   4.2. Se non ci sono nodi rimasti, hai finito.