Виды графов

Виды графов

В этой статье я попытаюсь коротенько рассказать про основные виды графов, с примерами, разумеется.

Информации получилось достаточно много, так что, если вы ищете что-то конкретное, то воспользуйтесь поиском по странице (в большинстве браузеров это Ctrl + F).

 

Конечный граф

Это граф, имеющий конечное кол-во вершин.

Конечный граф
Конечный граф

 

Бесконечный граф

Граф, имеющий бесконечное кол-во вершин.

Бесконечный граф
Бесконечный граф

 

Пустой (нуль-граф)

Это граф, который не содержит ни вершин, ни связей.

 

Неориентированный граф

Граф, в котором направление связей не выделяется (все связи являются ребрами).

Т.е. по любой связи можно двигаться в обе стороны.

Неориентированный граф
Неориентированный граф

 

Ориентированный граф (орграф)

Граф, в котором направление связей принципиально (все связи являются дугами).

По любой связи можно двигаться только в одном, определённом направлении, обозначенном стрелочкой.

Ориентированный граф (орграф)
Ориентированный граф (орграф)

 

Смешанный граф

Граф, содержащий как рёбра, так и дуги.

Смешанный граф
Смешанный граф

 

Простой граф

Граф, не содержащий петель и кратных связей.

Простой граф
Простой граф

 

Мультиграф

Граф, который содержит кратные связи.

В неориентированном графе: существуют хотя бы две вершины, которые соединены более, чем одним ребром.

Неориентированный мультиграф
Неориентированный мультиграф

В ориентированном графе: существуют хотя бы две дуги, имеющие одно начало и один конец.

Ориентированный мультиграф
Ориентированный мультиграф

 

Псевдограф

Граф, имеющий петли и/или кратные связи.

Псевдограф
Псевдограф

 

Полный граф

Это граф, в котором любые две вершины соединены между собой, т.е. все вершины соединены со всеми.

Полный неориентированный граф
Полный неориентированный граф

 

Полный ориентированный граф
Полный ориентированный граф

 

Плотный граф

Это полный граф, у которого при каждой вершине имеется петля.

Плотный граф
Плотный граф

 

Связный граф

Только неориентированные графы.

Это такой граф, в котором любые две вершины соединяются каким-либо маршрутом.

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

Связный граф
Связный граф

 

Сильно связный граф

Только ориентированные графы.

Это тот же связный граф, но только для ориентированных графов.

В таком графе точно так же можно из любой вершины попасть в любую другую.

Сильно связный граф
Сильно связный граф

 

Слабо связный граф

Только ориентированные графы.

Граф, который не является сильно связным, но при замене всех дуг на рёбра становиться связным, т.е. нет изолированных вершин.

Слабо связный граф
Слабо связный граф

 

Дерево

Это связный или слабо связный граф, не содержащий циклов.

Вершины, из которых не выходит ни одна связь (т.е. они являются конечными), называются листьями.

Неориентированное дерево
Неориентированное дерево

В ориентированном дереве, вершина, в которую не входит ни одна дуга, называется корнем дерева.

Ориентированное дерево
Ориентированное дерево

 

Лес

Это граф, состоящий из нескольких, изолированных друг от друга, деревьев.

Лес
Лес

 

Граф-цикл

Граф, целиком состоящий из одного (только одного!) цикла.

Неориентированный граф-цикл
Неориентированный граф-цикл

 

Ориентированный граф-цикл
Ориентированный граф-цикл

 

Плоский граф

Граф, в данном изображении которого связи пересекаются только в вершинах (например, треугольник).

Плоский граф
Плоский граф

 

Планарный граф

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

Планарный граф

Планарный граф

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

 

Взвешенный (нагруженный) граф

Граф, каждой связи которого поставлено в соответствие некое значение (вес).

Вес обозначает какую-либо характеристику «пути», чаще всего его длину.

Взвешенный граф
Взвешенный граф

 

Двудольный граф

Двудольный (бихроматичный) граф
Двудольный (бихроматичный) граф

 

Эйлеров граф

Это граф, в котором существует цикл (замкнутый путь), проходящий по всем связям графа ровно по 1 разу.

Через одну и ту же вершину можно проходить несколько раз.

Циклов может быть несколько.

Неориентированный эйлеров граф
Неориентированный эйлеров граф

Эйлеровы циклы:

X1 – X2 – X5 – X4 – X3 – X1

X1 – X3 – X4 – X5 – X2 – X1

 

Ориентированный эйлеров граф
Ориентированный эйлеров граф

Эйлеров цикл:

X1 – X3 – X5 – X4 – X3 – X2 – X1

 

Гамильтонов граф

Граф, в котором существует цикл (замкнутый путь), проходящий через все вершины ровно по 1 разу.

Циклов может быть несколько.

Неориентированный гамильтонов граф
Неориентированный гамильтонов граф

Гамильтоновы циклы:

X1 – X4 – X5 – X2 – X3 – X1

X1 – X3 – X2 – X5 – X4 – X1

 

Ориентированный гамильтонов граф
Ориентированный гамильтонов граф

Гамильтонов цикл:

X1 – X5 – X3 – X4 – X2 – X1

TEXT.RU - 38.73%

Поделиться ссылкой:

Добавить комментарий

Зарегистрируйтесь или Войдите, чтобы оставить комментарий.

Системное сообщение