[Grafi] Ordinamento Topologico

[xMauri94]

Ciao a tutti.
Avevo questo quesito: Dati due grafi orientati che hanno lo stesso insieme di vertici, ma due insiemi distinti di archi, come faccio a capire se esiste un ordinamento topologico del primo che é anche ordinamento topologico del secondo, in tempo quadratico sulla cardinalitá di vertici?

I grafi sono rappresentati come liste di adiacenza.

[apatriarca]

Puoi trovare quell'ordinamento topologico se
\[ x \prec_A y \implies x \prec_B y \vee \text{ $x$ e $y$ non comparabili} \quad \wedge \quad x \prec_B y \implies x \prec_A y \vee \text{ $x$ e $y$ non comparabili} \]
dove \(\prec_A\) e \(\prec_B\) sono le due relazioni d'ordine parziale. Alternativamente puoi studiare il grafo unione. Se è possibile trovare un ordinamento topologico per uno dei due grafi che vada bene anche per l'altro vuol dire che l'ordinamento topologico è anche compatibile con l'unione. Per verificare se esiste quell'ordinamento puoi per esempio verificare che il grafo unione sia aciclico.

[xMauri94]

Il mio problema stà proprio nel capire se, fatto un ordinamento topologico sul G1, questo vada bene anche sul G2.. e se non va bene, come faccio ad essere certo che non ne esiste nessun altro in G1 che vada bene per G2?

[apatriarca]

Ti ho già fornito un criterio per stabilire se tale ordinamento esiste. Provare l'esistenza di quell'ordinamento topologico equivale a provare l'esistenza di un ordinamento topologico nel grafo unione (un grafo cioè in cui si prende l'unione dei due insiemi di archi).

[xMauri94]

Grazie per le risposte, ci ho davvero pensato ma non sono riuscito a scrivere un algoritmo che verificasse la condizione che mi hai scritto..

[apatriarca]

Sarebbe utile ci spiegassi in cosa esattamente stai incontrando difficoltà. Non hai capito che cosa sia il grafo unione? Non hai idea di come dimostrare che un grafo ammetta un ordinamento topologico (e equivalentemente che sia aciclico)? L'algoritmo può infatti essere scritto più o meno come segue:

def test(A, B):
    U = graph_union(A, B)
    return isDAG(U)

Ovviamente mancano l'implementazione di graph_union e isDAG. Ma se hai capito che cosa dovrebbero fare non sono difficili da definire.

[xMauri94]

Chiedo scusa per la poca chiarezza; non c'è bisogno di verificare che i grafi G1 e G2 siano aciclici, prendiamoli aciclici direttamente.

Si, il problema è calcolare il grafo unione, non ho trovato appunti al riguardo e sul mio libro non è menzionato. La condizione che mi hai specificato non riesco ad implementarla in un algoritmo, cioè io dovrei prendere due vertici di G1 x e y, vedere se x viene prima di y o y viene prima di x; fatto ciò, controllo lo stesso in G2? Cioè, controllo se x e y sono nella stessa posizione di come lo sono in G1? Credo che non sia così.

[xMauri94]

Sono un cretino.. hai completamente ragione, l'algoritmo potrebbe essere questo:

ALGO(G1, G2)
    LIST = NULL
    E3 = G1(E) U G2(E)
    G3 = <V, E3>
    LIST = TOPOLOGICAL(G3)
    IF (LIST) THEN
        RETURN TRUE
RETURN FALSE

Per giunta è in tempo $ O(V+max{E_1, E_2}) $ !

Grazie mille per l'aiuto e la pazienza! (P.s dimmi che ne pensi eh )

[apatriarca]

Direi che è quello che avevo in mente..

[xMauri94]

Volevo essere certo che fosse così, grazie mille ancora!