Теория графов — раздел дискретной математики, в котором системно изучают свойства графов. 1

В самом общем смысле граф — это множество точек (вершин, узлов), которые соединяются множеством линий (рёбер, дуг). 3

Теория графов широко применяется в решении экономических и управленческих задач, в программировании, химии, конструировании и изучении электрических цепей, коммуникации, психологии, социологии, лингвистике и в других областях. 1

Некоторые основные понятия теории графов:

• Граф — это геометрическая фигура, которая состоит из точек и линий, которые их соединяют. 1 Точки называют вершинами графа, а линии — рёбрами. 1
• Два ребра называются смежными, если у них есть общая вершина. 1
• Два ребра называются кратными, если они соединяют одну и ту же пару вершин. 1
• Ребро называется петлёй, если его концы совпадают. 1
• Степенью вершины называют количество рёбер, для которых она является концевой (при этом петли считают дважды). 1
• Вершина называется изолированной, если она не является концом ни для одного ребра. 1
• Вершина называется висячей, если из неё выходит ровно одно ребро. 1

Также теория графов — один из самых востребованных инструментов при создании искусственного интеллекта. 1