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 dall'albero, eseguire BFS per trovare un nodo che è più lontano da esso e quindi eseguire BFS su quel nodo. La maggiore distanza dal secondo BFS produrrà il diametro.

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

Tutte le idee sarebbe molto apprezzato ...

Answer 1

Chiamiamo l'endpoint trovato dai primi BFS x. Il passaggio cruciale sta dimostrando che la x trovata in questo primo passo sempre "funziona", cioè che è sempre all'estremità di un percorso più lungo. (Si noti che in generale ci può essere più di un percorso ugualmente più lungo.) Se possiamo stabilire questo, è semplice vedere che un BFS con radice a x troverà un nodo il più lontano possibile da x, che deve quindi essere un totale il percorso più lungo

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

Osservare che, nel percorso univoco tra uev, deve esserci un vertice più alto (più vicino alla radice) h. Ci sono due possibilità: o h è sul percorso dalla radice di BFS a x, o non lo è. Mostra una contraddizione mostrando che in entrambi i casi, il percorso u-v può essere fatto almeno altrettanto a lungo sostituendo un segmento di percorso in esso con un percorso verso x.

[EDIT] In realtà, potrebbe non essere necessario trattare i 2 casi separatamente dopo tutto. Ma spesso trovo più semplice interrompere una configurazione in più (o anche molti) casi e trattarli separatamente. Qui, il caso in cui h è sul percorso dalla radice di BFS a x è più facile da gestire e dà un indizio per l'altro caso.

[EDIT 2] Tornando a questo più tardi, ora mi sembra che i due casi che devono essere considerati sono: (i) il percorso uv interseca il percorso dalla radice a x (ad qualche vertice y, non necessariamente nel punto più alto del percorso uv h); e (ii) non è così. Abbiamo ancora bisogno di h per dimostrare ogni caso.

Answer 2

Ho intenzione di lavorare fuori j_random_hacker's hint. Lascia che sia s, t una coppia al massimo distante. Sia u il vertice arbitrario. Abbiamo una schematica come

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

dove x è la giunzione di s, t, u.

Supponiamo che v sia un vertice al massimo distante da u. Se lo schema ora sembra

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 la disuguaglianza perché d(u, t) = d(u, x) + d(x, t) e d(u, v) = d(u, x) + d(x, v). Esiste un caso simmetrico in cui v si collega tra s e x anziché tra 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 media, e v appartiene ad una coppia massimamente distante.

Answer 3

Ecco un modo alternativo di vedere le cose:

supponga G = (V, E) è un non vuoto, albero finita con vertice impostato V e set di spigoli E.

Si consideri il seguente algoritmo:

1. Let conteggio = 0. Che tutti i bordi in E inizialmente incolore. Let C inizialmente uguale a V.
2. consideri il sottoinsieme V 'di V contenente tutti i vertici con esattamente un bordo incolore:
   • se V' è vuoto poi lasciare d = conteggio * 2 e fermarsi.
   • se V 'contiene esattamente due elementi poi il colore reciproco (non colorato) bordo verde, lasciate conteggio d = * 2 + 1, e stop.
   • altrimenti, V 'contiene almeno tre vertici; procedere come segue:
3. Incremento conteggio di uno.
4. Rimuovere tutti i vertici da C che non hanno bordi non colorati.
5. Per ciascun vertice in V con due o più spigoli non colorati, ricolorare ciascuno dei suoi bordi verdi in rosso (alcuni vertici potrebbero avere zero tali bordi).
6. Per ogni vertice in V ', colorare il suo bordo non colorato verde.
7. Torna al passaggio (2).

Questo fondamentalmente colora il grafico dalle foglie verso l'interno, segnando i percorsi con la distanza massima da una foglia in verde e contrassegnando quelli con distanze inferiori solo in rosso. Nel frattempo, i nodi di C, al centro, con breve distanza massima di una foglia sono sbucciato via fino C contiene solo uno o due nodi con la più grande distanza massima di una foglia.

Per costruzione, tutte semplici sentieri vertici foglia al loro centro più vicino vertice che attraversano solamente bordi verdi sono la stessa lunghezza (conteggio), e tutti gli altri percorsi semplici da un vertice foglia al suo centro più vicino vertice (traslazione a almeno un bordo rosso) sono più corti. Può inoltre essere dimostrato che

• questo algoritmo termina sempre nelle condizioni date, lasciando ogni bordo G colore rosso o verde, e lasciando C con uno o due elementi.
• a terminazione algoritmo, d è il diametro di G, misurata in bordi.
• Dato un vertice v in V, le massima lunghezza semplici percorsi in G partendo v sono esattamente quelle che contengono contenere tutti i vertici del centro, terminare una foglia, e attraversa solo i bordi verdi tra il centro e il punto finale lontano. Questi vanno da v, attraverso il centro, a una delle foglie più lontane dal centro.

---

Ora consideriamo il vostro algoritmo, che potrebbe essere più pratico, alla luce di quanto sopra. Partendo da ogni vertice v, v'è esattamente un semplice percorso p da tale vertice, che termina in un centro di vertice, 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 semplici percorsi massime in G avente v come punto finale tutti hanno la forma dell'unione di p con un semplice percorso dal centro al foglio attraversare bordi solo verdi.

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