Граф, вершина, ребро

Под неориентированным графом (или короче графом) будем понимать такую произвольную пару G = <V, E>, что

.

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

Граф G задается множеством точек или вершин х₁,х₂, . . ., х_n ,которое обозначается через X, и множеством линий или ребер a₁, a₂, . . ., a_n , которое обозначается символом A, соединяющих между собой все или часть этих точек. Таким образом,граф G полностью задается (и обозначается) парой (X, А).

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

Линия, изображающая ребро {и, v}, или <и, v> (угловые скобки используются для обозначения дуг орграфа.), соединяет точки, изображающие вершины и, v причем во втором случае стрелка обозначает направление от и к v (рис. 1.1).

Рис. 1.1. а) Неориентированный граф; б) Ориентированный граф.