Prova di correttezza:Algoritmo per il diametro di un albero nella teoria dei grafi

Question

Per trovare il diametro di un albero posso prendere qualsiasi nodo dell'albero, eseguire BFS per trovare un nodo più lontano da esso e quindi eseguire BFS su quel nodo.La distanza maggiore dal secondo BFS produrrà il diametro.

Non sono sicuro di come dimostrarlo, però?Ho provato a utilizzare l'induzione sul numero di nodi, ma ci sono troppi casi.

Qualsiasi idea sarebbe molto apprezzata...

Answer 1

Chiamiamo l'endpoint trovato dal primo BFS X. Il passo cruciale sta dimostrando che la X trovata in questo primo passo "funziona sempre", cioè che è sempre ad una estremità di un percorso più lungo. (Si noti che in generale può esserci più di un percorso altrettanto più lungo.) Se possiamo stabilire questo, è semplice vedere che un BFS radicato su X troverà un nodo il più possibile da x, che deve quindi essere un complesso Percorso più lungo.

Suggerimento: Supponiamo (al contrario) che vi è un percorso più lungo tra due vertici u e v, nessuno dei quali è x.

Osservare che, sul percorso unico tra U e V, ci deve essere il vertice più alto (più vicino alla radice) h. Ci sono due possibilità: o h è sul percorso dalla radice del BF a X, o non lo è. Mostra una contraddizione mostrando che in entrambi i casi, il percorso U-V può essere effettuato almeno a lungo sostituendo un segmento del percorso in esso con un percorso a x.

[modifica] In realtà, potrebbe non essere necessario trattare i 2 casi separatamente dopo tutto. Ma spesso trovo più facile rompere una configurazione in numerosi casi (o anche molti) e trattati separatamente ciascuno. Qui, il caso in cui H è sul percorso dalla radice BFS a X è più facile da gestire e dà un indizio per l'altro caso.

[Modifica 2] Torna a questo in seguito, ora mi sembra che i due casi che devono essere considerati siano (i) il percorso UV interseca il percorso dalla radice a x ( a alcuni vertice y, non necessariamente al punto più alto del percorso UV H); e (ii) no. Abbiamo ancora bisogno di stendere ogni caso.

Answer 2

Vado ad allenarmi suggerimento di j_random_hacker.Permettere s, t essere una coppia massimamente distante.Permettere u essere il vertice arbitrario.Abbiamo uno schema simile

    u
    |
    |
    |
    x
   / \
  /   \
 /     \
s       t ,

Dove x è la giunzione di s, t, u (cioè.l'unico vertice che si trova su ciascuno dei tre percorsi tra questi vertici).

Supporre che v è un vertice massimamente distante da u.Se lo schema ora assomiglia

    u
    |
    |
    |
    x   v
   / \ /
  /   *
 /     \
s       t ,

Poi

d(s, t) = d(s, x) + d(x, t) <= d(s, x) + d(x, v) = d(s, v),

dove vale la disuguaglianza perché d(u, t) = d(u, x) + d(x, t) E d(u, v) = d(u, x) + d(x, v).C'è un caso simmetrico in cui v si attacca tra s E x invece che in mezzo x E t.

L'altro caso assomiglia

    u
    |
    *---v
    |
    x
   / \
  /   \
 /     \
s       t .

Ora,

d(u, s) <= d(u, v) <= d(u, x) + d(x, v)
d(u, t) <= d(u, v) <= d(u, x) + d(x, v)

d(s, t)  = d(s, x) + d(x, t)
         = d(u, s) + d(u, t) - 2 d(u, x)
        <= 2 d(x, v)

2 d(s, t) <= d(s, t) + 2 d(x, v)
           = d(s, x) + d(x, v) + d(v, x) + d(x, t)
           = d(v, s) + d(v, t),

COSÌ max(d(v, s), d(v, t)) >= d(s, t) da un argomento di media, e v appartiene ad una coppia massimamente distante.

Answer 3

Ecco un modo alternativo di vederlo:

Supponiamo G = ( V, E ) è un albero finito e non vuoto con insieme dei vertici V e set di bordi E.

Consideriamo il seguente algoritmo:

1. Permettere contare = 0.Lascia entrare tutti i bordi E inizialmente non colorato.Permettere C inizialmente essere uguale a V.
2. Considera il sottoinsieme V' Di V contenente tutti i vertici con esattamente un bordo non colorato:
   • Se V' è vuoto quindi let D = contare * 2 e fermati.
   • Se V' contiene esattamente due elementi, quindi colora di verde il loro bordo reciproco (non colorato), let D = contare * 2 + 1 e stop.
   • Altrimenti, V' contiene almeno tre vertici;procedi come segue:
3. Incremento contare per uno.
4. Rimuovi tutti i vertici da C che non hanno bordi incolori.
5. Per ogni vertice in V con due o più bordi non colorati, ricolora ciascuno dei suoi bordi verdi in rosso (alcuni vertici potrebbero avere zero bordi di questo tipo).
6. Per ogni vertice in V', colora di verde il suo bordo incolore.
7. Ritornare al passaggio (2).

Ciò colora sostanzialmente il grafico dalle foglie verso l'interno, contrassegnando i percorsi con la distanza massima da una foglia in verde e contrassegnando quelli con solo distanze più brevi in ​​rosso.Nel frattempo, i nodi di C, il centro, con la distanza massima più breve da una foglia vengono ridotti fino a C contiene solo uno o due nodi con la distanza massima maggiore da una foglia.

Per costruzione, tutti i percorsi semplici dai vertici delle foglie al vertice centrale più vicino che attraversano solo i bordi verdi hanno la stessa lunghezza (contare), e tutti gli altri percorsi semplici dal vertice di una foglia al vertice centrale più vicino (attraversando almeno un bordo rosso) sono più brevi.Ciò può anche essere dimostrato

• questo algoritmo termina sempre alle condizioni date, lasciando ogni bordo di G colorato di rosso o di verde e se ne va C con uno o due elementi.
• al termine dell'algoritmo, D è il diametro di G, misurato in bordi.
• Dato un vertice v In V, i percorsi semplici di lunghezza massima in G a partire da v sono esattamente quelli che contengono tutti i vertici del centro, terminano in una foglia e attraversano solo i bordi verdi tra il centro e l'estremità lontana.Questi vanno da v, attraverso il centro, fino a una delle foglie più lontane dal centro.

---

Consideriamo ora il tuo algoritmo, che potrebbe essere più pratico, alla luce di quanto sopra.Partendo da un vertice qualsiasi v, esiste esattamente un percorso semplice P da quel vertice, terminando con un vertice centrale e contenente tutti i vertici del centro (perché G è un albero e se ci sono due vertici in C quindi condividono un vantaggio).Si può dimostrare che i cammini semplici massimi in G avendo v come punto finale tutti hanno la forma dell'unione di P con un percorso semplice dal centro alla foglia attraversando solo i bordi verdi.

Il punto chiave per i nostri scopi è che il bordo in entrata dell'altro endpoint sia necessariamente verde.Pertanto, quando eseguiamo una ricerca per i percorsi più lunghi che iniziano da lì, abbiamo accesso a quelli che attraversano solo i bordi verdi dalla foglia attraverso (tutti i vertici del) centro fino a un'altra foglia.Questi sono esattamente i percorsi semplici di lunghezza massima in cui si trova G, quindi possiamo essere sicuri che la seconda ricerca rivelerà effettivamente il diametro del grafico.

Answer 4

1:procedureTreeDiameter(T)

2:pick an arbitrary vertex v where v∈V

3:u = BFS ( T, v )

4:t = BFS ( T, u )

5:return distance ( u, t )

Result: Complexity = O(|V|)