U teoriji grafova, stablo je neusmjereni graf u kojem su bilo koja dva vrha povezana tačno jednom putanjom, ili ekvivalentno povezani aciklički neusmjereni graf. … Polišuma (ili usmjerena šuma ili orijentirana šuma) je usmjereni aciklički graf čiji je osnovni neusmjereni graf šuma.
Šta 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 rubovi pretvore u neusmjerene ivice to je neusmjerena šuma (ili drvo). Ukorijenjeno stablo je drvo s jednim vrhom označenim kao korijen.
Zašto su stabla neusmjerena?
Teorema: Neusmjereni graf je stablo ako postoji tačno jedan jednostavan put između svakog para vrhovaDokaz: Ako imamo graf T koji je stablo, onda mora biti povezan bez ciklusa. Pošto je T povezan, mora postojati barem jedna jednostavna staza između svakog para vrhova.
Šta znači usmjereno drvo?
Dirigovano stablo je aciklički usmjereni graf Ima jedan čvor sa stepenom 1, dok svi ostali čvorovi imaju stepen 1 kao što je prikazano na slici: Čvor koji ima vanjski stepen 0 je naziva se eksterni čvor ili terminalni čvor ili list. Čvorovi koji imaju vanjski stepen veći ili jednak jedan nazivaju se unutrašnji čvor.
Kako znate da li je neusmjereni graf drvo?
U slučaju neusmjerenih grafova, izvodimo tri koraka:
- Izvršite DFS provjeru sa bilo kojeg čvora kako biste bili sigurni da svaki čvor ima tačno jednog roditelja. Ako ne, vratite.
- Provjerite da li su svi čvorovi posjećeni. Ako DFS provjera nije mogla posjetiti sve čvorove, vratite.
- U suprotnom, graf je drvo.
