Let
![k](/media/m/f/1/3/f135be660b73381aa6bec048f0f79afc.png)
A forest consists of rooted (i. e. oriented) trees. Each vertex of the forest is either a leaf or has two successors. A vertex
![v](/media/m/3/d/c/3dc3003f5c10543e81344921fc032374.png)
![u](/media/m/8/a/3/8a31c0578d8711cccb064f92f92e19ca.png)
![u_{0}=u](/media/m/3/e/d/3ed6b77040942c41605d990f54580f58.png)
![u_{1}](/media/m/5/d/f/5df4e150e249ce4904edd08dd9ea6b13.png)
![u_{2}](/media/m/2/5/e/25e427131a14388484dec3e2d6b408e7.png)
![u_{t-1}](/media/m/5/0/2/5025fac755ab7567415cf8215991f0a4.png)
![u_{t}=v](/media/m/a/c/a/aca0584d310620d4f0966b5f7efd3bc0.png)
![t>0](/media/m/5/9/d/59d561d110daec675e8271774a085dac.png)
![u_{i+1}](/media/m/c/3/1/c31959353bb0f08ce3facd3cc4fe6793.png)
![u_{i}](/media/m/c/0/a/c0af948d18b3887bc642cd0d368a09d3.png)
![i](/media/m/3/2/d/32d270270062c6863fe475c6a99da9fc.png)
![0\leq i\leq t-1](/media/m/c/a/5/ca5483f45b0ca356cce6978dcddc7cab.png)
![k](/media/m/f/1/3/f135be660b73381aa6bec048f0f79afc.png)
Prove that if the forest has
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
![\frac{n}{k+2}](/media/m/0/2/3/0234b3234d813898e98702e621b7544b.png)
Kliknite ovdje kako biste prikazali rješenje.
Označimo sa broj dinastičkih čvorova u šumi. Svakom dinastičkom čvoru
pridružimo skup sebe i njegovih potomaka
. (Potomak je extended succesor) Također, svakom dinastičkom čvoru pridružimo skup
. Za svaki čvor koji ima djecu, odaberimo lijevo i desno dijete tog čvora.
Na stablu vršimo sljedeći algoritam:
Dok postoji, odaberimo dinastički čvor takav da
(takav očito postoji ako nisu svi
prazni). Neka
. Iz skupa
uklonimo
, njegovo lijevo dijete i sve potomke tog djeteta, a iz skupa
desno dijete
i sve potomke tog djeteta. "Osvježimo" skupove
za sve
. Nakon ovoga, vrijedi
i
Također, primijetimo da
sadrži
, njegovo lijevo dijete i potomke tog djeteta (njih barem
) pa
. Analogno,
.
Algoritam očito terminira ( se smanjuje) te nakon njegovog izvođenja su skupovi
disjunktni i vrijedi
.
Prema tome pa
, što je i trebalo pokazati.