Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Тема 11. Частичные булевы функций




Тема 11. Частичные булевы функций

Краткая теория

Булева функция называется частичной, если она определена не на всем множестве , а лишь на некотором его подмножестве. Частичные функции можно задавать аналогично общим функциям одномерными и двумерными таблицами с учетом того, что соответствующие наборы не пишутся, либо на соответствующих наборах значение функции игнорируется. Особый интерес вызывает задача доопределения частичных булевых функций с целью возможности записи их аналитическими выражениями, а в частности минимизации. Основная идея состоит в том, чтобы так доопределить частичную булеву функцию, чтобы ее МДНФ была самой короткой из всех возможных доопределения.

 

 

Примеры решения задач

Задача. Минимизировать частичную булеву функцию

Решение:

Графический метод.

x y z  
 
   
   
 
   
 
 
 

 

Анализируя полученный результата очевидно, что функцию  необходимо доопределить следующим образом:

x y z  
 
 
 
 
 
 
 
 

 

МДНФ: .

Аналогично можно проводить рассуждения и для метода Квайна и для метода карт Карно. В общем случае необходим полный перебор всех возможных дополнений.

 

Упражнения

1. Минимизировать различными методами частичную булеву функцию:

a)

b)

c)

 

Дополнительные упражнения

2. Минимизировать методом карт Карно частичную булеву функцию:

a)

b)

 

Тема 12. Различные способы задания графов. Операции над графами

Краткая теория

Граф  ( ) определяется двумя множествами: V – множество вершин, Е – множество ребер (дуг). Элементы из Е представляют собой неупорядоченные (упорядоченные) пары из V.

Граф содержащий только ребра называется неориентированным графом (неограф), а граф содержащий только дуги – ориентированным графом (орграф).

Операция над графами (без кратных ребер и петель):

1. Дополнением графа  (обозначается ) называется граф  множество вершин которого совпадает с множеством вершин исходного графа, а множество ребер (дуг) состоит из всех тех ребер (дуг) которые дополняют данный граф до полного графа.

2. Объединением графов  и  (обозначается ) называется граф  такой, что , .

3. Пересечением графов  и  (обозначается ) называется граф  такой, что .

4. Соединением (сложением) графов  и  (обозначается ), при условии  и  называется граф  такой, что , .

5. Удаление вершины  из графа  (обозначается ) дает граф  такой, что , .

6. Удаление ребра  из графа  (обозначается ) дает граф , где .

 

Примеры решения задач

Задача. Для графически заданного графа найти матрицы смежности и инцидентности.

Неориентированный граф Ориентированный граф
     

Решение:

Матрица смежности графа

Неориентированный граф Ориентированный граф
 

Матрица инцидентности графа

Неориентированный граф Ориентированный граф
 

 

Упражнения

1. Для графа заданного матрицей смежности найти графическое задание и матрицу инцидентности:

a) ; b) ;   c)

2. Для графа заданного матрицей смежности найти графическое задание и матрицу инцидентности:

a) ; b) .  

3. Выполните действия и найдите соответствующую матрицу смежности для графа :

a)  = ;

b)  = ;

c)  = ;

d)  = ;

e)  = ;

f)  = ( ) – ;

g)  = ( ) – (1, 3);

где , ,

матрицы смежности для графов ,  и  соответственно.

 

Тема 13. Минимальные деревья

Краткая теория

Деревом называется связный граф без циклов.

Матрицей весов графа называется матрица смежности в ячейках которой стоят веса соответствующих ребер (дуг) и знак бесконечности в случае отсутствия соответствующего ребра.

Минимальным деревом называется остовное дерево графа с минимальным суммарным весом ребер.

Жадный алгоритм построения минимального дерева:

На каждом шаге алгоритма берется ребро с минимальным весом, не образовывающее циклов в строящемся графе.

Алгоритм ближайшего соседа построения минимального дерева:

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

Алгоритм удаления максимальных циклических ребер:

На каждом шаге алгоритма удаляется ребро с максимальным весом образующее цикл в модифицируемом графе.

 

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...