Экстремальные графы

Полный граф – любые две вершины смежны или каждая вершина графа является доминирующей.

Обозначается, .

Пустой граф – не имеет ребер. Обозначается через .

Псевдограф – граф, содержащий петли и кратные ребра.

Мультиграф – граф, не содержащий петель, но с кратными ребрами.

Простой граф – конечный граф без петель и кратных ребер.

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

Нуль-граф – граф без вершин и без ребер.

Тривиальный граф – граф с одной вершиной, (1, 0)-граф, , .

Однородный или регулярный граф – все вершины имеют равную степень.

Например:

Двудольный граф (биграф) – множество вершин графа V можно разбить на два непересекающиеся подмножества и таких, что каждое ребро графа имеет одну концевую вершину в V₁, а вторую – в V₂, причем , а .

Полный двудольный граф – двудольный граф, у которого любые две вершины, входящие в разные доли и , смежны. Обозначается _,

Звезда – полный двудольный граф .