Граф – это множество вершин и множество ребер, элементами которого являются пары вершин.

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

Виды графов:

• Ориентированный граф – граф с ориентированными ребрами (имеющими направление; отображаются линиями со стрелками);
• Взвешенный граф – граф, ребра которого имеют вес (число, поставленное в соответствие ребру);
• Полный граф – граф со всеми возможными ребрами;
• Подграф – граф, содержащий подмножество вершин данного графа и подмножество инцидентных им (соединяющих) ребер;
• Связный граф – граф, в котором между любыми двумя вершинами есть путь;
• Псевдограф – граф, в котором допустимы кратные ребра и петли.