OliForum Matematico

Sia dato un albero T (grafo connesso aciclico). Tra i nodi di T ce n'è uno cattivo, chiamiato BAD. Il nodo BAD è assolutamente anonimo e non possiamo distinguerlo dagli altri guardando solamente la struttura di T. Fortunatamente ci è dato anche un "oracolo" che, interrogato su un nodo x, svela se x = BAD oppure qual è il primo arco da seguire nel cammino che congiunge x e BAD. Dimostrare che possiamo scoprire l'identità di BAD interrogando l'oracolo al più O(log n) volte.

Hint:

A cosa si riduce il problema se l'albero è una catena?

Forza, immaginate che in quel nodo ci sia un gattino rimasto intrappolato e voi dovete salvarlo, non è certamente un hint ma forse vi sentirete più motivati...

ricerca binaria no?

Dato un nodo v, chiamo $ ~ f(v) $ il rapporto tra l'ordine della più grande componente connessa di T \ v ed n.

Ora dimostrare che in ogni albero c'è un nodo con $ ~ f(v) \le \frac 12 $. Ma è semplice: parto da un nodo a caso, e seguo il figlio con la discendenza più grande finchè ad un certo punto devo trovare un nodo buono.

Poi, trovato questo, chiedo all'oracolo se c'è per caso un gatto, ed itero il procedimento.

Ogni albero ha un "centro" o un "bicentro" (che sono i nodi che hai chiamato "buoni"). Osservato questo, la ricerca si riduce ad una ricerca binaria.
rand è sempre fonte di bei problemi.

Che vi sia piaciuto o meno, la fonte non sono io. L'ho presa dal sito di E.Demaine, era in una delle lezioni del corso di strutture dati che tiene al mit. Viene usata per illustrare un'applicazione giocattolo del fatto che ogni albero contiene un nodo separatore (o centro).

una cosa pero': d'accordo la ricerca binaria pero' come si fa a trovare il centro in tempo costante senza un preprocessing?

Ricontrolla il testo, non c'è scritto che devi impiegarci tempo O(log n), c'è solo scritto che puoi chiedere indicazioni al più O(log n) volte.

ah e' vero non avevo notato!

Pardon, ho detto una fesseria anch'io: i nodi di edriv ovviamente non sono centri e bicentri, ma i due metodi (quello di edriv e quello dei centri) risolvono entrambi il problema. Quello dei centri però è più efficiente.

A questo punto son curioso di sapere che è un centro...

Pag. 9 del Diestel.
Un nodo di un grafo è centrale se minimizza la massima distanza da un altro nodo del grafo. Si dimostra che ogni albero ha un solo centro, oppure due centri adiacenti.