Дерева і ліси

Якщо граф – вироджений, тобто має лише вершини, а ребра – відсутні, то і. За теоремою 2.3.2 додавання нового ребра збільшує або, або. Отже, числа та можуть лише зростати.

Наслідок доведено¾.

Підсумовуючи вище сказане, бачимо, що цикломатичне число графа вказує на кількість у ньому циклів.

Серед зв’язних графів найпростішу структуру мають дерева.

Означення 2.3.4. Деревом називають скінчений зв’язний граф без циклів, який має щонайменше дві вершини.

Граф є деревом тоді і тільки тоді, коли кожна пара різних його вершин з’єднана одним і тільки одним ланцюгом.

Видалення довільного ребра з дерева робить його незв’язним, оскільки це ребро є складовою єдиного ланцюга, що з’єднує будь-які дві точки.

Теорема 2.3.3. Для графа G, який має n (n> 1) вершин і m ребер, наступні твердження є еквівалентними:

1) G є деревом;

2) є лише один ланцюг між будь-якими двома вершинами в G;

3) G є зв’язним і m = n -1;

4) G не має циклів і m = n -1;

5) G не має циклів і при з’єднанні ребром довільних двох несуміжних вершин отримуємо граф, який має лише один цикл;

6) G є зв’язним проте втрачає цю властивість, якщо вилучити одне ребро.

Означення 2.3.5. Деревом графа G називають зв’язний підграф графа G, що не має циклів.

Означення 2.3.6. Остовом або покриттям графа G називають дерево графа G, що містить всі вершини графа G.

Означення 2.3.7. Кодерево Т * остова Т графа G – це підграф графа G, що містить всі вершини графа G і лише ті ребра, які не входять в Т.

Орієнтований граф G називається орієнтованим деревом (або прадеревом), що росте з кореня х ₀, якщо:

1) він є деревом без врахування орієнтації;

2) з х ₀ є орієнтований шлях до всіх інших вершин графа G.

Наприклад,

Ребра остова графа G називають гілками дерева Т, а ребра відповідно кодерева – хордами або зв’язками.

Дата добавления: 2014-10-17