Химические приложения топологии и теории графов - Кинг Р.
Скачать (прямая ссылка):
Вот почему решение задачи реконструкции для графов обычно начинают с
перечисления всех свойств графа G, которые могут быть дедуцированы на
основании графов Gj. Для начала В может найти число вершин и число ребер
графа G. Первое - это число данных ему карточек. Оно также больше числа
вершин, показанных на каждой карточке. Для того чтобы определить число
вершин, В может сложить вместе числа ребер на каждой из имеющих-
306
У Татт
ся у него п карточек и разделить результат на п - 2. Это обусловлено тем,
что каждое ребро графа G появляется точно в двух графах Gf. Этот метод
был бы неприменим в случае п = 2.
В может получить и более впечатляющий результат. Пусть Н - любой граф с
менее чем п вершинами. Тогда В может установить, сколько копий графа Н
оказываются подграфами графа G. Пусть число вершин графа Н равно И.
Рассмотрим любой подграф графа G, являющийся копией Я. Это - подграф
точно п - к графов Gj. Таким образом, В нужно лишь найти число копий
графа Я на каждой из своих карточек, суммировать это число по у и
разделить результат на л - к. Полученная сумма для числа копий графа Я в
графе G является леммой Кэли - единственной важной (до сих пор) теоремой
теории реконструкции.
Возможно, читатель возразит, что эгот процесс на практике может оказаться
довольно утомительным. У автора на это имеются, пожалуй, два возможных
ответа. Один из них: "Вы еще ничего не увидели". Другой: "Нам необходим
теоретический результат, и процессы, описанные в наших доказательствах,
вовсе не обязательно должны осуществляться на практике". Таким образом, в
данном случае тот факт, что В мог бы в принципе осуществить предлагаемую
процедуру, имея необходимое время и терпение, достаточен для того, чтобы
показать, что имеется лишь одно возможное значение для числа копий Я в
графе G; это число, как мы говорим, реконструируемо.
Лемма Кэли дает, по-видимому, обширную информацию о графе G, сообщая нам,
сколько имеется подграфов с менее чем п вершинами для каждой возможной
структуры. Однако загадочно, что тем не менее не было возможности
показать с помощью любого доказательства, справедливого для каждого графа
G, что вся эта информация соответствует только одному графу G. Тайна еще
более сгущается в случае варианта, известного как предположение о
реберной реконструкции. В этом варианте А перечисляет вместо вершин ребра
и получает граф Gj, удаляя только у-е ребро Соответствующий вариант леммы
Кэли охватывает все соответствующие подграфы графа G, точно сообщая нам,
сколько их имеется от каждой возможной структуры. Но предположение о
реберной реконструкции также до сих пор не проверено.
Лемма Кэли распространена на случай, когда граф Я имеет п вершин.
Предположим, например, что граф Я - несвязный и имеет компоненты Яр Я2,
... , Нт (т ^ 2). Нас интересует, сколько копий графа Я имеется в G. Это
эквивалентно вопросу о том, сколькими способами мы можем реализовать Я,,
Н2, ... , Нт в ка-
Проблема реконструкции
307
честве подграфов графа G, так что никакие две из этих реализаций не
являются взаимопересекающимися. Нам действительно известно число
способов, если взаимопересечение допустимо, поскольку мы знаем число
реализаций каждого графа //, в графе G с помощью леммы Кэли. В может
также определить, хотя это довольно утомительно, число способов, при
которых действительно существует взаимопересечение. Для любого графа К с
менее чем п вершинами он определяет число реализаций //,, Н2, ... , Нт в
графе К, таких, что объединением т реализаций является К. В таком случае
реализации некоторых двух подграфов из Н пересекаются. Затем В определяет
с помощью леммы Кэли число копий К в графе G, перемножает эти два числа и
суммирует полученную величину по графам К. Это дает ему числб таких
способов реализации Н{, Н2, ... , Нт в К, при которых существует
пересечение. Теперь, вычитая, он может найти число реализаций без
взаимопересечений, т. е: число копий Н в графе G.
Этот результат связан с теоремой о том, что несвязный граф G
реконструируем. Перед обсуждением этого отметим, что несвязные графы G
"распознаваемы", т. е. мы можем доказать их_несвязность, изучив графы Gj.
Если некоторый граф G, имеет то же число ребер, что и граф G, то граф G -
несвязный, поскольку он имеет vt в качестве изолированной вершины. Если
каждый граф Gy - несвязный, то несвязным является и граф G. Во всех
остальных случаях граф G - связный. Установив несвязность, В может
составить перечень всех несвязных графов с одним и тем же числом ребер.
Для каждого из них он может определить число его копий в G. Это число
будет отличным от нуля только для одного графа Н, и этим графом будет G.
Следует признать, что имеются более эффективные методы реконструкции
несвязного графа. Ну и что же? Однако эффективные реконструкционные
алгоритмы - это совсем иная тема.
Д'авайте же растолкуем В, что он может во всех случаях найти число
связных подграфов графа G с п вершинами и с данным числом ребер, скажем
