Algoritmo per elencare i cicli di un grafo non orientato
Salve a tutti, sto facendo un progettino implementativo del calcolo del polinomio cromatico di un grafo G non orientato.
Ho deciso di implementarlo utilizzando la formula di H. Whitney:
dove t="numero di colori" e n="numero vertici del grafo G" e dn,k è così definito:
dn,k = numero di sottoinsiemi di lati di ordine n-k che non contengono circuiti spezzati
L' "algoritmo" dovrebbe essere a grandi linee il seguente:
- dare un ordinamento arbitrario agli archi di G
- elencare i circuiti (cicli) di G
- togliere ad ogni circuito l'arco più grande (secondo l'ordine dato precedentemente)
- quello che si ottiene è l'insieme dei circuiti spezzati di G
- successivamente è facile calcolare il numero dn,k
il punto in cui mi sono incagliato è proprio quello di trovare (/realizzare) un algoritmo per identificare ed elencare tutti i circuiti presenti nel grafo per poi utilizzarli secondo l'algoritmo. Sapreste consigliarmene uno? non so proprio dove sbattere la testa -.-'
Cercando qualche informazione ho letto che molti consigliano di utilizzare il DFS (depth first search) "modificato"....ma non ho ancora capito quel "modificato"
Confido in voi matematici
Grazie in anticipo per l'aiuto.
Ho deciso di implementarlo utilizzando la formula di H. Whitney:
dove t="numero di colori" e n="numero vertici del grafo G" e dn,k è così definito:
dn,k = numero di sottoinsiemi di lati di ordine n-k che non contengono circuiti spezzati
L' "algoritmo" dovrebbe essere a grandi linee il seguente:
- dare un ordinamento arbitrario agli archi di G
- elencare i circuiti (cicli) di G
- togliere ad ogni circuito l'arco più grande (secondo l'ordine dato precedentemente)
- quello che si ottiene è l'insieme dei circuiti spezzati di G
- successivamente è facile calcolare il numero dn,k
il punto in cui mi sono incagliato è proprio quello di trovare (/realizzare) un algoritmo per identificare ed elencare tutti i circuiti presenti nel grafo per poi utilizzarli secondo l'algoritmo. Sapreste consigliarmene uno? non so proprio dove sbattere la testa -.-'
Cercando qualche informazione ho letto che molti consigliano di utilizzare il DFS (depth first search) "modificato"....ma non ho ancora capito quel "modificato"
Confido in voi matematici
Grazie in anticipo per l'aiuto.
Risposte
Scusa per "polinomio cromatico" intendi il problema della "k-colorazione" di un grafo ?
Leggendo le condizioni del tuo problema o è una riduzione ad un altro problema, o è tutt'altro.
Leggendo le condizioni del tuo problema o è una riduzione ad un altro problema, o è tutt'altro.
"ham_burst":
Scusa per "polinomio cromatico" intendi il problema della "k-colorazione" di un grafo ?
Leggendo le condizioni del tuo problema o è una riduzione ad un altro problema, o è tutt'altro.
Ciao, a essere sincero non so se il problema della "k-colorazione" di un grafo sia la stessa cosa ma per polinomio cromatico intendo una funzione p(G,t) che da il numero di possibili "buone"colorazioni di un grafo; dove per "buone colorazioni" intendo ogni vertice del grafo deve avere un colore diverso dai propri vertici adiacenti.
In ogni caso il problema su cui mi sono bloccato è il trovare un algoritmo che mi permetta di elencare tutti i cicli all'interno di un generico grafo G....e fino ad ora non ho avuto successo
up pls
bhe la tua descrizione è esattamente la k-colorazione.
Ma il tuo problema come è descritto mi sembra una sua riduzione (riduzione dei problemi NP se conosci).
Se rimaniamo solo sulla tua richiesta, senza guardare le altre condizoni, si possono fare queste considerazioni:
- per essere un ciclo (per pignoleria sarebbe un "circuito semplice" per i grafi non orientati) deve avere almeno 3 nodi. Questo penso sia banale.
- un ciclo deve avere tutti nodi distinti tranne il primo=ultimo.
- un ciclo è un cammino con gli estremi uguali.
perciò si può fare una visita DFS con condizione di tenere in considerazione, che invece di eliminare i nodi già visitati, contare e poi eliminare.
Dal punto di vista algoritmico al momento non ho molta voglia, ma devi pensare prima a cosa fare poi pensi al come.
Se vuoi un algoritmo terra-terra, e guardi subito all'implementazione, io tempo fa pensai così: se usi una matrice di adiacenza, essendo simmetrica, puoi già subito lavorare lì, essendo che se esiste un ciclo sulle diagonali c'è tutto 1.
Se ricordo bene è così, basta che provi, se c'è un elenco di 1, c'è un ciclo. La complessità è alta tipo un $O(n^3)$ perciò non è il massimo
intanto mi è venuto in mente questo, prova a pensarci, cmq domani guardo qualcosa di meglio è interessante questo problema, anche se è un problema conosciuto prova a googlare e vedrai
Ma il tuo problema come è descritto mi sembra una sua riduzione (riduzione dei problemi NP se conosci).
Se rimaniamo solo sulla tua richiesta, senza guardare le altre condizoni, si possono fare queste considerazioni:
- per essere un ciclo (per pignoleria sarebbe un "circuito semplice" per i grafi non orientati) deve avere almeno 3 nodi. Questo penso sia banale.
- un ciclo deve avere tutti nodi distinti tranne il primo=ultimo.
- un ciclo è un cammino con gli estremi uguali.
perciò si può fare una visita DFS con condizione di tenere in considerazione, che invece di eliminare i nodi già visitati, contare e poi eliminare.
Dal punto di vista algoritmico al momento non ho molta voglia, ma devi pensare prima a cosa fare poi pensi al come.
Se vuoi un algoritmo terra-terra, e guardi subito all'implementazione, io tempo fa pensai così: se usi una matrice di adiacenza, essendo simmetrica, puoi già subito lavorare lì, essendo che se esiste un ciclo sulle diagonali c'è tutto 1.
Se ricordo bene è così, basta che provi, se c'è un elenco di 1, c'è un ciclo. La complessità è alta tipo un $O(n^3)$ perciò non è il massimo
intanto mi è venuto in mente questo, prova a pensarci, cmq domani guardo qualcosa di meglio è interessante questo problema, anche se è un problema conosciuto prova a googlare e vedrai
"bytec0d3":[mod="dissonance"]Non fare UP prima di 24 ore dall'ultimo post. Vedi regolamento (clic) 3.4. In una stanza così poco affollata poi non c'è davvero nessuna ragione di comportarsi così.[/mod]
up pls
Ciao ham_burst, prima di tutto grazie mille per l'interessamento
Allora ho cercando un po ma ho trovato sempre DFS applicato a grafi orientati e non riesco ad adattarlo ai non orientati.
Per quanto riguarda un algoritmo "alternativo" ne ho abbozzato uno...ma non è assolutamente il massimo!
Lo spiego con un esempio che faccio prima:
- Il grafo è rappresentato con una lista di adiacenza quindi ad esempio:
1 | 2 3
2 | 1 3 4
3 | 1 2
4 | 2
parto dal primo vertice e ragiono in questo modo:
- 1->2 ciclo={1,2}
- 2->1 non va bene perchè è il precedente, array rimane invariato ciclo={1,2}
- 2->3 non è già presente nell'array, quindi ok. ciclo={1,2,3}
- 3->1 1 non è il precedente ma sopratutto è il primo elemento dell'array. ciclo={1,2,3,1} array completato
- così facendo continuo a creare le altre combinazioni possibili e ad ogni array completato controllo che non sia già stato creato (stessi elementi ma posizioni diverse); così da avere, in questo esempio, le seguenti combinazioni:
1) {1,2,3,1} OK
2) {1,3,2,1} NO (già presente)
3) {2,1,3,2} NO (già presente)
4) {2,3,1,2} NO (già presente)
5) {2,4} NO (impossibile continuare dato che il vertice 4 è collegato solo al vertice 2)
6) {3,1,2,3} NO (già presente)
7) {3,2,1,3} NO (già presente)
8) {4,2} NO (impossibile continuare dato che il vertice 4 è collegato solo al vertice 2)
come vedi non è assolutamente un algoritmo "intelligente" ma sembra funzionare....
@dissonance:
scusa, non avevo letto il regolamento
Allora ho cercando un po ma ho trovato sempre DFS applicato a grafi orientati e non riesco ad adattarlo ai non orientati.
Per quanto riguarda un algoritmo "alternativo" ne ho abbozzato uno...ma non è assolutamente il massimo!
Lo spiego con un esempio che faccio prima:
- Il grafo è rappresentato con una lista di adiacenza quindi ad esempio:
1 | 2 3
2 | 1 3 4
3 | 1 2
4 | 2
parto dal primo vertice e ragiono in questo modo:
- 1->2 ciclo={1,2}
- 2->1 non va bene perchè è il precedente, array rimane invariato ciclo={1,2}
- 2->3 non è già presente nell'array, quindi ok. ciclo={1,2,3}
- 3->1 1 non è il precedente ma sopratutto è il primo elemento dell'array. ciclo={1,2,3,1} array completato
- così facendo continuo a creare le altre combinazioni possibili e ad ogni array completato controllo che non sia già stato creato (stessi elementi ma posizioni diverse); così da avere, in questo esempio, le seguenti combinazioni:
1) {1,2,3,1} OK
2) {1,3,2,1} NO (già presente)
3) {2,1,3,2} NO (già presente)
4) {2,3,1,2} NO (già presente)
5) {2,4} NO (impossibile continuare dato che il vertice 4 è collegato solo al vertice 2)
6) {3,1,2,3} NO (già presente)
7) {3,2,1,3} NO (già presente)
8) {4,2} NO (impossibile continuare dato che il vertice 4 è collegato solo al vertice 2)
come vedi non è assolutamente un algoritmo "intelligente" ma sembra funzionare....
@dissonance:
scusa, non avevo letto il regolamento
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo