Основные сведения о графах

Графом называется конечное множество вершин, соединенных ребрами. Если ребра являются направленными, то граф называется ориентированным (орграфом). Направленные ребра часто называют дугами. Каждое ребро соединяет две вершины, причем, в графе две вершины соединяются только одним ребром. В противоположном случае используется понятие мультиграфа (графа с кратными или параллельными ребрами).

Две вершины графа называются смежными, если они соединены ребром. Вершина инцидентна ребру, если ребро соединяет ее с другой какой-то вершиной. Петля – ребро, соединяющее вершину саму с собой. Степень вершины – это число инцидентных ей ребер. Цепью называется последовательность неповторяющихся ребер, соединяющих какие-либо две вершины графа. Замкнутая цепь в графе называется циклом.

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

Ребра графа могут иметь вес, который может интерпретироваться, например, как длинна ребра.

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