графы
6. Изоморфизм графов
7. Плоские графы
8. Операции над графами
9.
Способы задания графов3. Маршруты, цепи, циклы
10. Некоторые типы графов
FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.
Email: Нажмите что бы посмотреть
3. Маршруты, цепи, циклы
10. Некоторые типы графов
Deg(6)=3, deg(5)=1, 5 – висячая вершина
N(3)={2,1,6,4}, deg(7)=0, 7 – изолированная вершина
Вершина называется нечетной, если d(v) – нечетное число, четной если d(v) – четное число. Степень каждой вершины полного графа на единицу меньше числа его вершин.
Рис 2.1
2. Степень вершины
Свойства степени вершины
3. Маршруты, цепи, циклы
Так, на рисунке любая пара вершин, взятая из набора А,Б,В,Г,Д ,будет связной, т.к. от любой из них к любой можно "пройти" по ребрам графа.
Рис 4.2
Рис 4.1
4. Связность графов
Ориентированное ребро
Неориентированное ребро
Одна и та же вершина ориентированного графа может служить началом для одних ребер и концом для других, поэтому различают две степени вершины:
Степенью выхода вершины орграфа – число выходящих из вершины ребер;
Степенью входа вершины орграфа – число входящих в вершину ребер.
Рис 5.1
Рис 5.2
5. Ориентированные графы
Простым путем в ориентированном графе называется путь, в котором ни одна вершина не содержится более одного раза (Рис 5.3). На рис 5.4 изображен не простой путь.
Рис 5.3
Рис 5.4
Замкнутый путь в ориентированном графе называется ориентированным циклом или контуром. Длиной пути называется число ребер в этом пути.
Полным ориентированным графом называется граф, каждая пара вершин которого соединена в точности одним ориентированным ребром. Если ребра полного графа неориентированные, то граф соответственно будет полным неориентированным.
Ориентированный граф
6. Изоморфизм графов
Два графа называются изоморфными, если между множествами их вершин существует биективное (взаимно-однозначное) соответствие, такое, что вершины соединены ребрами в одном из графов в том и только в том случае, когда соответствующие им вершины соединены в другом графе.
Рис 7.1