3.4 Ағаштар

 

Ақырлы байланысты циклдарсыз граф ағаш деп аталады. Байланыстылық саны k ға тең, k>1, ақырлы циклдарсыз граф k ағаштан тұратын орман  деп аталады.

Теорема Ақырлы {M, N, T) граф үшін келесі 3 тұжырым эквивалентті:

1) (M, N, T) – ағаш, яғни байланысты циклдарсыз граф.

2) (M, N, T) графтың циклдары жоқ және |N|=|M|-1.

3) (M, N, T) граф байланысты және |N|=|M|-1.