Химические приложения топологии и теории графов - Кинг Р.
Скачать (прямая ссылка):
опубликовано).
19. Neumann P.M., частное сообщение.
20. Dugundji J., Gillespie P., Marquarding D., Ugi I., Ramirez F., In:
Chemical
Applications of Graph Theory, A.T. Balaban (Ed.), Academic Press, London,
1976, p. 107.
21. Gielen М., In: Chemical Applications of Graph Theory, A.T. Balaban
(Ed.), Academic Press, London, 1976, p. 261.
22. Neumann P.M., In: Topics in Group Theory and Computation, M.P.J.
Curran (Ed.), Academic Press, London, 1977, p. 82.
23. Cameron P.J., In: Combinatorics, M. Hall, Jr. J.H. van Lint (Eds.),
D. Reidel, Dordrecht, 1975, p. 419.
24. Tsusuku Т., Finite Groups and Finite Geometries, Cambridge Tracts in
Mathematics, V. 78, Cambridge University Press, Cambridge, 1982.
25*.- Berry R.S.f J. Chem. Phys., 1960, v. 32, p. 933.
ПРОБЛЕМА РЕКОНСТРУКЦИИ
У. Татт (W.T. Tutte)
Department of Combinatorics and Optimization, University of Waterloo,
Waterloo, Ontario N2L 3G1, Canada
Существует аналогия между графами комбинаторной теории и структурными
формулами органической химии. Структура графа, в котором отсутствуют
петли, определена, когда нам известно, сколько ребер связывает каждую
пару вершин. Излишне упрощая, говорят, что структура молекулы может быть
описана, если указать, сколько валентных связей соединяет каждую пару
атомов. Но аналогия имеется и здесь.
Иногда в комбинаторной задаче нам известны некоторые части графа, и мы
хотели бы соединить их вместе для реконструкции целого графа. В некоторых
исследованиях вывод о структуре органического соединения был сделан на
основании известных- структур продуктов разложения. В каждом случае мы
сталкиваемся с проблемой реконструкции.
Мы можем вкладывать довольно широкий смысл в понятие "проблема
реконструкции". Как часто в научных исследованиях мы имеем ряд частных
теорий, каждая из которых связана с особым случаем, и стараемся
скомбинировать их в одну теорию, охватывающую каждый случай! Разве это не
проблема реконструкции? Но, по-видимому, слишком претенциозно пытаться
создать теорию проблем реконструкции. Это должна быть теория теорий,
действующая на недоступном в настоящее время уровне абстракции.
Стандартная задача реконструкции в теории графов точно определена и легко
формулируется.. Ее отличие от химической задачи состоит в том, что она
пытается доказать реконструируемость всех графов, вместо того чтобы
ограничиться конечным числом случаев, представляющих интерес. Это модель,
в которой могут быть выделены и изучены чисто математические трудности
реконструкции.
В данном случае это теоретико-графовая задача. Представим себе, что
некто, называемый в дальнейшем А, строит граф G. Пусть это будет для
простоты граф в "строгом смысле слова", т.е. граф, в котором нет петель и
пар вершин, связанных более чем одним ребром. Число вершин от 1 до л
обозначим как и,, и2, ... , vn. Для
Проблема реконструкции
305
каждого целого числа j, входящего в этот интервал, А рисует на карточке
граф Gj, полученный из графа G в результате удаления г, и всех
инцидентных этой вершине ребер. Затем он вручает п рисунков второму
человеку В и предлагает ему в качестве задачи реконструировать граф G.
Не приносит никакого вреда, но и никакой пользы для В, если все эти п
карточек пронумерованы соответствующим образом от 1 до п. На своей
карточке для графа Gj В не найдет нумерации вершин этого графа. Ему не
сообщают, какие вершины на одной карточке соответствуют каким вершинам на
другой карточке. Фактически это оказывается тем, что ему необходимо
установить самому. Ему известна структура каждого графа Gj, но он не
знает, как перекрываются структуры, изображенные на разных карточках.
Итак, ясно, что задача, -поставленная перед В, имеет решение. Но
однозначно ли это решение? Специалист по теории графов P. JI. Брукс
хранит как реликвию прямоугольник, разрезанный на 13 неравных квадратов.
Он вырезал эти квадраты и передал своей матери, попросив решить задачу
реконструкции прямоугольника. Она сложила их вместе, получив
прямоугольник, отличающийся от разрезанного сыном прямоугольника.
Основываясь на этом удивительном открытии, Брукс и его сотрудники
разработали обширную математическую теорию. Но в реконструкционном
подходе в рамках теории графов В и не собирался соревноваться с г-жой
Брукс.
В соответствии с реконструкционным подходом задача, поставленная перед В,
имеет только одно решение, при условии что в графе G по крайней мере 3
вершины. Причины для исключения случая п = 2 очевидны. В дали бы две
карточки, на каждой из которых показана единственная вершина. Для графа G
имелось бы два решения: одно - граф, имеющий две изолированные вершины,
другое - граф, в котором две вершины связаны ребром.
Вероятно, задача для В не составляет трудности в случае любого графа G,
достаточно простого, чтобы А изготовил свои карточки в течение
приемлемого времени. Но доказательство единственности решения для каждого
члена бесконечного множества конечных графов до сих пор не найдено.
