U teoriji grafova, stablo je neusmjereni graf u kojem su bilo koja dva vrha povezana točno jednim putem, ili ekvivalentno povezani aciklički neusmjereni graf. … Polišuma (ili usmjerena šuma ili orijentirana šuma) je usmjereni aciklički graf čiji je temeljni neusmjereni graf šuma.
Što su usmjerena i neusmjerena stabla?
Neusmjeren graf bez ciklusa je šuma i ako je povezan naziva se stablom. Usmjereni graf je šuma (ili stablo) ako kada se svi bridovi pretvore u neusmjerene bridove to je neusmjerena šuma (ili stablo). Ukorijenjeno stablo je stablo s jednim vrhom označenim kao korijen.
Zašto stabla nisu usmjerena?
Teorem: Neusmjeren graf je stablo ako postoji točno jedan jednostavan put između svakog para vrhovaDokaz: Ako imamo graf T koji je stablo, onda mora biti povezan bez ciklusa. Budući da je T povezan, mora postojati barem jedan jednostavan put između svakog para vrhova.
Što znači usmjereno stablo?
Dirigirano stablo je aciklički usmjereni graf Ima jedan čvor s stupnjem 1, dok svi ostali čvorovi imaju stupanj 1 kao što je prikazano na slici: Čvor koji ima vanjski stupanj 0 je naziva vanjski čvor ili terminalni čvor ili list. Čvorovi koji imaju vanjski stupanj veći ili jednak jedan nazivaju se unutarnji čvor.
Kako prepoznati je li neusmjereni graf stablo?
U slučaju neusmjerenih grafova, izvodimo tri koraka:
- Izvršite DFS provjeru s bilo kojeg čvora kako biste bili sigurni da svaki čvor ima točno jednog roditelja. Ako ne, vratite.
- Provjerite jesu li posjećeni svi čvorovi. Ako DFS provjera nije mogla posjetiti sve čvorove, vratite.
- U suprotnom, graf je stablo.
