Quando posso essere sicuro che un grafo diretto è aciclico?

Naviga le tue risposte
4

La definizione per il grafo aciclico diretto è questa: "non c'è modo di iniziare da qualche vertice v e seguire una sequenza di spigoli che alla fine ritorna a v di nuovo."

Fin qui tutto bene, ma sto cercando di trovare alcune premesse che saranno più semplici da testare e che garantiranno anche che il grafico sia aciclico. Mi sono imbattuto in queste premesse, ma sono piuttosto semplici quindi sono sicuro che altre persone l'hanno capito in passato (o sono errate). Il problema è che non sono riuscito a trovare nulla relativo ai libri / online, quindi perché ho deciso di pubblicare questa domanda.

Premessa 1 : se tutti i vertici del grafico hanno un margine in entrata, il grafico non può essere aciclico. È corretto?

Premessa 2 : supponiamo che il grafico in questione abbia un vertice senza bordi in entrata. In questo caso, per avere un ciclo, almeno uno degli altri vertici dovrebbe avere due o più spigoli in entrata. È corretto?

    
posta Daniel Scocco 12.11.2011 - 13:46
fonte

2 risposte

4

Sì, entrambe le premesse descrivono le condizioni necessarie per un grafico ciclico. Tuttavia, escludono solo i grafici banali dall'analisi del ciclo e ti consigliamo di utilizzare uno degli algoritmi standard per assicurarti che un dato grafico sia effettivamente privo di cicli.

Esistono algoritmi abbastanza economici per il rilevamento di cicli nei grafici; se si sta eseguendo un ordinamento topologico su un grafico, ad esempio, si rileveranno cicli durante l'ordinamento. La scelta esatta dell'algoritmo dipende naturalmente dal tuo grafico (un bordo in uscita o multiplo?) E dai tuoi requisiti.

    
risposta data 12.11.2011 - 13:56
fonte
1

un test semplice sarebbe

  1. Sia S l'insieme di tutti i nodi senza percorsi in entrata (se non hai un ciclo)

  2. estrai un nodo P da S e aggiungi tutti i nodi direttamente accessibili a B e segna P attraversato,

    se uno dei nodi aggiunti è marcato attraversato hai un ciclo

  3. trova tutti i nodi in B con solo i percorsi in ingresso dai nodi contrassegnati attraversati e li aggiunge a S

  4. ripeti 2 e 3 finché S è vuoto

  5. se ci sono nodi che non sono attraversati hai un ciclo

Invariante di loop: S ha solo nodi che hanno dimostrato di non far parte di un ciclo (solo i percorsi in entrata formano quelli che non fanno parte di un ciclo)

questo è O (n * k) con k il numero medio di percorsi in uscita da un nodo

    
risposta data 12.11.2011 - 16:03
fonte

Leggi altre domande sui tag

Struttura dei dati simile a MaxHeap che supporta max AND min, anche decrementa (si decrementa) Di cosa ho bisogno per un server di database per Mobile-Apps? [chiuso]