Определение. Пара (V(G), E(G)) называется простым графом, если V(G) – непустое конечное множество элементов, называемых вершинами (или узлами, или точками), а E(G) – конечное множество неупорядоченных пар различных элементов из V(G), называемых ребрами (или линиями). В простом графе данную пару вершин может соединять не более чем одно ребро.

Между элементами множества вершин и множества ребер определено отношение инцидентности. Говорят, что ребро е инцидентно вершинам v₁, v₂, если оно соединяет эти вершины и наоборот, каждая из вершин v₁, v₂  инцидентна ребру е.

Рассмотрим графическое представление графов (табл. 3.1).

Таблица 3.1 Графическое представление графов

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

Пример 68.

Определение. Если  ребро задаётся упорядоченной парой вершин, то оно является ориентированным. Если каждое ребро графа ориентированное, то граф называется ориентированным или орграфом.

Иногда удобно преобразовать неориентированный граф в ориентированный – заменой одного неориентированного ребра парой ребер с противоположной ориентацией.

Приведем ряд понятий и определений для ориентированных и неориентированных графов. Там, где это специально не оговорено, те же понятия и определения переносятся без изменений на ориентированные и неориентированные псевдографы.