Контактная схема — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Определение |definition = '''Контактная схема''' {{---}} это ориентированный ациклический [[Основн...»)
(нет различий)

Версия 22:46, 1 октября 2013

Определение:
Контактная схема — это ориентированный ациклический граф, на каждом ребре которого написана переменная или ее отрицание (ребра в контактных схемах называют контактами, а вершины - полюсами).


Принцип работы

Contact.png
Contactnot.png

Зафиксируем некоторые значения переменным. Тогда замкнутыми называются ребра, на которых записана 1, ребра, на которых записан 0, называются разомкнутыми. Зафиксируем две вершины [math]u[/math] и [math]v[/math]. Тогда контактная схема вычисляет некоторую функцию [math]f[/math] между вершинами [math]u[/math] и [math]v[/math], равную 1 на тех наборах переменных, на которых между [math]u[/math] и [math]v[/math] есть путь по замкнутым ребрам.

Примеры некоторых контактных схем