Definicje drzewa

1. Drzewo jest to acykliczny i spojny graf.

2. Drzewo jest to zbior ciagow zamkniety na operacje wybierania podciagu poczatkowego.

Przyklad: {<1,1,0>, <1,1>, <0,1>, <1>, <0>, <>}

3. (Definicja indukcyjna drzewa skonczonego):

- Zbior pusty jest drzewem

- Skonczona liczba drzew podporzadkowanych pewnemu wezlowi jest drzewem.

- Nic wiecej nie jest drzewem.

4. Drzewo niepuste jest to acykliczny graf ktorego liczba krawedzi jest o 1 wieksza niz liczba wezlow.

5. Drzewo niepuste jest to spojny graf ktorego liczba krawedzi jest o 1 wieksza niz liczba wezlow.

6. Drzewo niepuste jest to maksymalny acykliczny graf na zadanej liczbie wezlow. 

7. Drzewo niepuste jest to minimalny spojny graf na zadanej liczbie wezlow. 


Definicja drzewa binarnego

Drzewem binarnym jest drzewo ktorego korzen ma co najwyzej 2 krawedzie styczne a kazdy inny wezel ma co najwyzej 3 krawedzie styczne. 

Cwiczenie: Przeformuluj definicje 2 i 3 tak aby definiowaly one drzewa binarne.