\(\textbf{Граф} - \) это математическая абстракция реальной системы любой природы, объекты которой обладают парными связями. Граф как математический объект есть совокупность двух множеств \(-\) множества самих объектов, называемого множеством \(\textbf{вершин}\), и множества их парных связей, называемого множеством \(\textbf{ребер}\). Элемент множества рёбер есть пара элементов множества вершин.

В качестве примера можно привести генеалогическое древо \(-\) вершинами будут выступать члены семьи, а ребра будут обозначать прямое родство.

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

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

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

Плоский граф - граф, который можно нарисовать на плоскости без пересечений ребер.