Некоторые задачи, которые возникают при построении и анализе больших графов:

• Поиск часто встречающихся подграфов. 1 Это помогает ускорить нахождение сходства и сжатого представления графа, а также классификацию структур. 1
• Работа с сложными графами. 1 Например, в компьютерных сетях и социальных сетях метки вершин (например, URL-адреса) различны и их очень много. 1 В таких графах распределение степеней сильно нерегулярно, что приводит к затруднениям в выборе оптимальной формы хранения. 1
• Анализ графов, изменяющихся во времени. 1 Структура графа может быстро меняться. 1 В таких случаях интересен временной аспект структурного анализа. 1
• Вычисление характеристик графа. 2 К ним относятся, например, диаметр графа, центр графа, радиус графа, цикломатическое и хроматическое число. 2
• Построение минимального остовного дерева. 3 Это остовный лес, вес которого не превосходит вес любого другого возможного остовного дерева графа. 3
• Нахождение кратчайших путей. 25 Для этого используются, например, алгоритмы Дейкстры, Беллмана, построение дерева путей. 2