Некоторые классы конечных графов

Некоторые конечные графы имеют в литературе специальные названия. Охарактеризуем наиболее часто употребляемые термины.

Элементарные графы

Ранее мы определили элементарный граф как конечный граф без петель и параллельных ребер. Иногда элементарные графы называют также простыми или обыкновенными. Во многих приложениях рассмотрение таких графов является достаточным, и в некоторой литературе авторы используют термин «граф» для обозначения лишь элементарных графов.

Элементарные графы с петлями

Конечный граф без параллельных ребер (и без параллельных петель) называется элементарным графом с петлями. Элементарный граф является его частным случаем. Для элементарного графа с петлями можно использовать упрощенное определение (без упоминания отображения инциденции). Именно этот граф определяется как совокупность непустого множества V (множество вершин) и любого подмножества? из V&V (множество ребер). Ясно, что если |у| = п, то |?| < п + С"² = ^{П +} ^ .

Если в конечном графе любая пара вершин соединена единственным ребром и в каждой вершине есть ровно одна петля, то этот граф называется полным графом

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