Граф Г(Х,U) определяется множеством X точек, называемых вершинами или узлами графа, и некоторым множеством U линий, соединяющих все или некоторые пары точек. Элементы из U называются ребрами графа. Последовательность ребер графа, где конец одного ребра является началом следующего, называется цепью. Цепь называется простой, если в ней никакое ребро не встречается дважды, и элементарной, если в ней никакая вершина не встречается дважды. Если начало и конец цепи совпадают, она называется циклом или петлей. Граф называется связным, если любые две его вершины соединены цепью. Связный граф без циклов, содержащий не менее двух вершин, называется деревом. Любые две вершины дерева соединены ровно одной цепью, а любая его цепь элементарна. Если порядок следования вершин ребра определен однозначно, т.е. на ребре стрелкой указано направление, то в этом случае ребро называется ориентированным ребром или дугой, выходящей из вершины и входящей в следующую вершину. Граф называется ориентированным, если он содержит только дуги, и неориентированным, если он содержит только ребра. Если в графе есть и ребра, и дуги, его называют смешанным. Вершину графа, в которую не входит ни одна дуга, называют начальной или корневой; вершину, из которой ни одна дуга не выходит - конечной или выходом, а остальные вершины - внутренними.
