Ћекции.ќрг


ѕоиск:




 атегории:

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

 

 

 

 


Ёлементы теории графов




 

√раф задаЄтс€ парой множеств: множества , называемого множеством вершин, и множества U, называемого множеством рЄбер. –ебро u Î U есть пара i, еj), где еi, еj Î , указывающа€, между какими двум€ вершинами проведено ребро. √овор€т, что ребро u Î U инцидентно вершинам еi, еj. ≈сли пор€док рЄбер не имеет значени€, т.е. u =(еi, еj) =(еj, еi), то ребро называетс€ неориентированным или просто ребром, если же пор€док имеет значение, то ребро u = (еi, еj) называетс€ ориентированным ребром или дугой. ¬ершина еi называетс€ началом дуги, еj Ц конец дуги. √раф, содержащий хот€ бы одну дугу, называетс€ ориентированным графом или орграфом.

√раф G (E, U) называетс€ конечным, если множество ≈ вершин конечно.

√раф G (E, U), у которого кажда€ вершина еi Î соединена рЄбрами с остальными вершинами (любые две вершены соединены ребром), называетс€ полным (рис. 3.2).

 

–ис. 3.2. ѕолный граф

 

≈сли хот€ бы две вершины соединены несколькими рЄбрами, то такой граф называетс€ мультиграфом. ƒве вершины еi, еj Î ≈ называютс€ смежными, если они соединены ребром. „исло рЄбер, инцидентных данной вершине еj, называетс€ локальной степенью этой вершины р(еi). „исло рЄбер r графа G(E,U) определ€етс€ выражением.

 

 

где n Ц количество вершин в графе.

–ассмотрим граф, изображЄнный на рисунке 3.3.

 

 

–ис. 3.3. ќриентированный граф

 

ћножество вершин графа состоит из п€ти элементов: = {1, 2, 3, 4, 5}, а множество рЄбер U = {(1, 2), (1, 4), (1, 5), (2, 3), (3, 4), (5, 3)}. –ебро (5, 3) €вл€етс€ ориентированным ребром или дугой. „исло рЄбер в графе определ€етс€ по значению локальных степеней дл€ каждой вершины:

р (1) = 3; р (2) = 2; р (3) = 3; р (4) = 2; р (5) = 2; р = (3 + 2 + 3 + 2 + 2) / 2 = 6.

¬ажным в теории графов €вл€етс€ пон€тие части графа G(E,U), который обозначаетс€ G'(E',U') Í G(E,U). ћножества вершин и ребЄр части графа €вл€ютс€ подмножествами вершин и рЄбер исходного графа ≈' Í ≈ U' Í U. ћногие задачи на графах состо€т в определении частей графа с заданными свойствами.

„асть графа G'(E',U') Í G(E,U) называетс€ подграфом графа G(E,U), если ≈' Í , а подмножество U' Í U образовано только рЄбрами, инцидентными вершинам множества ≈'.

ћаршрутом графа G называетс€ последовательность рЄбер S = (u 1, u 2, ¼, u n), в которой каждые два соседних ребра имеют общую вершину, т.е. u 1 = (е 1, е 2); u2= (е 2, е 3); ... u n = (еn, еn+ 1). Ќе исключено, что одно и то же ребро может встречатьс€ несколько раз на одном маршруте.

ƒве вершины еi и еj называютс€ св€занными, если существует маршрут из еi в еj.

ѕростой цепью,или простым путЄм, называетс€ маршрут, в котором ни одно ребро не повтор€етс€ дважды. Ёлементарной цепью или элементарным путЄм называетс€ маршрут, в котором ни одна вершина не повтор€етс€ дважды. ÷иклом в графе называетс€ маршрут, у которого начальна€ вершина совпадает с конечной. Ќапример, граф, представленный на рисунке 3.4, имеет цикл S =(1, 2,3, 5, 4, 1).

 

–ис. 3.4. ѕример графа, имеющего цикл

 

÷икл, проход€щий по всем рЄбрам графа только один раз, называетс€ эйлеровым циклом. ¬ теории графов доказываетс€ теорема, определ€юща€, содержит ли граф эйлеров цикл. ќказываетс€, конечный граф содержит эйлеров цикл тогда и только тогда, когда он св€зан, и все его локальные степени вершин чЄтные. ¬ажной прикладной задачей теории графов €вл€етс€ задача поиска в графе цикла, проход€щего через каждую вершину только один раз. “акие циклы называютс€ гамильтоновыми циклами.

¬есьма важным €вл€етс€ св€занный граф, не имеющий циклов, он называетс€ деревом. ¬ дереве любые две вершины св€заны единственным путЄм. ¬ершина называетс€ концевой, если ей инцидентно не более одного ребра; одна из концевых вершин может быть выбрана в качестве корн€.

“еори€ графов используетс€ в информатике и программировании, например, дл€ представлени€ структур данных (деревь€), дл€ моделировани€ сетей (маршрутизации данных в »нтернете). ¬ теории алгоритмов, блок-схема алгоритма − это ориентированный граф, указывающий пор€док исполнени€ команд. ¬ершины такого графа могут быть одного из трЄх типов, представленных в таблице 11.

 

“аблица 11





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


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


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

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

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

504 - | 438 -


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

√ен: 0.012 с.