Ћекции.ќрг


ѕоиск:




 атегории:

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

 

 

 

 


«¬Тя«Ќ≤—“№




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

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

„асто в≥дношенн€ звТ€зност≥ ускладнюЇтьс€ додатковими умовами. √раф називають цикл≥чно зв'€зковим, €кщо будь-€к≥ дв≥ р≥зн≥ вершини м≥ст€тьс€ в цикл≥ (наприклад, граф на мал. 3.5, а цикл≥чно зв'€зковий, а граф на мал. 3.6 Ч н≥, тому що вершина не м≥ститьс€ н≥ в €кому цикл≥ з ≥ншими вершинами). √раф називають -зв'€зковим, €кщо будь-€ка пара р≥зних вершин зв'€зана, принаймн≥ ланцюгами, що не мають сп≥льних вершин (кр≥м початковоњ ≥ к≥нцевоњ). “ак, граф на мал. 3.5, а двузвТ€зний, а на мал. 3.6 Ч однозвТ€зний.

¬идал€Їмий

цикл

ѕростий ланцюг ћал. 3.6. «в'€зковий граф. ћал. 3.7. Ќезв'€зний граф, що складаЇтьс€ ≥з трьох компонент .

 

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





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


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


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

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

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

2051 - | 1912 -


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

√ен: 0.008 с.