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

• Вершина — точка в графе, отдельный объект. 1
• Ребро — линия, соединяющая две вершины графа. 3 Одну вершину могут связывать множество рёбер. 3
• Степень вершины — количество рёбер, входящих или исходящих из вершины. 3
• Изолированная вершина — вершина с нулевой степенью. 1
• Висячая вершина — вершина со степенью 1. 1
• Подграф — граф, вершины и рёбра которого являются подмножествами другого графа. 3
• Полный граф — граф, в котором каждые две вершины соединены одним ребром. 1
• Путь или маршрут — это последовательность смежных рёбер. 1
• Цикл или контур — цепь, в котором последняя вершина совпадает с первой. 1
• Взвешенный граф — граф, в котором у каждого ребра и/или каждой вершины есть «вес» — некоторое число, которое может обозначать длину пути, его стоимость и т. п.. 1
• Связный граф — граф, в котором существует путь между любыми двумя вершинами. 1
• Дерево — связный граф без циклов. 1 Между любыми двумя вершинами дерева существует единственный путь. 1

Теория графов широко применяется в компьютерных науках и информационных технологиях. 2 Некоторые области использования:

• Компьютерные сети — моделирование маршрутизации и топологии сети. 5
• Социальные сети — анализ связей между пользователями. 5
• Базы данных — оптимизация запросов и управление зависимостями данных. 5
• Поисковые системы — алгоритмы ранжирования страниц, такие как PageRank. 5
• Навигаторы и интернет-карты — различные места или текущее местоположение пользователя можно представить как вершины графа, а соединяющие их дороги — как рёбра графа. 3
• Механизм рекомендаций на различных сайтах — теория графов здесь используется для поиска объектов, статей или событий, которые могут заинтересовать пользователя, опираясь на его предыдущие действия. 3