Cтраница 4
Однако интенсивное развитие дискретной математики, начавшееся в послевоенные годы, и в частности тематики, связанной с перечислением графов ( начало последней положила статья Харари [32], в которой он использовал неопубликованные результаты Пойа), привело к необходимости поиска новых ( более общих и достаточно тонких) методов перечисления. [46]
Применение теоремы Пойа к перечислению этих орбит в соответствии с их весами приводит к следующей разновидности формулы Пойа для перечисления графов. [47]
Учитывая классическое равенство из теории графов: а0 р р cXj p, заключаем, что нужно только упомянуть о задачах перечисления графов с данным вершинным числом независимости Ро и с данным числом рх. Перечисление графов по этим параметрам кажется интуитивно более легким, чем перечисление графов с данными числами покрытий; однако из приведенного выше равенства это не следует. [48]
Учитывая классическое равенство из теории графов: а0 Ро р at Pi, заключаем, что нужно только упомянуть о зада чах перечисления графов с данным вершинным числом независим мости Р0 и с данным числом рг Перечисление графов по эти 4 параметрам кажется интуитивно более легким, чем перечислений, графов с данными числами покрытий; однако из приведенного выше равенства это не следует. [49]
Мы должны особо подчеркнуть, что, в то время как перечисление 2-раскрашиваемых графов выполнимо ( об этом говорилось в § 4.3), задача перечисления иг-раскрашиваемых графов при т ss 3 остается нерешенной ( см. гл. [50]