- •Томск – 2014
- •ТЕМА 1. Основные понятия и определения теории графов
- •1.1. ОПРЕДЕЛЕНИЕ ГРАФА
- •В общем случае множество U можно представить в виде
- •1.2. Классы графов
- •1.3. СПОСОБЫ ЗАДАНИЯ ГРАФОВ
- •1.3.1 Геометрический
- •1.3.2. Описание графа через предикат (инцидентор) P
- •1.3.3. Матричный
- •1.4. Числовые характеристики вершин графа
- •1.5. МАРШРУТЫ, ЦЕПИ И ЦИКЛЫ
- •1.6. ОПРЕДЕЛЕНИЕ ЧИСЛА МАРШРУТОВ ДЛИНЫ "L" НА ГРАФЕ
- •Тема 2. Операции на графах
- •2.1. Удаление вершины
- •2.2. Удаление ребра
- •2.3. Замыкание (отождествление) вершин
- •2.4. Стягивание вершин графа по ребру
- •2.5. Симметрическая разность графов
- •2.6. Пересечение графов
- •2.7. Объединение графов
- •ТЕМА 3. Части графа
- •3.1. ПОДГРАФ
- •3.2 Частичный граф.
- •Тема 4. Взвешенные графы. Метрика графа
- •4.1. Основные понятия и определения
- •4.3. Алгоритм построения матрицы метрики графа
- •4.3.1. Описание алгоритма
- •Тема 5. Структурный анализ графов
- •5.1. Связность графа
- •5.2. Скелет графа
- •5.4. Максимальные полные и максимальные пустые подграфы
- •5.5. Клика графа.
- •5.6. Алгоритм нахождения всех максимальных пустых и всех максимальных полных подграфов (максимальных клик) в графе общего вида
- •Тема 6. Раскраска графов
- •6.1. Правильная раскраска. Хроматическое число
- •Тема 7. Маршруты специального вида
- •7.1. Алгоритм Флери построения эйлерова цикла
- •7.2. Обходы графа вида гамильтоновой цепи, гамильтонова цикла, гамильтонова пути и контура.
- •7.3. Пример решения задачи коммивояжера c помощью алгоритма Литтла
- •Тема 8. Двудольные графы
- •8.1. Основные положения
- •8.2. Венгерский алгоритм нахождения максимального паросочетания в двудольном графе
- •Тема 9. Компоненты связности
- •9.1. Основные определения
- •9.2. Способ определения числа компонент связности
- •9.3. Алгоритм вычисления числа компонент связности графа
- •Тема 10. Оптимальные потоки в транспортных/информационных сетях
- •10.1. СЕТЬ (транспортная, информационная)
- •10.2. Поток в сети
- •10.3. Задача о максимальном потоке
- •10.4. Алгоритм Форда — Фалкерсона.
- •10.5. Пример решения задачи о максимальном потоке с помощью алгоритма Форда-Фалкерсона
- •8. Алгоритм нахождения минимального разреза сети
- •Раздел 2. Переключательные функции и их разложения
- •2.1. Переключательные функции и способы задания
- •2.2. Булевы функции (бф)
- •2.3. Аналитическое представление булевых функций
- •2.3.1. Булева алгебра функций и эквивалентные преобразования в ней
- •2.3.2. Представление переключательных функций в виде многочленов.
- •2.4. Функционально полные системы
- •2.5. Примеры
- •2.6. ПЕРЕЧЕНЬ ЗАДАНИЙ НА ЛАБОРАТОРНЫЕ РАБОТЫ
- •Список литературы
119
f14 = `x`y Ú x`y Ú `x y .
f14 = K0 Å K1 Å K2 = x y Å xy Å x y = (x Å 1)( y Å 1) Å ( x + 1) y Å x( y + 1) = = 1Å x Å x Å y Å y Å xy Å xy Å xy = 1Å xy.
2.4. ФУНКЦИОНАЛЬНО ПОЛНЫЕ СИСТЕМЫ
Система функций å называется функционально полной системой, если любая логическая функция может быть представлена формулой над å , т.е. являться суперпозицией функций из å .
Теорема. Всякая логическая функция может быть представлена булевой формулой, т.е. как суперпозиция дизъюнкции, конъюнкции и отрицания.
Действительно, для всякой логической функции, кроме константы «0», таким представлением может служить её СДНФ. (Дизъюнкция конституент «1», равных «1» на тех же наборах, что и заданная функция, называется СДНФ переключательной функции).
Константу «0» также можно представить булевой формулой x`x .
Из теоремы следует, что система å = {&, , ¬} является функционально полной:
f ( x1 , x2 , , xn ) = K j1 K j 2 K jm
где Kji – это наборы переменных, где функция принимает значение «1». СДНФ функции f представляет собой разложение функции по всем n переменным.
Согласно принципу двойственности, справедливому в алгебре Буля, имеем следующий вывод: ¾ любая булева функция f(x1, x2, … , xn) может быть представлена в виде конъюнкции дизъюнкций её аргументов на тех наборах их значений, на которых f(x1, x2, … , xn ) принимает значение «0». Таким представлением булевой функции служит совершенная конъюнктивная нормальная форма (СКНФ).
120
Представление булевых функций двух аргументов в формах СДНФ и СКНФ приведены в таблице 2.3.
Таблица 2.3 |
|
|
|
|
|||
|
|
|
|
|
|
|
|
x |
0 |
0 |
1 |
1 |
СДНФ |
СКНФ |
|
y |
0 |
1 |
0 |
1 |
|||
|
|
||||||
f0(x,y) |
0 |
0 |
0 |
0 |
не имеет |
(x Ú y)( x Ú `y)( `x Ú y)× |
|
× ( `x Ú `y) |
|||||||
|
|
|
|
|
|
||
f1(x,y) |
0 |
0 |
0 |
1 |
x y |
(x Ú y)( x Ú `y)( `x Ú y) |
|
|
|
|
|
|
|
|
|
f2(x,y) |
0 |
0 |
1 |
0 |
x×`y |
(x Ú y)( x Ú `y)( `x Ú `y) |
|
|
|
|
|
|
|
||
f3(x,y) |
0 |
0 |
1 |
1 |
x×`y Ú x y |
(x Ú y)( x Ú `y) |
|
|
|
|
|
|
|
||
f4(x,y) |
0 |
1 |
0 |
0 |
`x y |
(x Ú y)( `x Ú y) ( `x Ú `y) |
|
|
|
|
|
|
|
||
f5(x,y) |
0 |
1 |
0 |
1 |
`x y Ú x y |
(x Ú y)(`x Ú y) |
|
|
|
|
|
|
|
|
|
f6(x,y) |
0 |
1 |
1 |
0 |
`x y Ú x` y |
(x Ú y) ( `x Ú `y) |
|
|
|
|
|
|
|
||
f7(x,y) |
0 |
1 |
1 |
1 |
`x y Ú x` y Ú x y |
x Ú y |
|
|
|
|
|
|
|
|
|
f8(x,y) |
1 |
0 |
0 |
0 |
`x×` y |
( x Ú `y)( `x Ú y)( `x Ú `y) |
|
|
|
|
|
|
|
||
|
|
|
|
|
` |
|
|
f9(x,y) |
1 |
0 |
0 |
1 |
`x× `y Ú x y |
( x Ú `y)( `x Ú y) |
|
|
|
|
|
|
|
|
|
f10(x,y) |
1 |
0 |
1 |
0 |
|
|
|
|
|
|
|
121 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
`x×`y x`y |
( x `y)( `x `y) |
||||
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
f11(x,y) |
1 |
0 |
1 |
1 |
`x×`y x ` y x y |
( x `y) |
||||
|
|
|
|
|
|
|
|
|
|
|
f12(x,y) |
1 |
1 |
0 |
0 |
`x×`y `x y |
( `x y)( `x `y) |
||||
|
|
|
|
|
|
|
|
|
|
|
f13(x,y) |
1 |
1 |
0 |
1 |
|
|
|
y |
||
`x×`y `x y x y |
|
x |
||||||||
|
|
|
|
|
|
|
|
|
|
|
f14(x,y) |
1 |
1 |
1 |
0 |
|
|
|
|
|
|
`x×`y `x y x`y |
|
x |
y |
|||||||
|
|
|
|
|
|
|
|
|
|
|
f15(x,y) |
1 |
1 |
1 |
1 |
`x×`y `x y x`y |
не имеет |
||||
|
|
|
|
|
x y |
|
|
|
|
|
122
2.5. ПРИМЕРЫ
Пример 1.
Логическую функцию f(x1, x2, x3 )=(x1 ~ ¬x2) → ((x1 x3 ) & x2) представить булевой формулой - в виде СДНФ.
Решение.
1.Функция f (x1, x2, x3 ) задана не булевой формой.
2.По исходной формуле восстановим её таблицу истинности.
3.По таблице истинности составим СДНФ заданной функции:
f (x1,x2 ,x3 )= x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3
Пример 2. Привести к ДНФ функцию:
f (x, y, z) = xy x(y xz)(x(y z) yz)
Решение.
f (x, y, z) = xy Ú x(y Ú xz)(x(y Ú z) Ú yz) =
= xy Ú (xy Ú xxz) × x(y Ú z) × yz = xy Ú xy(x Ú (y Ú z)) × yz = = xy Ú xy(x Ú yz) × (y Ú z) = xy Ú xy(x y Ú xz Ú y yz Ú yzz) =
xy Ú xy(x y Ú xz Ú yz) = xy Ú xy(x y Ú yz) = xy Ú xyz = y(x Ú xz) = y(x Ú z) = = xy Ú yz.
Пояснение к решению.
При проведении эквивалентных преобразований функции f(x,y,z) применяли правила де Моргана, законы действия с константами 0 и 1
(x ¬x =1)
и закон идемпотентности.
x xy = x·1 xy = x·(y y) xy = xy xy xy xy =x y .
123
Пример 3.
Привести к СДНФ функцию: f (x,y,z ) = xy ¬x y ¬z
Решение.
f (x, y, z) = xy Ú xyz = xy × 1Ú xyz = xy × (z Ú z) Ú xyz = = xyz Ú xyz Ú xyz.
Пример 4.
Представить булеву формулу x1 x2 ¬x2 ( x3 x4 ) в базисе {& , ¬} и в базисе { ,¬}.
Решение.
Применим правила де Моргана и правило двойного отрицания.
а) в базисе {&,¬}: f = x1 x2 ¬x2 ( x3 x4 ) =
б) = |
|
x x |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
Ú |
|
|
|
× |
|
|
× |
|
|
|
|
= |
|
|
|
|
|
|
|
× |
|
|
× |
|
|
× |
|
|
|
. |
|||||||
|
2 |
x |
2 |
x |
3 |
x |
4 |
x x |
2 |
|
x |
2 |
x |
3 |
x |
4 |
|||||||||||||||||||||||
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
||||||||||||||||
= |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
2 |
|
|
2 (x3 x4 ) = |
|
|
1 |
|
|
2 x2 |
|
|
|
|
. |
|
|
|||||||||||||||||||
|
x |
x |
|
x |
x |
x |
x3 x4 |
|
|
||||||||||||||||||||||||||||||
в базисе { ,¬} |
|
|
f = |
|
x1 x2 ¬x2 ( x3 |
|
|
x4 ) |
= |
|
|
|
|
Пример 5. Упростить булеву формулу:
f(x1, x2 , x3) = x1 x1 x3 ¬x1 x2 x3 x 2 ¬x3
Решение:
f (x1 , x2 , x3 ) = x1 x1 x3 x1 x2 x3 x2 x3 =
x1(1 x3) x1 x2 x3 x2 x3 = x1 x1 x2 x3 x2 x3 = = x1 x2 x3 x2 x3 = x1 x2.
Пример 6.
Доказать тождество: x1 ¬x1x2x3 = x1 x2x3 .
Доказательство.