множество объектов произвольной природы, изображаемых в виде точек (вершины А, В, С и так далее) и множества связей (линий), соединяющих пары вершин (например, АВ, АС, BD). Линии, связывающие вершины, могут быть неориентированными, тогда их называют ребрами, а такой граф — неориентированным. Если линии ориентированы, то их называют дугами, а граф, содержащий дуги, — ориентированным или орграфом. Две вершины графа, например А и В, называются смежными, если между ними существует ребро или дуга АВ, которые, в свою очередь, называются инцидентными этим вершинам. Вершина, например В, может быть соединена сама с собой петлей ВВ. Граф, состоящий только из вершин без связей, называется нульграфом. Граф, у которого любая пара вершин смежна, называется полным графом. Число ребер, инцидентных вершине, называют степенью этой вершины, например степень вершины А равна 4. Граф, в котором каждая вершина связана с любой другой вершиной некоторой последовательностью ребер (маршрутом), называется связанным графом.