Ћекции.ќрг


ѕоиск:




 атегории:

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

 

 

 

 


ћаршрути




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

ћаршрут, ус≥ ребра €кого р≥зн≥, називаЇтьс€ ланцюгом, а маршрут, дл€ €кого р≥зн≥ ус≥ вершини, називаЇтьс€ простим ланцюгом. «амкнутий ланцюг називаЇтьс€ циклом, а простий ланцюг Ч простим циклом. “ак, на граф≥ мал. 3.3, а Ч ланцюг, Ч простий ланцюг, Ч цикл, Ч простий цикл.

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

 ритер≥й ≥снуванн€ ейлерового циклу. ƒл€ ≥снуванн€ в граф≥ ейлерового циклу необх≥дно ≥ достатньо щоб ступен≥ ус≥х вершин були парними.

ƒл€ гам≥льтонових цикл≥в н≥€кого загального правила не знайдено.

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





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


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


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

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

¬ моем словаре нет слова Ђневозможної. © Ќаполеон Ѕонапарт
==> читать все изречени€...

1901 - | 1880 -


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

√ен: 0.01 с.