Начальные понятия

Граф состоит из двух множеств – множества V, элементы которого называются вершинами, и множества Е, состоящего из пар вершин, эти пары называются ребрами графа. Это записывают так: G = (V, E), где G – имя графа.

Один момент в этом определении требует уточнения: считаем ли мы ребра и различными. Если да (и это распространяется на все ребра), то граф называется ориентированным (сокращенно орграф), в противном случае ­– неориентированным.

Говорят, что ребро соединяет вершины а и b. Если такое ребро в графе есть, то говорят, что вершины а и b в нем смежны. Заметим, что в графе может быть не более одного ребра, соединяющего данную пару вершин. Ребро типа , т.е. соединяющее вершину с ней же самой, называют петлей.

Говорят, что ребро инцидентно каждой из вершин а и b, а каждая из этих вершин инцидентна ребру е.

В дальнейшем, если не оговаривается иное, под графом понимается неориентированный граф без петель, такие графы называют обыкновенными. Для обозначения числа вершин и числа ребер графа будем обычно использовать буквы и .

Мультиграф – обобщение понятия графа. В мультиграфе могут быть кратные ребра, то есть несколько ребер, соединяющих одну и ту же пару вершин. Иначе говоря, в мультиграфе Е является мультимножеством, то есть одна пара может входить в него несколько раз.