Ћекции.ќрг


ѕоиск:




 атегории:

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

 

 

 

 


ќр≥Їнтован≥ графи




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

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

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

ћал. 3.2.ќр≥Їнтований (а) ≥ зм≥шаний (б) графи.

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





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


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


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

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

Ќаглость Ц это ругатьс€ с преподавателем по поводу четверки, хот€ перед экзаменом уверен, что не знаешь даже на два. © Ќеизвестно
==> читать все изречени€...

838 - | 622 -


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

√ен: 0.007 с.