Степенные последовательности. 
Теория графов

Эта глава посвящена теории степенных последовательностей.

Степенной последовательностью графа называется список степеней его вершин.

Часто по степеням вершин графа можно судить о его строении. Например, граф, в котором полусумма степеней вершин (т.е. число ребер) не меньше числа вершин, содержит цикл и т. д.

Естественно возникают следующие вопросы. Как связать между собой степени вершин графа? Как по списку степеней вершин судить о свойствах графа? Какова связь между графами с совпадающими списками степеней вершин? Можно ли построить граф с заданным списком степеней вершин и предписанными теоретико-графовыми свойствами и как это делать?

Изучение этих вопросов не только продиктовано внутренней логикой развития теории графов, но имеет и практическое значение. Если в виде графа представляется коммуникационная схема, узлам которой соответствуют вершины графа, а ребрам — каналы связей между вершинами и, например, максимально возможной связью. Такой граф соответствовал бы схеме с заданными пропускными способностями узлов и максимальной надежностью. Одна из исторически первых задач теории графов также относится к этому кругу проблем. Именно, в 1857 году А. Кэли, изучая насыщенные углеводороды, пришел к задаче перечисления деревьев, степени вершин которых равны 1 и 4.