Dijametar drveta

-Grafovi-

Website maintained by ntrifunovic Theme by mattgraham modified by ntrifunovic

Sta je dijametar drveta ?

Dijametar drveta je najduze rastojanje izmedju dva cvora u drvetu

Kako mozemo odrediti dijametar drveta ?

  1. Izaberimo slucajano neki cvor A
  2. Odredimo cvor koji je nadjudaljeniji od cvora A, neka je to cvor B
  3. Odredimo cvor koji je nadjudaljeniji od cvora B, neka je to cvor C
  4. Dijametar drveta je jednak rastojanju izmedju cvorova B i C

Dokaz

Ovo tvrdjenje se moze dokazati svodjenjem na apsurd tvrdjenja da najduzi put u drvetu ne pocinje u cvoru B.

comments powered by Disqus