Глава VIII. Степенные последовательности

Степенные последовательности

Эта глава посвящена теории степенных последова-тельностей. Напомним, что степенной последователь-ностью графа называется список степеней его вершин.

Часто по степеням вершин графа можно судить о его строении. Например, граф, в котором полусумма сте-пеней вершин (т. е. число ребер) не меньше числа вер-шин, содержит цикл (следствие 13.6); граф, степень каждой вершины которого равна двум, есть дизъюнкт-ное объединение циклов; граф, степень каждой вершины которого - четное число, не равное нулю, является объ-единением циклов (теорема 43.1) и т. д. В предыдущих главах есть и другие факты, поддающиеся интерпрета-ции подобного рода.

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

Подобные вопросы особенно интенсивно изучаются в настоящее время. Это не только продиктовано внутрен-ней логикой развития теории графов, но имеет и прак-тическое значение. Если в виде графа представляется коммуникационная схема, узлам которой соответствуют вершины графа, а ребрам - каналы связей между вер-шинами, то возникает задача построения графа с задан-ными степенями вершин и, например, максимально воз-можной связностью. Такой граф соответствовал бы схеме

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