Vystředěný strom - Centered tree

Vlevo vystředěný strom, vpravo dvoustranný. Čísla ukazují výstřednost každého uzlu.

V diskrétní matematice, a centrovaný strom je strom pouze s jedním centrum a dvoustranný strom je strom se dvěma středy.

Vzhledem k tomu, graf, výstřednost vrcholu proti je definována jako největší vzdálenost z proti na jakýkoli jiný vrchol. A centrum grafu je vrchol s minimální excentricitou. Graf může mít libovolný počet středů. Nicméně, Jordan (1869) dokázal, že u stromů existují pouze dvě možnosti:

  1. Strom má přesně jeden střed (vystředěné stromy).
  2. Strom má přesně dvě centra (dvoustranné stromy). V tomto případě jsou obě centra sousedící.

Důkazem této skutečnosti je například Knuth.[1]

Poznámky

  1. ^ (Knuth 1997 ), s. 387 a str. 589

Reference

  • Jordan, Camille (1869). „Sur les assemblages de lignes“. Journal für die reine und angewandte Mathematik (francouzsky). 70 (2): 185–190.
  • Knuth, Donald E. (1997). Umění počítačového programování, Svazek 1: Základní algoritmy (3. vyd.). Addison-Wesley Professional. ISBN  0-201-89683-4.

externí odkazy