alt text

задан 31 Янв '15 14:49

10|600 символов нужно символов осталось
1

Попробую описать один из способов, хотя не исключаю, что есть какие-то более простые.

Граф будет эйлеровым тогда и только тогда, когда он связен, и степени всех вершин чётны. Для начала протестируем второе свойство. Для каждой вершины $%i$% составляем прямую сумму $%g(i)=f(i,1)\oplus f(i,2)\oplus\cdots\oplus f(i,n)$%. Реализация такой схемы требует полиномиального числа элементов (прямая сумма, она же xor, стандартно выражается через and, or, not). Нас интересует случай, когда все $%g(i)$% равны нулю. Берём их дизъюнкцию: $%g(1)\lor g(2)\lor\ldots\lor g(n)$%. Добавляем к ней отрицание, и получаем на выходе 1 тогда и только тогда, когда степени всех вершин чётны. Размер схемы, очевидно, полиномиален.

Теперь тестируем связность. Для этого собираем схему, которая "физически" реализует наш граф. В ней $%n$% узлов и $%O(n^2)$% рёбер. Теперь для каждой пары вершин $%1\le i < j\le n$% отводим два специальных проводка, между которыми идёт ток тогда и только тогда, когда вершины соединены путём в графе. Можно чуть упростить конструкцию, полагая $%i=1$%, то есть проверяя, с каждой ли вершиной графа соединена первая вершина -- для связности этого достаточно.

От всех "ответвлений" создаём последовательное соединение (конъюнкцию), по которому идёт ток в том и только в том случае, если он идёт по каждому из "ответвлений". Это даёт критерий связности графа на уровне схемы.

В конце берём конъюнкцию двух описанных выше схем, и получаем тест на эйлеровость.

ссылка

отвечен 31 Янв '15 17:56

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×941
×131

задан
31 Янв '15 14:49

показан
295 раз

обновлен
31 Янв '15 21:22

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru