Ћекции.ќрг


ѕоиск:




 атегории:

јстрономи€
Ѕиологи€
√еографи€
ƒругие €зыки
»нтернет
»нформатика
»стори€
 ультура
Ћитература
Ћогика
ћатематика
ћедицина
ћеханика
ќхрана труда
ѕедагогика
ѕолитика
ѕраво
ѕсихологи€
–елиги€
–иторика
—оциологи€
—порт
—троительство
“ехнологи€
“ранспорт
‘изика
‘илософи€
‘инансы
’ими€
Ёкологи€
Ёкономика
Ёлектроника

 

 

 

 


ƒерева ≥ л≥с




ќсобливий ≥нтерес представл€ють зв'€зков≥ ацикличн≥ графи, називан≥ деревами. ƒерево на безл≥ч≥ вершин завжди м≥стить ребер, тобто м≥н≥мальну к≥льк≥сть ребер, необх≥дну дл€ того, щоб граф був звТ€зним. ƒ≥йсно, дв≥ вершини зв'€зуютьс€ одним ребром, ≥ дл€ зв'€зку кожноњ наступноњ вершини з попередн≥ми потр≥бно ребро, отже, дл€ зв'€зку вершин необх≥дно ≥ достатньо ребер.

ѕри додаванн≥ в дерево ребра утворитьс€ цикл, а при видаленн≥ хоча б одного ребра дерево розпадаЇтьс€ на компоненти, кожна з €кий €вл€Ї собою також дерево або ≥зольовану вершину. Ќезв'€зний граф, компоненти €кого Ї деревами, називаЇтьс€ л≥сом (л≥с ≥з дерев, що м≥стить вершин, маЇ в точност≥ ребер). —казане ≥люструЇтьс€ на приклад≥ дерева (мал. 3.9, а), що перетворюЇтьс€ в цикл≥чний граф додаванн€м ребра (мал. 3.9, б) ≥ розпадаЇтьс€ на л≥с ≥з двох дерев при видаленн≥ ребра (мал. 3.9, в).

ћал. 3.9. ƒерево (а), утворенн€ циклу при введенн≥ додаткового ребра (б) ≥ л≥с, що утворитьс€ п≥сл€ видаленн€ ребра (в).

«вичайно дерева вважаютьс€ ≥стотно р≥зними, €кщо вони не ≥зоморфн≥. Ќа мал. 3.10 показан≥ вс≥ можлив≥ р≥зн≥ дерева ≥з ш≥стьма вершинами. «≥ зб≥льшенн€м числа вершин к≥льк≥сть р≥зних дерев р≥зко зростаЇ (наприклад, при њх нараховуЇтьс€ б≥л€ м≥льйона). —еред р≥зних дерев вид≥л€ютьс€ два важлив≥ окрем≥ випадки: посл≥довне дерево, що представл€Ї собою простий ланцюг, ≥ зор€не дерево, у €кому одна з вершин (центр) сум≥жна з вс≥ма ≥ншими вершинами.

 

ћал. 3.10. ≤стотно р≥зн≥ дерева ≥з ш≥стьма вершинами. ћал. 11. ѕрадерево з коренем .

 

–озгл€даютьс€ також дерева з ор≥Їнтованими ребрами (дугами). ќр≥Їнтоване дерево називаЇтьс€ прадеревом ≥з коренем , €кщо ≥снуЇ шл€х м≥ж вершиною ≥ будь-€кою ≥ншою його вершиною (мал. 3.11). ясно, що прадерево маЇ Їдиний кор≥нь.

ƒотепер розгл€далис€ дерева €к м≥н≥мальн≥ звТ€зн≥ графи на безл≥ч≥ вершин. ¬ажливе значенн€ маЇ й ≥нша точка зору, коли дерева або л≥с Ї частинами де€кого графа, тобто утворюютьс€ з його ребер. Ѕудь-€ка зв'€зкова сукупн≥сть ребер, що не м≥стить контур≥в, разом ≥з ≥нцидентними њм вершинами утворюЇ дерево графа (мал. 3.12, а). якщо таке дерево Ї суграфом (м≥стить ус≥ вершини графа), то воно називаЇтьс€ покриваючим деревом, або к≥ст€ком (мал. 3.12,б). “ак €к петл€ €вл€Ї собою найпрост≥ший цикл, що перебуваЇ з Їдиного ребра, то вона не може входити до складу будь-€кого дерева графа. –ебра графа, що належать його дереву, називають г≥лками. якщо дерево покриваЇ граф, то множина ребер графа розбиваЇтьс€ на дв≥ п≥дмножини: п≥дмножина г≥лок ≥ п≥дмножина ребер доповненн€ дерева, називаних хордами. ѕри цьому зв'€зковий граф м≥стить г≥лок ≥ хорд. якщо граф незв'€зний, то сукупн≥сть к≥ст€к≥в його компонент утворить покриваючий л≥с. ” цьому випадку .

 
 

 

 


а б

ћал. 3.12. ƒерево €к частина графа (вид≥лено жирними л≥н≥€ми):

а Ч дерево; б Ч к≥ст€к (дерево, що покриваЇ,).

 

ƒерева грають важливу роль у р≥зних прикладних завданн€х, коли, наприклад, мова йде про зв'€зок €ких-небудь об'Їкт≥в м≥н≥мальним числом канал≥в (л≥н≥й зв'€зку, дор≥г, комун≥кац≥й) ≥з визначеними властивост€ми. «а допомогою дерева визначаЇтьс€ система координат при моделюванн≥ ланцюг≥в ≥ систем р≥зноњ ф≥зичноњ природи. ƒерева використовуютьс€ в €кост≥ моделей при розгл€д≥ ≥Їрарх≥чних систем об'Їкт≥в, структурних формул орган≥чних сполук ≥ т.п.

ѕЋјЌј–Ќќ—“№

√раф називають плоским (планарным), €кщо ≥снуЇ ≥зоморфний йому граф (геометрична реал≥зац≥€), що може бути зображений на площин≥ без перетинанн€ ребер. Ќаприклад, хоча в одному з граф≥в на мал. 10 ребра перетинаютьс€, ≥зоморфн≥ йому не мають перетинань, отже, в≥н плоский.

 

ћал. 3.13. √рафи ѕонтр€гина Ч  уратовского:

а Ч повний п'€тикутник; б Ч двочастковий граф.

 

Ќа мал. 3.13 показан≥ два неплоских графи, що грають фундаментальну роль у теор≥њ планарности ≥ називан≥ графами ѕонтр€г≥на -  уратовського. ѕовний п'€тикутник (мал. 3.13, а) €вл€Ї собою простий неплоский граф ≥з м≥н≥мальним числом вершин (повний граф ≥з чотирма вершинами Ч плоский, а видаленн€ з п'€тикутника хоча б одного ребра також перетворюЇ його в плоский граф). ƒвочастковий граф (мал. 3.13, б) Ї моделлю в≥домого завданн€ про три будинки ≥ три колод€з€: чи можна прокласти в≥д будинк≥в до кожного колод€з€ дороги так, щоб вони не перетиналис€ (ворогуюч≥ сус≥ди повинн≥ мати можлив≥сть користуватис€ вс≥ма колод€з€ми, але не хочуть зустр≥чатис€ на дорогах)?

¬ластивост≥ планарности не порушуютьс€, €кщо де€ке ребро розбити на два введенн€м новоњ вершини другого ступен€ або зам≥нити два ребра, €к≥ ≥нцидентн≥ вершин≥ другого ступен€, одним ребром, видалив цю вершину. ƒва графи називають гомеоморфними (≥зоморфними з точн≥стю до вершин другого ступен€), €кщо п≥сл€ видаленн€ з них вершин другого ступен€ й об'Їднанн€ ≥нцидентних цим вершинам ребер, вони ви€вл€ютьс€ ≥зоморфними (мал. 3.14). ќчевидно, граф, гомеоморфний плоскому графу, також плоский.

—трого доводитьс€, що граф Ї плоским тод≥ ≥ т≥льки тод≥, коли в≥н не м≥стить п≥дграф, гомеоморфний одному з граф≥в ѕонтр€гинаЧ уратовского.

 

ћал. 3.14. √омеоморфн≥ графи.

 

ѕланарн≥сть Ї ≥стотною властив≥стю граф≥в, що моделюють комун≥кац≥њ ≥ зв'€зк≥ м≥ж об'Їктами на площин≥ (дороги м≥ж населеними пунктами, водопров≥дн≥ ≥ газопров≥дн≥ мереж≥, л≥н≥њ передач електроенерг≥њЕ). ѕлоскими графами представл€ютьс€ р≥зн≥ карти, ≥з €кими, зокрема, зв'€зана в≥дома проблема чотирьох фарб: чи завжди можна розфарбувати област≥, на €к≥ плоский граф под≥л€Ї поверхню, так, щоб н≥€к≥ дв≥ сум≥жн≥ област≥ не були пофарбован≥ в однаковий кол≥р ≥ щоб при цьому було використано не б≥льш чотирьох кольор≥в? ƒоведено, що дл€ такого розфарбуванн€ в будь-€кому випадку досить п'€тьох фарб, але н≥хто ще не прив≥в приклада, коли п'€ть фарб д≥йсно необх≥дн≥. ѕроблема залишаЇтьс€ невир≥шеноњ, незважаючи на величезн≥ зусилл€ багатьох видатних математик≥в, що штурмують њњ б≥льш стор≥чч€.





ѕоделитьс€ с друзь€ми:


ƒата добавлени€: 2015-02-12; ћы поможем в написании ваших работ!; просмотров: 942 | Ќарушение авторских прав


ѕоиск на сайте:

Ћучшие изречени€:

Ћогика может привести ¬ас от пункта ј к пункту Ѕ, а воображение Ч куда угодно © јльберт Ёйнштейн
==> читать все изречени€...

1983 - | 1943 -


© 2015-2024 lektsii.org -  онтакты - ѕоследнее добавление

√ен: 0.008 с.