Лемма Кэли

В может получить и более впечатляющий результат. Пусть Н — любой граф с менее чем п вершинами. Тогда В может установить, сколько копий графа Н оказываются подграфами графа С. Пусть число верщин графа Н равно И. Рассмотрим любой подграф графа С, являющийся копией Н. Это — подграф точно п — к графов GJ. Таким образом, В нужно лишь найти число копий графа Н на каждой из своих карточек, суммировать это число по ] и разделить результат на л — к. Полученная сумма для числа копий графа Н в графе О является леммой Кэли — единственной важной (до сих пор) теоремой теории реконструкции. [c.306]

Лемма Кэли распространена на случай, когда граф Н имеет п вершин. Предположим, например, что граф Я — несвязный и имеет компоненты Я,, Я ,. .., Я т 2). Нас интересует, сколько копий графа Я имеется в О. Это эквивадентно вопросу о том, сколькими способами мы можем реализовать Н , Н2,. .., Я в ка- [c.306]

Давайте же растолкуем В, что он может во всех случаях найти число связных подграфов графа Gen вершинами и с данным числом ребер, скажем к. Известен ряд / -реберных стягиваемых подграфов графа G это число способов выбора К ребер из множества ребер графа G. И число несвязных подграфов оказывается реконструируемым с помощью расширенной нами леммы Кэли. [c.307]

Все это представляется увлекательным для человека, впервые знакомящегося с теорией реконструкции. Но когда он приобретет опыт, будет отрицательно к этому относиться, говоря, что это лишь набор упражнений по применению леммы Кэли. [c.308]

Оставляя эти особые случаи в стороне, я думаю, что будет справедливо сказать о том, что современная общая теория реконструкции остановилась на лемме Кэли. Многое можно извлечь из того факта, что некоторые полиномы,.соответствующие графу С, реконструируемы. Но эти полиномы могут быть выражены с помощью соответствующих подграфов графа С, которые могут быть адекватно перечислены с использованием леммы Кэли и наших расширенных вариантов ее. [c.308]

Лемма Кэли дает, по-видимому, обширную информацию о графе О, сообщая нам, сколько имеется подграфов с менее чем п верщинами для каждой возможной структуры. Однако загадочно, что тем не менее не было возможности показать с помощью любого доказательства, справедливого для каждого графа О, что вся эта информация соответствует только одному графу С. Тайна еще более сгущается в случае варианта, известного как предположение о реберной реконструкции. В этом варианте А перечисляет вместо вершин ребра и получает граф С , удаляя только У-е ребро. Соответствующий вариант леммы Кэли охватьшает все соответствующие подграфы графа О, точно сообщая нам, сколько их имеется от каждой возможной структуры. Но предположение о реберной реконструкции также до сих пор не проверено. [c.306]

Справочник химика 21

Химия и химическая технология