В математике графы используются для отображения связей между объектами. Связанные объекты называются вершинами V графа, а связи между ними — ребрами E.
Если два объекта соединены между собой ребром, то они называются смежными.
Степень (валентность) вершины — это количество ребер, которые соединяются с ней.
Размер графа |Е| — общее количество ребер графа. Количество вершин графа |V| называется порядком графа.
Ребра графом могут обладать весом, такие графы называют взвешенными. Например, для графа, объекты которого представляют собой города, вес может быть расстоянием между двумя городами или количеством времени, которое требуется для перемещения между ними.
Ориентированные графы — это графы, ребра которых имеют направление. Ребра неориентированных графов, наоборот, направление не имеют.
Граф, в котором между двумя вершинами находится более одного ребра, называется мультиграфом, такие ребра также называют кратными.
Петля графа — это ребро, которое соединяется со своей собственной вершиной.
Простым графом называется граф, в котором нет кратных ребер и петель.
Полный граф — это простой граф, в котором каждая вершина напрямую соединена с каждой другой.
Последовательность ребер называется путем. Путь, который начинается и заканчивается на одном и том же ребре, называется циклом.
Путь и цикл называются простыми, если они не проходят через одну вершину более одного раза.
