Главная | Обратная связь

Властивості неорієнтованих дерев

Теорема 6. Граф G є деревом тоді й тільки тоді, коли будь-які його вершини u та v з’єднані єдиним ланцюгом.

Доведення. (Þ) Нехай граф G є деревом. Покажемо, що будь-які вершини u та v графу G з’єднані єдиним ланцюгом. Припустимо супротивне. Тоді у графі G є такі вершини u та v, що існують принаймні два різних ланцюги l₁=u₁,…,u_k та l₂=v₁,…,v_m між ними. Якщо ці ланцюги не мають спільних внутрішніх вершин, то послідовність u₁,…,u_k,v_m-1,…,v₁ є циклом у графі G (адже u₁=v₁=u, u_k=v_m=v, u_k та v_m-1 суміжні, а послідовність ребер, що визначається маршрутом u₁,…,u_k,v_m-1,…,v₁, не містить однакових ребер), тобто маємо суперечність (за умовою, G – ациклічний граф). Нехай l₁ та l₂ мають спільну внутрішню вершину. Зауважимо, що таких вершин може бути кілька. Розглянемо спільну вершину послідовностей l₁ та l₂ (позначимо її w). Знайдемо останнє входження u_s вершини w у послідовність l₁ та останнє входження v_r вершини w у послідовність l₂. Зазначимо, що вершину w можна вибрати таким чином, що послідовності u_s,…,u_k та v_r,…,v_m не матимуть спільних внутрішніх вершин. Тоді послідовність u_s,…,u_k,v_m-1,…,v_r є циклом у графі G. Знову маємо суперечність. Таким чином, у дереві будь-які вершини u та v з’єднані єдиним ланцюгом.

(Ü) Нехай маємо граф G, у якому між будь-якими вершинами u та v існує єдиний ланцюг. Тоді G – зв’язний граф. Покажемо, що він ациклічний. Припустимо супротивне. Тоді у G існує цикл u₁,…,u_k, де u₁=u_k, k>1. Виділимо деяку внутрішню вершину u_i даного циклу й розглянемо підпослідовності u₁,…,u_i й u_i,…,u_k послідовності u₁,…,u_k. Оскільки u₁=u_k, то u₁,…,u_i та u_k,u_k-1,…,u_i – різні ланцюги, що з’єднують вершини u₁ та u_i. Але, за умовою, у графі G будь-які вершини u та v з’єднані єдиним ланцюгом. Отже, маємо суперечність. Таким чином, граф G ациклічний. Теорема доведена.

Наслідок. Нехай Т – нетривіальне дерево, u – кінцева вершина у Т. Тоді граф Т-u є деревом.

Доведення. Нехай е=(u,v) – ребро, інцидентне кінцевій вершині u. Покажемо, що у графі Т-u будь-які вершини w₁ та w₂ з’єднані єдиним ланцюгом. Зауважимо, що w₁¹u й w₂¹u. Оскільки Т – дерево, а w₁ та w₂ – вершини Т, то w₁ та w₂ з’єднані єдиним ланцюгом l (у дереві Т). Такий ланцюг не містить ребра е. Якби це було не так, то вершина u мала б бути першою або останньою вершиною ланцюга l, але це неможливо. Отже, ланцюг l існує у дереві Т-u. Наслідок доведено.

Твердження 8. У кожному нетривіальному дереві скінченного порядку існує кінцева вершина.

Доведення. Припустимо супротивне. Тоді існує таке нетривіальне дерево Т порядку n, у якому немає жодної кінцевої вершини. Це означає, що кожна вершина дерева Т має принаймні дві суміжні вершини. Розглянемо деякий простий ланцюг l=u₁,…,u_k максимальної довжини у дереві Т. Вершина u_k має суміжну вершину w, відмінну від u_k-1. Для вершини w можливі два випадки: 1) w входить у ланцюг l, 2) w не входить у ланцюг l. Розглянемо перший випадок. Нехай для деякої вершини u_i ланцюга l виконується u_i=w. Тоді у дереві Т має існувати цикл u_i,…, u_k,w, що неможливо. Розглянемо другий випадок. Тоді у дереві Т має існувати простий ланцюг u₁,…,u_k,w, довжина якого більша довжини ланцюга l, що неможливо, бо за припущенням l є простий ланцюг максимальної довжини у дереві Т. Таким чином, у дереві Т не може існувати вершина w, відмінна від u_k-1 та суміжна з u_k. Отже, степінь u_k дорівнює одиниці, тобто дерево Т має кінцеву вершину. Твердження доведено.

Наслідок. У кожному нетривіальному дереві скінченного порядку існує кінцеве ребро.

Теорема 7. Дерево порядку n має n-1 ребро.

Доведення здійснюється індукцією по порядку дерева n. При n=1 маємо тривіальне дерево, тобто граф без ребер. Отже, кількість ребер на одиницю менша кількості вершин. Нехай твердження теореми виконується для дерева з m вершинами. Покажемо, що дерево з кількістю вершин m+1 має m ребер. У такому дереві, за твердженням 8, існує кінцева вершина. Вилучивши цю вершину, матимемо граф, що, згідно з наслідком теореми 6, є деревом (позначимо його Т). Але дерево Т має m вершин, отже, за припущенням індукції, Т має m-1 ребро. Дерево Т побудоване шляхом вилучення кінцевої вершини, а, отже, й одного ребра, з дерева, що має m+1 вершину, тобто у дереві порядку m+1 є m ребер. Теорему доведено.

Твердження 9. Нетривіальне скінченне дерево має принаймні дві кінцеві вершини.

Доведення. Нехай Т=(V,E) – дерево порядку n, n>1. Доведемо твердження від супротивного, тобто припустимо, що кількість кінцевих вер-шин у дереві Т менше двох. За твердженням 8, у Т існує кінцева вершина, отже, оскільки Т – нетривіальне дерево, то одна його вершина має степінь 1, а будь-яка інша – степінь не менше двох. До дерева Т застосовна лема про рукостискання, за якою 2×|E|=n(v₁)+…+n(v_n); за теоремою 7, |E|=n-1. Отже, згідно з нашим припущенням, маємо: 2×|E|=2×(n-1)=n(v₁)+…+n(v_n)³2×(n-1)+1, звідки 2n³2n+1, що неможливо, оскільки n>0. Таким чином, маємо суперечність, отже, припущення про те, що у дереві Т менше двох кінцевих вершин, неправильне. Тоді Т має принаймні дві кінцеві вершини. Твердження доведено.

Теорема 8 (теорема Келі). Нехай V – множина, така що |V|=n, n³2. Тоді число різних дерев з множиною вершин V дорівнює n^n-2.

Доведення. Якщо n=2, то твердження теореми правильне, адже існує лише одне дерево з двома заданими вершинами, й також n^n-2=2^2-2=2⁰=1. Нехай Т=(V,E) – дерево з множиною вершин V, |V|=n, n>2. Побудуємо за цим деревом послідовність l довжини n-2, що складається з елементів множини V. Нехай вершини Т пронумеровані числами від 1 до n. За твердженням 9, Т має кінцеві вершини. Зауважимо, що не усі вершини дерева Т кінцеві. Позначимо а₁ кінцеву вершину з найменшим номером (така вершина визначається однозначно). Нехай (а₁,b₁) – кінцеве ребро, інцидентне вершині а₁. Занесемо вершину b₁ у послідовність l й вилучимо вершину а₁. За наслідком теореми 6, граф Т-а₁ є деревом. Якщо це дерево має більше двох вершин, виконаємо таке саме перетворення, як й для дерева Т, тобто знайдемо кінцеву вершину з найменшим номером (позначимо її а₂), знайдемо інцидентне цій вершині ребро (а₂,b₂), занесемо b₂ у послідовність l, вилучимо вершину а₂. Таке перетворення ми будемо здійснювати, поки не залишиться дерево, що має найменшу можливу кількість кінцевих вершин, тобто дві вершини. Оскільки при кожному перетворенні кількість елементів послідовності l збільшується на одиницю, а Т має n вершин, то зрештою l буде мати n-2 вершини. З опису побудови послідовності l видно, що вона однозначно визначається деревом Т.

Навпаки, якщо задано послідовність l довжини n-2, що складається з елементів множини V, то за допомогою оберненого перетворення можна побудувати єдине дерево з множиною вершин V. Нехай b₁ – перша вершина у послідовності l. Знайдемо у множині вершин V вершину, що не входить у l й має найменший номер (позначимо її а₁). Побудуємо ребро (а₁,b₁), вилучимо вершину b₁ з послідовності l, а вершину а₁ – з множини V. Таке побудування виконуватимемо, поки не використаємо усі вершини послідовності l для побудови ребер. Таким чином буде побудовано n-2 ребра, а у множині вершин залишаться дві вершини. Вони й визначатимуть останнє, (n-1)-е, ребро.

Отже, дерево з множиною вершин V однозначно визначає послідовність довжини n-2, що складається з елементів множини V, а послідовність з (n-2) вершин множини V однозначно визначає дерево з множиною вершин V. Таким чином, між множиною Т дерев з множиною вершин V та множиною L послідовностей довжини n-2, що складаються з елементів множини V, існує взаємно однозначна відповідність, а це означає, що потужності цих множин однакові. Тоді, обчисливши кількість послідовностей у L, ми будемо знати кількість дерев у Т. Оскільки на кожному з n-2 місць послідовності може знаходитися будь-яка з n вершин, то за основним правилом комбінаторики, кількість послідовностей у L дорівнює n^n-2, отже, й дерев у Т буде n^n-2. Теорему доведено.

Розглянемо приклад побудови послідовності за деревом й, навпаки, дерева за послідовністю. Нехай у вигляді діаграми задано дерево Т з сімома вершинами (див. рис.14,а). Побудуємо за цим деревом послідовність вершин довжини 5. Спочатку знайдемо у дереві Т кінцеву вершину з найменшим номером. Це вершина 3. Знайдемо ребро, інцидентне цій вершині. Це ребро (3,1). Вершину 3 вилучимо, вершину 1 занесемо у послідовність (рис.14,б). Оскільки побудоване дерево Т₁ має більше двох вершин, продовжимо побудову послідовності. Для цього знайдемо у дереві Т₁ кінцеву вершину з найменшим номером. Це вершина 5; (5,2) – інцидентне їй кінцеве ребро. Вилучимо вершину 5, а вершину 2 занесемо у послідовність (рис.14,в). Дерево Т₂ має більше двох вершин, отже, продовжуємо побудову послідовності. У дереві Т₂ кінцевою вершиною з найменшим номером є вершина 2, (2,1) – інцидентне їй ребро. Вилучимо вершину 2 й занесемо вершину 1 у послідовність (рис.14,г). Дерево Т₃ допускає подальше перетворення. Кінцевою вершиною з найменшим номером є у ньому вершина 1, (1,4) – інцидентне їй кінцеве ребро. Вилучимо вершину 1 та занесемо вершину 4 у послідовність (рис.14,д). Дерево Т₄ має більше двох вершин, отже, перетворюємо його. Кінцевою вершиною з найменшим номером є у Т₄ вершина 6, (6,4) – інцидентне їй кінцеве ребро. Вилучимо вершину 6 та занесемо у послідовність вершину 4 (рис.14,е). Дерево Т₅ має дві вершини, а побудована послідовність містить п’ять елементів. Побудова завершена.

 

а)	б)	в)
г)	д)	е)
	Рис. 14

 

Розглянемо тепер приклад побудови дерева за послідовністю. Нехай задана множина V={1,2,3,4,5,6,7} й послідовність l=1,3,3,5,7, що складається з елементів множини V. Покажемо, як побудувати дерево з множиною вершин V за послідовністю l. У цьому дереві має бути 6 ребер. Перше ребро (е₁) будуємо таким чином. Один кінець цього ребра – перша вершина послідовності l, а інший – вершина з множини V, що не міститься у l й має найменший номер. Такою вершиною є вершина 2. Отже, е₁=(1,2). Вилучимо з l перший елемент й позначимо результат l₁ (l₁=3,3,5,7); з множини V вилучимо вершину 2 й позначимо результат V₁ (V₁={1,3,4,5,6,7}). Наступне ребро (е₂) будуємо, користуючись для зручності послідовністю l₁ та множиною V₁. Одним з кінців ребра е₂ є перша вершина у послідовності l₁, тобто вершина 3, а іншим – вершина 1, бо вона є вершиною з V₁, що не входить у l₁ та має найменший номер. Таким чином, е₂=(3,1). Вилучимо з l₁ перший елемент, а з V₁ – вершину 1; позначимо нову послідовність l₂ (l₂=3,5,7), а нову множину – V₂ (V₂={3,4,5,6,7}). Аналогічним чином будуємо наступні три ребра: е₃=(3,4) (нова послідовність та нова множина вершин: l₃=5,7, V₃={3,5,6,7}), е₄=(5,3) (l₄=7, V₄={5,6,7}), е₅=(7,5) (l₅ – порожня послідовність, V₅={6,7}). Останнє ребро (е₆) визначається двома вершинами, що утворюють множину V₅, тобто е₆=(6,7). Отже, послідовність 1,3,3,5,7 однозначно визначає дерево Т=({1,2,3,4,5,6,7},{(1,2),(3,1),(3,4),(5,3),(7,5),(6,7)}).

Оскільки дерево – зв’язний граф, то кількість компонентів зв’язності будь-якого дерева дорівнює одиниці. Якщо дерево має n вершин, то кількість його ребер, за теоремою 7, дорівнює n-1, тобто однозначно визначається кількістю вершин. Для довільного скінченного графу функціональної залежності між кількістю вершин та кількістю ребер немає. Але можна говорити про нижню та верхню межі кількості ребер графу порядку n з k компонентами зв’язності.

Теорема 9. Нехай G – простий граф порядку n з m ребрами та k компонентами зв’язності. Тоді n-k£ m £(n-k)×(n-k+1)/2.

Доведення. Доведемо спочатку нерівність n-k£m. Доведення здійснюватимемо індукцією по m. Найменша кількість ребер у графі – це 0, тому перевіримо спочатку, чи виконується дана нерівність при m=0. Якщо граф має n вершин й не має ребер, то усі його вершини ізольовані, а це означає, що кожна вершина утворює компонент зв’язності, але тоді кількість компонентів зв’язності такого графу збігається з кількістю вершин. Отже, m=0Þn=kÞn-k=0 Þ n-k£m. Таким чином, при m=0 нерівність n-k£m виконується. Припустимо, що для графу з t ребрами, n¢ вершинами та k¢ компонентами зв’язності виконується нерівність n¢-k¢£t, й покажемо, що тоді для графу з n вершинами, k компонентами зв’язності та кількістю ребер t+1 виконується: n-k£t+1. Нехай G – простий граф порядку n з k компонентами зв’язності й кількістю ребер t+1. Оскільки у графі G існує принаймні одне ребро, то можна здійснити вилучення деякого ребра е з графу G (нехай G₁=G-е). Граф G₁ має t ребер й той самий порядок, що й граф G. Для кількості компонентів зв’язності k₁ графу G₁ можливі два випадки: 1) k₁=k+1, 2) k₁=k (адже вилучення одного ребра графу може призвести до збільшення компонентів зв’язності на одиницю, а може й не призвести до зміни кількості компонентів зв’язності). Розглянемо перший випадок. Оскільки до графу G₁ застосовне припущення індукції, то n-k₁£t, звідки випливає, що n-(k+1)£t, отже, n-k£t+1. Розглянемо другий випадок. Застосувавши до G₁ припущення індукції, маємо n-k₁£t, звідки випливає, що n-k£t, отже, n-k£t+1. Таким чином, індукцією по кількості ребер графу доведено, що n-k£m.

Доведемо тепер нерівність m£(n-k)×(n-k+1)/2. Знайдемо умови, за яких граф порядку n з k компонентами зв’язності має найбільшу кількість ребер й обчислимо цю кількість. Зауважимо, що з усіх простих графів порядку n з k компонентами зв’язності G₁,…, G_k, таких що G₁ має n₁ вершин,…, G_k має n_k вершин, найбільшу кількість ребер має той, у якого кожний компонент зв’язності є простим повним графом. Розглянемо такий простий граф G порядку n з m ребрами та k компонентами зв’язності, усі компоненти зв’язності якого є простими повними графами, й серед компонентів зв’язності якого є нетривіальні графи G_i та G_j. Нехай n_i – порядок графу G_i, m_i – кількість його ребер, n_j – порядок графу G_j, m_j – кількість його ребер. Нехай n_i³n_j. Побудуємо граф G₁ таким чином: виберемо довільну вершину графу G_j, вилучимо її з множини вершин графу G_j й внесемо у множину вершин графу G_i; далі на нових множинах вершин побудуємо прості повні графи, позначимо їх G_i⁺ та G_j^- відповідно; компоненти зв’язності G_i та G_j графу G замінимо відповідно графами G_i⁺ та G_j^-. Новий граф G₁ має той са-мий порядок й ту саму кількість компонентів зв’язності, що й граф G. По-рівняємо кількості ребер графів G₁ та G. Для цього достатньо обчислити за-гальну кількість ребер, що містять G_i⁺ та G_j^-, й порівняти із загальною кіль-кістю ребер, що містять G_i та G_j. Зауважимо, що простий повний граф по-рядку n має n×(n-1)/2 ребер. Граф G_i має n_i×(n_i-1)/2 ребер, граф G_j має n_j×(n_j-1)/2 ребер; порядок графу G_i⁺ дорівнює n_i+1, отже, G_i⁺ має (n_i+1)×n_i/2 ребер; порядок графу G_j^- дорівнює n_j-1, отже, G_j^- має (n_j-1)×(n_j-2)/2 ребер. Таким чином, (((n_i+1)×n_i/2) + ((n_j-1)×(n_j-2)/2))-((n_i×(n_i-1)/2)+(n_j×(n_j-1)/2)) = ((n_i²+n_i+n_j²- -3n_j+2)-(n_i²-n_i+n_j²-n_j))/2=(n_i²+n_i+n_j²-3n_j+2-n_i²+n_i-n_j²+n_j)/2=(n_i-n_j+1)>0, оскільки n_i³n_j. Отже, граф G₁ має більше ребер, ніж граф G. Звідси випливає, що повторюючи описане перетворення, будемо щоразу мати граф з більшою кількістю ребер, ніж у попереднього. Це означає, що з усіх графів порядку n з k компонентами зв’язності найбільшу кількість ребер має той, у якого усі компоненти зв’язності, крім одного, є тривіальними графами, а рівно один компонент зв’язності є простим повним графом. Обчислимо кількість ребер такого графу. Кількість вершин у тому компоненті зв’язності, що містить усі ребра графу, дорівнює n-(k-1), отже, кількість ребер графу дорівнює:

(n-(k-1))×((n-(k-1))-1)/2=(n-k+1)×(n-k)/2.

Таким чином, кількість ребер m будь-якого графу порядку n з k компонентами зв’язності не може перевищувати (n-k+1)×(n-k)/2, тобто m£(n-k)×(n-k+1)/2. Теорему доведено.

 

Контрольні питання

1. Що таке: а) неорієнтоване дерево, б) ліс?

2. Що таке: а) кістякове дерево графу, б) кістяковий ліс графу?

3. Яка є необхідна й достатня умова того, що граф є деревом?

4. Скільки ребер має дерево порядку n?

5. Скільки існує різних дерев із заданою множиною вершин, що складаєть-ся з n елементів?

6. Яка найменша кількість кінцевих вершин у нетривіальному скінченному дереві?

7. У яких межах знаходиться число m ребер простого графу порядку n з k компонентами зв’язності?

 

Задачі та вправи

І. Для заданого графу G визначити, чи є він: а) зв’язним, б) ациклічним, в) неорієнтованим деревом, г) лісом. Які з графів мають кістякові дерева?

1)	G=({1,2,3,4},{(1,2),(1,3),(2,3)});			2)	G=({1,2,3,4},{(1,2),(2,3),(2,4),(3,4)});
3)	G=({1,2,3,4},{(2,3),(3,4)});			4)	G=({1,2,3,4},{(1,2),(2,3),(3,4)});
5)	G=({1,2,3,4},{(1,2),(2,3),(2,4)});			6)	G=({1,2,3,4},{(1,2),(3,4)});
7)	G=({1,2,3,4},{(1,1),(2,3)});			8)	G=({1,2,3,4},{(1,2),(1,3),(2,4),(3,4)}).

ІІ. Побудувати усі кістякові дерева заданого графу G.

1) G=({1,2,3,4,5,6},{(1,4),(2,4),(3,4),(4,5),(4,6),(5,6)});

2) G=({1,2,3,4,5,6},{(1,2),(2,3),(1,4),(2,4),(4,5),(4,6),(5,6)});

3) G=({1,2,3,4,5,6},{(1,2),(2,3),(1,4),(2,4),(3,4),(4,5),(5,6)});

4) G=({1,2,3,4,5,6},{(1,2),(1,4),(1,5),(2,3),(2,6),(3,4),(3,6),(5,6)});

5) G=({1,2,3,4,5,6},{(1,2),(1,3),(2,3), (2,4),(3,5),(3,6),(4,6),(5,6)}).

ІІІ. Задана множина V={1,2,3,4,5,6}. Побудувати дерево з множиною вершин V за послідовністю елементів множини V.

1)	1,2,3,4;		2)	1,1,3,3;		3)	1,2,2,1;		4)	1,1,1,1;		5)	1,3,1,3;
6)	1,1,1,4;		7)	4,4,5,6;		8)	1,4,4,6;		9)	2,3,4,2;		10)	6,3,6,6.

ІV. Для заданого дерева Т побудувати послідовність вершин (як показано у доведенні теореми Келі).

1) T=({1,2,3,4,5,6},{(1,2),(1,3),(2,4),(2,5),(2,6)});

2) T=({1,2,3,4,5,6},{(1,2),(2,3),(2,4),(4,5),(4,6)});

3) T=({1,2,3,4,5,6},{(1,2),(1,3),(1,4),(1,5),(1,6)});

4) T=({1,2,3,4,5,6},{(1,3),(2,3),(3,4),(4,5),(4,6)});

5) T=({1,2,3,4,5,6},{(1,2),(2,3),(3,4),(4,5),(5,6)}).

V. Скільки існує дерев: а) з множиною вершин {a,b,c,d,e}; б) з n вершинами, дві з яких є кінцевими; в) порядку n з максимальною кількістю кінцевих вершин?

VІ. На множині вершин {a,b,c,d,e} побудувати усі попарно неізоморфні дерева, які мають вершини степеня 2.

VІІ. Описати усі дерева, доповнення яких також є деревами.

VІІІ. Нехай G=(V,E) – граф порядку n з m ребрами. Нехай m>(n-1)(n-2)/2. Довести, що G зв’язний.

ІХ. Назвемо ребро графу мостом, якщо його вилучення збільшує кількість компонентів зв’язності графу. Довести, що в нетривіальному дереві кожне ребро є мостом.

Х. Довести, що граф G є зв’язним тоді й тільки тоді, коли він має кістякове дерево.

ХІ. Довести, що ліс, який має n вершин та складається з k дерев, містить n-k ребер.

ХІІ. Нехай граф G порядку n є деревом, нехай G не має вершин степеня 2. Довести, що кількість кінцевих вершин дерева G не менша від (n/2)+1.

ХІІІ. Нехай у графі G порядку n (n³3) кількість кінцевих вершин збігається з кількістю ребер. Довести, що граф G або є незв’язним, або є деревом.

ХІV. Довести, що ребро зв’язного графу G, яке інцидентне кінцевій вершині, входить в усі кістякові дерева графу G.

ХV. Назвемо цикломатичним числом простого графу G=(V,E), який має k компонентів зв’язності, величину v(G)=|E|-|V|+k. Довести, що: а) v(G)³0,

б) граф G є лісом тоді й тільки тоді, коли v(G)=0.