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