Ћекции.ќрг


ѕоиск:




 атегории:

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

 

 

 

 


“ипи к≥нцевих граф≥в




якщо множина вершин графа к≥нцева, то в≥н називаЇтьс€ к≥нцевим графом. ” математику розгл€даютьс€ ≥ неск≥нченн≥ графи, але ми займатис€ ними не будемо, тому що в практичних додатках вони зустр≥чаютьс€ р≥дко.  ≥нцевий граф G = (V, ≈), що м≥стить р вершин ≥ q ребер, називаЇтьс€ (р, q) -графом.

ћал. 3.3. “ипи граф≥в: а Чпсевдограф; б- повний граф (шестикутник); в-двочастковий граф (б≥граф).

 

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

„исло ребер, зв'€заних з вершиною , (петл€ враховуЇтьс€ дв≥ч≥), називають ступенем вершини ≥ позначають через чи . “ак, дл€ графа на мал. 9, a ≥ т.д. ќчевидно, ступ≥нь ≥зольованоњ вершини дор≥внюЇ нулю . ¬ершина ступен€ одиниц≥ називаЇтьс€ к≥нцевою чи вис€чою вершиною . Ћегко показати, що в будь-€кому граф≥ сума ступен≥в ус≥х вершин дор≥внюЇ подвоЇному числу ребер, а число вершин непарного ступен€ завжди парне. ¬ орграф≥ розр≥зн€ють позитивн≥ ≥ негативн≥ ступен€ вершин, що р≥вн≥ в≥дпов≥дно числу що з ≥ заход€ть у , дуг. Ќаприклад, дл€ вершини орграфа (див. мал. 3.2., а) маЇмо . ќчевидно, суми позитивних ≥ негативних ступен≥в ус≥х вершин орграфа р≥вн≥ м≥ж собою ≥ р≥вн≥ також числу вс≥х дуг.

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

ѕростий граф, у €кому будь-€к≥ дв≥ вершини з'Їднан≥ ребром, називаЇтьс€ повним (на мал. 3.3, б приведений приклад повного графа ≥з ш≥стьма вершинами).

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

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





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


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


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

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

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

1309 - | 1174 -


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

√ен: 0.012 с.