De ce contează?
Imaginează o rețea de drumuri fără bucle: orașe legate prin șosele, dar fără niciun cerc — între oricare două orașe există exact un drum. Te întrebi: care sunt cei mai îndepărtați doi oameni din rețea, adică ce traseu are lungimea cea mai mare? Distanța dintre acele două capete este diametrul rețelei. Un arbore e exact o astfel de rețea fără bucle.
Intuiția
Un arbore are n noduri și n-1 muchii, fără cicluri — deci între oricare două
noduri există un drum unic. Diametrul este lungimea celui mai lung astfel de
drum, adică numărul maxim de muchii care leagă două noduri. Capetele lui sunt
mereu două frunze, iar drumul „se îndoaie” într-un singur nod — strămoșul lor
comun cel mai de jos.
Lema capătului: pornește un BFS (sau DFS) din orice nod s; cel mai
îndepărtat nod găsit, A, este mereu un capăt al unui diametru. Un al
doilea BFS, din A, ajunge cel mai departe exact la celălalt capăt B, iar
distanța A–B este diametrul. Schița argumentului: dacă A n-ar fi capăt,
drumul de la s la A s-ar putea „recombina” cu diametrul — fie se
intersectează cu el și atunci am prelungi diametrul dincolo de A
(contradicție cu maximalitatea lui), fie nu se intersectează și atunci am
construi, prin drumul unic dintre ele, un drum mai lung decât s–A
(contradicție cu alegerea lui A).