Задача - перечисление - граф
Cтраница 1
Задача перечисления биокрашенных и бихроматических графов недавно была сформулирована с помощью построения новой бинарной операции на группах подстановок, названной экспоненциацией. [1]
При применении формул ( 7) и ( 8) к задачам перечисления графов суммируют каждое из этих соотношений по множеству всех графов, которые следует пересчитать. Член 1, просуммированный по всем графам, очевидно, дает общее число графов, - в то время как 2р дает число корневых графов. [2]
Три леммы, обсуждаемые ниже, составляют основу разнообразных подходов к задачам перечисления непомеченных графов. Тогда элементы х и у из X называются А-эквивалентными или подобными, если существует подстановка а из А, такая, что ах у. Классическим и немедленно получающимся результатом является утверждение о том, что введенное нами отношение есть эквивалентность. Классы эквивалентности называются орбитами, или системами транзитивности группы А. [3]
Три леммы, обсуждаемые ниже, составляют основу разнообразных подходов к задачам перечисления непомеченных графов. Тогда элементы х и у из X называются А - эквивалентными или подобными, если существует подстановка а из А, такая, что ах - у. Классическим и немедленно получающимся результатом является утверждение о том, что введенное нами отношение есть эквивалентность. Классы эквивалентности называются орбитами, или системами транзитивности группы А. [4]
Покажем сначала, пользуясь графами и направленными графами, что подразумевается под задачей перечисления графов. Затем разовьем эти предварительные понятия, чтобы кратко сформулировать нерешенные задачи. Будут даны ( без доказательств) некоторые методы, которые используются при перечислении графов. Наиболее важным из них является изящный и сильный метод перечисления Пойа. [5]
Пойа [49] дал изящное и ясное изложение в рисунках, которое помогает интуитивным соображениям при размышлении над задачами перечисления графов. [6]
Учитывая классическое равенство из теории графов: а0 р р cXj p, заключаем, что нужно только упомянуть о задачах перечисления графов с данным вершинным числом независимости Ро и с данным числом рх. Перечисление графов по этим параметрам кажется интуитивно более легким, чем перечисление графов с данными числами покрытий; однако из приведенного выше равенства это не следует. [7]
Мы должны особо подчеркнуть, что, в то время как перечисление 2-раскрашиваемых графов выполнимо ( об этом говорилось в § 4.3), задача перечисления иг-раскрашиваемых графов при т ss 3 остается нерешенной ( см. гл. [8]
Мы должны особо подчеркнуть, что, в то время как перечисление 2-раскрашиваемых графов выполнимо ( об этом говорилось в § 4.3), задача перечисления тп-раскрашиваемых графов при т 3 остается - нерешенной ( см. гл. [9]
 |
Число Ап простых связных фигур площади п. [10] |
Теорема Оттера [46] для деревьев была обобшена Норманом [43] для произвольных графов. Это предложение играет роль полезной комбинаторной леммы в решении некоторых задач перечисления графов. Недавно Рид [51] усовершенствовал свою теорему о суперпозициях для перечисления определенного класса графов общего вида. В целях исторической справедливости заметим, что перечисляющая теорема Пойа и несколько других относящихся к ней приемов подсчета были предвосхищены Ред-филдом в прекрасной статье [56], которая в основном осталась незамеченной. [11]
Например, всякий раз когда в нашем поле зрения появляется новый параметр, мы немедленно можем сформулировать соответствующую задачу перечисления. Задачи перечисления графов с данными параметрами естественным образом разбиваются на подмножества, соответствующие связанным между собой параметрам. [12]
Конечно, существует очень много трудных задач о маркированных графах, например задача Лизинга. Некоторые задачи перечисления маркированных графов, однако, так просты, что могут быть немедленно решены. [13]
Хотя разнообразная, усложненная, малопонятная и специализированная терминология может затуманить истинное положение вещей, но факт остается фактом: очень многие модельные ( схемные, структурные) и конфигурационные задачи становятся графическими по своей природе, если их соответствующим образом переформулировать. Более того, представив задачу на языке графов или родственных им образований, можно значительно легче выявить ее концептуальные трудности. Мы приводим здесь обширный набор задач перечисления графов, содержащий достаточный материал для изысканий специалистов нашего времени и последующих поколений. [14]
Не удивительно, что теория групп необычайно плодотворно взаимодействует с теорией графов. Для изложения этой темы нам понадобятся некоторые элементарные сведения из теории групп. В частности, мы определим несколько операций на группах подстановок. Эти операции играют важную роль в теории графов, поскольку они тесно связаны с операциями над графами; особенно велико их значение при решении задач перечисления графов. [15]
Страницы: 1