Де́рево в теорії графів — зв'язний граф без циклів.
Орієнтоване (спрямоване) дерево — ациклічний орграф (орієнтований граф, що не містить циклів) — той, в якому тільки одна вершина має нульову напівстепінь входу, а всі інші вершини мають напівстепінь входу 1. Вершина з нульовим степенем входу називається коренем дерева, вершини з нульовим напівстепенем виходу (з яких не виходить жодне ребро) називаються кінцевими вершинами або листям.
Формально дерево визначається як скінченна множина T одного або більше вузлів з наступними властивостями:
- Існує один корінь дерева .
- Інші вузли (за винятком кореня) розподілені серед непересічних множин і кожна з множин є деревом; дерева називаються піддеревами даного кореня .
Характеристичні властивості
Найважливіші характеристичні властивості «дерева» висловлюються такими шістьма рівносильними одне одному висловленнями:
- та (визначення «дерева»);
- та ;
- та ;
- для довільної пари вершин x, y в L існує один і тільки один ланцюг, який з'єднує x та y;
- , але якщо із L видалити будь яке ребро, то для отриманого графу L− буде ;
- , але якщо до додати будь яке ребро (не додаючи вершин), то у отриманого графу буде .
Тут — довільний граф, — кількість його вершин, — кількість ребер, — кількість компонент зв'язності, — цикломатичне число.
Довільний граф без циклів часто називають лісом (оскільки кожна його складова — «дерево»). Ордерево, яке росте із x0, — це «дерево», в якому виділено одну вершину x0 («корінь»), а ребра орієнтовані таким чином, що всі ланцюги, які починаються в x0, є шляхами (тобто, їхні дуги орієнтовані в напряму обходу).
Пов'язані визначення
Степінь вершини — кількість інцидентних їй ребер.
Кінцевий вузол (лист, термінальна вершина) — сайт зі ступенем 1 (тобто вузол, у який веде тільки одне ребро; у разі орієнтованого дерева — вузол, який веде тільки одна дуга і не виходить ні однієї дуги).
Вузол розгалуження — некінцевий вузол.
Рівень вузла — довжина шляху від кореня до вузла. Можна визначити рекурсивно:
рівень кореня дерева дорівнює 0;
рівень будь-якого іншого вузла на одиницю більше, ніж рівень кореня найближчого піддерева дерева, що містить цей сайт.
Дерево із позначеною вершиною називається кореневим деревом.
N-й ярус дерева — множина вузлів дерева, на n-ому рівні від кореня дерева.
Частковий порядок на вершинах: якщо вершини різні і вершина лежить на елементарному ланцюзі, що з'єднує корінь з вершиною кореневе дерево з коренем — підграф .
Кістякове дерево (остов) — це підграф даного графу, що містить всі його вершини і є деревом. Ребра графу, що не входять в остов, називаються хордами графу відносно остова.
Незведеним називається дерево, в якому немає вершин ступеня 2.
Ліс — множина дерев, або незв'язний граф без циклів.
- Лінійний ліс — ліс, утворений з диз'юнктного об'єднання шляхів.
Бінарне (двійкове) дерево
Термін бінарне дерево (воно ж двійкове дерево) має кілька значень:
- Неорієнтоване дерево, в якому ступені вершин не перевищують 3.
- Орієнтоване дерево, в якому вихідні ступені вершин (число вихідних ребер) не перевищують 2.
- Абстрактна структура даних, яка використовується в програмуванні. На двійковому дереві засновані такі структури даних, як бінарне дерево пошуку, двійкова купа, червоно-чорне дерево, АВЛ-дерево, фібоначчієва купа та ін.
N-арні дерева
N-арні дерева визначаються за аналогією з двійковим деревом. Для них також є орієнтовані та неорієнтовані випадки, а також відповідні абстрактні структури даних.
- N-арне дерево (неорієнтоване) — це дерево звичайне (неорієнтоване), в якому ступені вершин не перевищують N+1.
- N-арне дерево (орієнтоване) — це орієнтоване дерево, в якому вихідні ступені вершин (число вихідних ребер) не перевершують N.
Властивості
- Дерево не має кратних ребер та петель.
- Будь-яке дерево з вершинами містить ребер. Більш того, скінченний зв'язний граф є деревом, тоді і тільки тоді, коли , де — число вершин, — число ребер графу.
- Граф є деревом, тоді і тільки тоді, коли будь-які дві різні його вершини можна з'єднати єдиним простим ланцюгом.
- Будь-яке дерево однозначно визначається відстанями (найменшою довжиною ланцюга) між його кінцевими (ступеня 1) вершинами.
- Будь-яке дерево є двочастковим графом. Будь-яке дерево, множина вершин якого не більше ніж рахункова, є планарним графом.
- Для будь-яких трьох вершин дерева шляхи між парами цих вершин мають одну спільну вершину.
Підрахунок дерев
Кількість різних дерев, які можна побудувати на нумерованих вершинах, згідно формули Келі дорівнює .
Див. також
- Теорія графів — містить визначення багатьох термінів.
- Дерево (структура даних) — застосування дерев в програмуванні.
- Дерево Тремо
- Псевдоліс
Примітки
- Дерево // Словник української мови : у 20 т. — К. : Наукова думка, 2010—2022.
Джерела
- Енциклопедія кібернетики, Зиков О. О., т. 1, с. 256.
- Трохимчук, Роман. (PDF) (Українська) . Архів оригіналу (PDF) за 4 березня 2016. Процитовано 27 березня 2016.
- . vuz.exponenta.ru. Архів оригіналу за 12 квітня 2016. Процитовано 27 березня 2016.
Це незавершена стаття з математики. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U Vikipediyi ye statti pro inshi znachennya cogo termina Derevo znachennya De revo v teoriyi grafiv zv yaznij graf bez cikliv Priklad dereva Oriyentovane spryamovane derevo aciklichnij orgraf oriyentovanij graf sho ne mistit cikliv toj v yakomu tilki odna vershina maye nulovu napivstepin vhodu a vsi inshi vershini mayut napivstepin vhodu 1 Vershina z nulovim stepenem vhodu nazivayetsya korenem dereva vershini z nulovim napivstepenem vihodu z yakih ne vihodit zhodne rebro nazivayutsya kincevimi vershinami abo listyam Formalno derevo viznachayetsya yak skinchenna mnozhina T odnogo abo bilshe vuzliv z nastupnimi vlastivostyami Isnuye odin korin dereva T displaystyle T Inshi vuzli za vinyatkom korenya rozpodileni sered M 0 displaystyle M geqslant 0 neperesichnih mnozhin T1 Tm displaystyle T 1 T m i kozhna z mnozhin ye derevom dereva T1 Tm displaystyle T 1 T m nazivayutsya pidderevami danogo korenya T displaystyle T Harakteristichni vlastivostiNajvazhlivishi harakteristichni vlastivosti dereva vislovlyuyutsya takimi shistma rivnosilnimi odne odnomu vislovlennyami ϰ L 1 displaystyle varkappa L 1 ta l L 0 displaystyle lambda L 0 viznachennya dereva l L 0 displaystyle lambda L 0 ta m L n L 1 displaystyle m L n L 1 ϰ L 1 displaystyle varkappa L 1 ta m L n L 1 displaystyle m L n L 1 dlya dovilnoyi pari vershin x y v L isnuye odin i tilki odin lancyug yakij z yednuye x ta y ϰ L 1 displaystyle varkappa L 1 ale yaksho iz L vidaliti bud yake rebro to dlya otrimanogo grafu L bude ϰ L 2 displaystyle varkappa L 2 l L 0 displaystyle lambda L 0 ale yaksho do L displaystyle L dodati bud yake rebro ne dodayuchi vershin to u otrimanogo grafu L displaystyle L bude l L 1 displaystyle lambda L 1 Tut L displaystyle L dovilnij graf n L displaystyle n L kilkist jogo vershin m L displaystyle m L kilkist reber ϰ L displaystyle varkappa L kilkist komponent zv yaznosti l L displaystyle lambda L ciklomatichne chislo Dovilnij graf bez cikliv chasto nazivayut lisom oskilki kozhna jogo skladova derevo Orderevo yake roste iz x0 ce derevo v yakomu vidileno odnu vershinu x0 korin a rebra oriyentovani takim chinom sho vsi lancyugi yaki pochinayutsya v x0 ye shlyahami tobto yihni dugi oriyentovani v napryamu obhodu Pov yazani viznachennyaDokladnishe Slovnik terminiv teoriyi grafiv Stepin vershini kilkist incidentnih yij reber Kincevij vuzol list terminalna vershina sajt zi stupenem 1 tobto vuzol u yakij vede tilki odne rebro u razi oriyentovanogo dereva vuzol yakij vede tilki odna duga i ne vihodit ni odniyeyi dugi Vuzol rozgaluzhennya nekincevij vuzol Riven vuzla dovzhina shlyahu vid korenya do vuzla Mozhna viznachiti rekursivno riven korenya dereva dorivnyuye 0 riven bud yakogo inshogo vuzla na odinicyu bilshe nizh riven korenya najblizhchogo piddereva dereva sho mistit cej sajt Derevo iz poznachenoyu vershinoyu nazivayetsya korenevim derevom N j yarus dereva mnozhina vuzliv dereva na n omu rivni vid korenya dereva Chastkovij poryadok na vershinah yaksho vershini rizni i vershina lezhit na elementarnomu lancyuzi sho z yednuye korin z vershinoyu koreneve derevo z korenem pidgraf Kistyakove derevo ostov ce pidgraf danogo grafu sho mistit vsi jogo vershini i ye derevom Rebra grafu sho ne vhodyat v ostov nazivayutsya hordami grafu vidnosno ostova Nezvedenim nazivayetsya derevo v yakomu nemaye vershin stupenya 2 Lis mnozhina derev abo nezv yaznij graf bez cikliv Linijnij lis lis utvorenij z diz yunktnogo ob yednannya shlyahiv Binarne dvijkove derevoDokladnishe Dvijkove derevo Termin binarne derevo vono zh dvijkove derevo maye kilka znachen Neoriyentovane derevo v yakomu stupeni vershin ne perevishuyut 3 Oriyentovane derevo v yakomu vihidni stupeni vershin chislo vihidnih reber ne perevishuyut 2 Abstraktna struktura danih yaka vikoristovuyetsya v programuvanni Na dvijkovomu derevi zasnovani taki strukturi danih yak binarne derevo poshuku dvijkova kupa chervono chorne derevo AVL derevo fibonachchiyeva kupa ta in N arni derevaN arni dereva viznachayutsya za analogiyeyu z dvijkovim derevom Dlya nih takozh ye oriyentovani ta neoriyentovani vipadki a takozh vidpovidni abstraktni strukturi danih N arne derevo neoriyentovane ce derevo zvichajne neoriyentovane v yakomu stupeni vershin ne perevishuyut N 1 N arne derevo oriyentovane ce oriyentovane derevo v yakomu vihidni stupeni vershin chislo vihidnih reber ne perevershuyut N VlastivostiDerevo ne maye kratnih reber ta petel Bud yake derevo z n displaystyle n vershinami mistit n 1 displaystyle n 1 reber Bilsh togo skinchennij zv yaznij graf ye derevom todi i tilki todi koli B P 1 displaystyle B P 1 de B displaystyle B chislo vershin P displaystyle P chislo reber grafu Graf ye derevom todi i tilki todi koli bud yaki dvi rizni jogo vershini mozhna z yednati yedinim prostim lancyugom Bud yake derevo odnoznachno viznachayetsya vidstanyami najmenshoyu dovzhinoyu lancyuga mizh jogo kincevimi stupenya 1 vershinami Bud yake derevo ye dvochastkovim grafom Bud yake derevo mnozhina vershin yakogo ne bilshe nizh rahunkova ye planarnim grafom Dlya bud yakih troh vershin dereva shlyahi mizh parami cih vershin mayut odnu spilnu vershinu Pidrahunok derevKilkist riznih derev yaki mozhna pobuduvati na n displaystyle n numerovanih vershinah zgidno formuli Keli dorivnyuye nn 2 displaystyle n n 2 Div takozhPortal Matematika Teoriya grafiv mistit viznachennya bagatoh terminiv Derevo struktura danih zastosuvannya derev v programuvanni Derevo Tremo PsevdolisPrimitkiDerevo Slovnik ukrayinskoyi movi u 20 t K Naukova dumka 2010 2022 DzherelaEnciklopediya kibernetiki Zikov O O t 1 s 256 Trohimchuk Roman PDF Ukrayinska Arhiv originalu PDF za 4 bereznya 2016 Procitovano 27 bereznya 2016 vuz exponenta ru Arhiv originalu za 12 kvitnya 2016 Procitovano 27 bereznya 2016 Ce nezavershena stattya z matematiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi