Некоторые методы анализа последовательностей степеней вершин в графе:

• Теорема Эрдёша — Галлаи. 13 Утверждает, что невозрастающая последовательность может быть последовательностью простого графа только если её сумма чётна и выполняется определённое неравенство. 13
• Критерий Гавела — Хакими. 1 Позволяет построить полиномиальный алгоритм нахождения простого графа с заданной реализуемой последовательностью. 1
• Преобразование последовательностей. 3 Задаёт как минимум одну вершину графа, все инцидентные ей рёбра и множество вершин с новыми требуемыми дополнениями степеней. 3 Затем оставшиеся вершины упорядочивают по невозрастанию дополнений степеней. 3
• Спектральный и кластерный анализ. 2 Анализ графов на основе спектров его матриц. 2 В качестве матрицы обычно используется либо матрица смежности, либо лапласиан. 2 Спектр лапласиана используют для поиска кластеров вершин в графе, то есть выделения обособленных (слабо связанных) групп. 2