Ћекции.ќрг


ѕоиск:




 атегории:

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

 

 

 

 


Ћемма о рукопожатии. —ледствие




“еори€ графов. ѕон€тие графа.

√рафом называетс€ набор точек (эти точки называютс€ вершинами), некоторые из которых объ€вл€ютс€ смежными (или соседними). —читаетс€, что смежные вершины соединены между собой ребрами (или дугами).

„исло вершин в графе Ч пор€док, число рЄбер Ч размер графа.

√раф называетс€ ориентированным (или орграфом),если некоторые ребра имеют направление. Ётоозначает, что в орграфе некотора€ вершина может быть соединена с другой вершиной, а обратного соединени€ нет. √еометрически граф часто изображают точками плоскости, причем соседние вершины соединены дугами (дл€ орграфа некоторые дуги имеют направление, что обычно отмечают стрелкой).

способы задани€ графа

явное задание графа как алгебраической системы.

√еометрический

ћатрица смежности

ћатрица инцидентности

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

ѕуть в графе (иногда говор€т простой путь) Ц это маршрут без повторени€ вершин (а значит, и ребер).

 онтур Ц это цикл без повторени€ вершин, за исключением первой вершины, совпадающей с последней.

 

2. ќсновные пон€ти€ теории графов: пон€тие ребра, вершины, смежности вершин, инцидентности ребер, пон€тие петли.

“аким образом, ребро определ€етс€ парой вершин. ƒва ребра, у которых есть обща€ вершина, также называютс€ смежными (или соседними).

ƒва ребра называютс€ кратными, если множества их концевых вершин совпадают.

ћежду элементами множества вершин и множества ребер определено отношение инцидентности. √овор€т, что ребро е инцидентно вершинам v, w, если оно соедин€ет эти вершины и наоборот, кажда€ из вершин v, w инцидентна ребру е.

–ебро называетс€ петлЄй, если его концы совпадают.

 

ѕон€тие мультиграфа, псевдографа.

ѕсевдограф − граф, в котором есть петли и/или кратные ребра.

ћультиграф − псевдограф без петель.

 

ѕон€тие степени вершины, пор€дка графа.

—тепень вершины Ц это число ребер, вход€щих в эту вершину. ¬ершина называетс€ вис€чей, если ее степень равна единице (0 - изолированна€).

„исло вершин графа называетс€ его пор€дком и обозначаетс€ |G|.

 

Ћемма о рукопожатии. —ледствие.

Ћемма: —умма степеней всех вершин графа (или мультиграфа без петель) Ч четное число, равное удвоенному числу ребер.

—ледствие 1 из леммы о рукопожати€х. ѕроизвольный граф имеет четное число вершин нечетной степени.

—ледствие 2 из леммы о рукопожати€х. „исло ребер в полном графе n(n-1)/2.

 

6. –азновидности графов: полные графы, регул€рные графы, простые графы, св€зные графы, полностью несв€зные графы, ѕлатоновы графы, двудольные графы

√раф G называетс€ полным, если любые две его вершины смежны. ѕолный граф Ч простой граф, в котором кажда€ пара различных вершин смежна. ѕолный граф с вершинами имеет рЄбер и обозначаетс€

–егул€рный граф Ч граф, степени всех вершин которого равны, то есть кажда€ вершина имеет одинаковое количество соседей.

ѕростой граф Ч граф, в котором нет кратныхрЄбер и петель.

—в€зный граф Ч граф, в котором все вершины св€заны.

” вполне несв€зного графа все вершины изолированы.

ѕлатоновы графы Ч графы, образованные вершинами и ребрами п€ти правильных многогранников Ч платоновых тел: тетраэдра, куба, октаэдра, додекаэдра и икосаэдра.

ƒвудольный граф (или биграф, или чЄтный граф) Ч это граф , такой что множество вершин V разбито на два непересекающихс€ подмножества и , причЄм вс€кое ребро E инцидентно вершине из и вершине из (то есть соедин€ет вершину из с вершиной из ). “о есть, правильна€раскраскаграфадвум€ цветами. ћножества и называютс€ Ђдол€миї двудольного графа. ƒвудольный граф называетс€ Ђполнымї, если любые две вершины из и €вл€ютс€ смежными. ≈сли , , то полный двудольный граф обозначаетс€ .

 





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


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


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

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

Ќачинать всегда стоит с того, что сеет сомнени€. © Ѕорис —тругацкий
==> читать все изречени€...

1462 - | 1261 -


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

√ен: 0.008 с.