Na dworze coraz cieplej, wszystko z ziemi wychodzi a drzew pokrywają się kwiatami. W grafach też są drzewa i to spójne :). Czymże one są ? Zaczynamy od definicji spójności grafu.
Graf jest spójny gdy każde jego dwa wierzchołki połączone są drogą. Dla grafów skierowanych jest określenie silnie spójny czyli taki graf, w którym możemy znaleźć drogę między dwoma wierzchołkami zgodną z kierunkiem strzałek. Z tej definicji wyprowadzamy następną. Składowa spójna to maksymalny podgraf spójny lub w drugą stronę żaden jego nadgraf nie jest spójny. Czyli każdy graf spójny ma jest jedną składową stałą. Poniżej przykład grafu silnie spójnego oraz takich, które nie są spójne.
Wiedząc już co nieco o spójności i składowych spójnych można przejść do zagadnienia związanego z drzewami, lasami i liśćmi.
Drzewo to graf spójny nie zawierający cykli. Dodanie jakiejkolwiek krawędzi spowoduje cykl. Ponadto każda krawędź w drzewie jest mostem czyli taką krawędzią po usunięciu, której liczba składowych spójnych wzrośnie. Lasem można nazwać zbiór drzew 🙂 ot cała filozofia – bardziej naukowo można powiedzieć że to graf acykliczny ale nie koniecznie spójny. Na koniec liście – to takie wierzchołki z których wychodzi tylko jedna krawędź więc można o nich powiedzieć, że są pierwszego stopnia.
Ponadto można powiedzieć o drzewie, że jest ukorzenione gdy ma wyróżniony jeden z wierzchołków (właśnie korzeń). Można również określić głębokość i wysokość takiego drzewa określając maksymalne długości drogi między wierzchołkami. W drzewie między wierzchołkami zachodzą również zależności podobne do drzewa genealogicznego. Zatem wierzchołki mają swoich przodków, rodziców, dzieci i potomków. Nazewnictwo jest intuicyjne więc pominę szczegółowy opis.
Należy jeszcze dodać że wyróżniamy drzewa d-arne np. 2-arne. Drzewo 2-arne to takie w którym każdy wierzchołek ma ilość mniejszą lub równą liczbie dwa. Takie drzewo jest jeszcze nazywane binarnym.