0
1
  1. Треугольником в графе называется тройка вершин, попарно соединенных между собой. Постройте схему полиномиального размера, которая по графу выдает 1 тогда и только тогда, когда в нем нет треугольников.

задан 29 Янв '15 1:58

А что имеется в виду под схемой?

(29 Янв '15 11:50) falcao

Как я понял, схема - это какой-то граф, соединенный конъюнкциями, дизъюнкциями, отрицанием и т.д.

(29 Янв '15 12:16) Leva319

Здесь можно было бы уточнить смысл используемых булевых переменных. Я так понимаю, их должно быть столько, сколько имеется рёбер в полном графе, то есть $%\frac{n(n-1)}2$%. Каждая из этих переменных равна 1 при наличии соответствующего ребра в графе. Я сейчас попробую коротко изложить свои соображения.

(29 Янв '15 13:33) falcao
10|600 символов нужно символов осталось
2

Я понял задачу так: у нас имеются булевы переменные вида $%x_{ij}$%, где $%1\le i < j\le n$%. Значение $%x_{ij}$% равно 1, если в графе соединена ребром $%i$%-я вершина с $%j$%-й.

Предположим, что в графе имеется треугольник, вершины которого имеют номера $%i < j < k$%. Тогда $%x_{ij}x_{ik}x_{jk}=1$% (конъюнкция). Таких троек имеется ровно $%C_n^3=\frac{n(n-1)(n-2)}6$%, то есть это полином от $%n$%. Беря дизъюнкцию (параллельное соединение) всех таких конъюнкций (последовательных соединений), каждая из которых содержит три элемента схемы, мы получаем схему из $%\frac{n(n-1)(n-2)}2$% элементов, по которой идёт ток в случае наличия хотя бы одного треугольника в графе. Осталось "инвертировать" ответ, добавив одно отрицание ("реле"). Количество элементов схемы увеличится на 1. Размер схемы имеет вид полинома третьей степени от $%n$%.

ссылка

отвечен 29 Янв '15 13:42

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

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

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

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

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

отмечен:

×133

задан
29 Янв '15 1:58

показан
661 раз

обновлен
29 Янв '15 13:42

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

по почте:

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

по RSS:

Ответы

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

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