29
правок
Изменения
Новая страница: «{{Определение |definition = '''Контактная схема''' {{---}} это ориентированный ациклический [[Основн...»
{{Определение
|definition =
'''Контактная схема''' {{---}} это ориентированный ациклический [[Основные определения теории графов|граф]], на каждом ребре которого написана переменная или ее отрицание (ребра в контактных схемах называют ''контактами'', а вершины - ''полюсами'').
}}
==Принцип работы==
[[Файл:contact.png||right||200px]]
[[Файл:contactnot.png||right||200px]]
Зафиксируем некоторые значения переменным. Тогда '''замкнутыми''' называются ребра, на которых записана 1, ребра, на которых записан 0, называются '''разомкнутыми'''. Зафиксируем две вершины <tex>u</tex> и <tex>v</tex>. Тогда контактная схема вычисляет некоторую функцию <tex>f</tex> между вершинами <tex>u</tex> и <tex>v</tex>, равную 1 на тех наборах переменных, на которых между <tex>u</tex> и <tex>v</tex> есть путь по замкнутым ребрам.
==Примеры некоторых контактных схем==
|definition =
'''Контактная схема''' {{---}} это ориентированный ациклический [[Основные определения теории графов|граф]], на каждом ребре которого написана переменная или ее отрицание (ребра в контактных схемах называют ''контактами'', а вершины - ''полюсами'').
}}
==Принцип работы==
[[Файл:contact.png||right||200px]]
[[Файл:contactnot.png||right||200px]]
Зафиксируем некоторые значения переменным. Тогда '''замкнутыми''' называются ребра, на которых записана 1, ребра, на которых записан 0, называются '''разомкнутыми'''. Зафиксируем две вершины <tex>u</tex> и <tex>v</tex>. Тогда контактная схема вычисляет некоторую функцию <tex>f</tex> между вершинами <tex>u</tex> и <tex>v</tex>, равную 1 на тех наборах переменных, на которых между <tex>u</tex> и <tex>v</tex> есть путь по замкнутым ребрам.
==Примеры некоторых контактных схем==
