Виды графов: тривиальные и полные графы, двудольные графы, орграфы и сети.


Определение 10.7. Граф, состоящий из одной вершины называется тривиальным.

Определение 10.8. Граф у которого любая пара вершин смежные называется полным графом.

Полный граф с Р вершинами обозначается kp. Его максимальное количество ребер находится по формуле .

Пример.

.

Действительно, можно заметить, что данный граф имеет 6 ребер.

 

Определение 10.9. Полный подграф некоторого графа называется кликой этого графа.

Граф, состоящий из простого цикла с k вершинами обозначается сk.

Определение 10.10. Двудольным графом (биграфом, чётным графом) называется такой граф G(V,E), что , при чём всякое ребро из множества Е инцидентно вершине из V1 и вершине из V2. Множество из V1 и V2 называется долями этого графа

Определение 10.11. Если двудольный граф содержит все ребра, соединяющие множества V1 и V2, то такой граф называют полным двудольным графом.

Теорема. Граф является двудольным тогда и только тогда, когда все его простые циклы имеют четную длину.

Определение 10.11. Если в графе ориентировать все ребра, то получится направленный орграф.

Определение 10.12. Если в графе полустепень захода некоторой вершины равна 0 (d+=0), то такая вершина называется источником.

Определение 10.13. Если в графе полустепень исхода некоторой вершины равна 0 (d-=0), то такая вершина называется стоком.

Определение 10.13. Направленный граф с одним истоком и одним стоком называется сетью.



Дата добавления: 2021-07-22; просмотров: 361;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.007 сек.