Логический элемент Булева операция

элемент «и»

x1

f

x2

f

x1

x2

f

x

элемент «или»

элемент «не»

 

 

x ₁ x ₂

 

 

` x ₁

 

Входы одних логических элементов можно подсоединить к выходам других элементов и получить логическую сеть. Логическая сеть реализует некоторую булеву функцию. В случае контактных цепей выражение для функции с наименьшим числом вхождений переменных дает реализацию цепи с наименьшим количеством контактов. Простота логической сети может определяться как числом логических элементов, так и числом входов логических элементов. Кроме того, логические элементы характеризуются запаздыванием, поэтому быстродействие сети пропорционально числу ступеней сети (т.е. максимальному числу логических элементов, через которые проходит входной сигнал без учета инверторов). Представление функции в ДНФ дает двухступенчатую быстродействующую реализацию. Поэтому, для упрощения логической сети можно использовать минимизацию булевой функции методом Квайна, но при этом ввести понятие «стоимости» простой импликанты. В задаче минимизации числа логических элементов стоимость простой импликанты, содержащей две и более переменные, принимается равной 1, а стоимость простой импликанты из одной переменной – 0 (т.к. для ее реализации не требуется логический элемент «и»). В задаче минимизации общего числа входов логических элементов стоимость простой импликанты складывает из входов логического элемента «и», реализующего импликанту, и входов логического элемента «или». При построении минимальной ДНФ по множеству простых импликант, среди простых импликант выбирается множество с суммарной минимальной стоимостью простых импликант.

Теория графов

Часто бывает полезно и наглядно изобразить некоторую ситуацию в виде рисунка, состоящего из точек (вершин), представляющих основные элементы ситуации и линий (ребер), отражающих связи между элементами. Такие рисунки называются графами.

Граф может изображать сеть улиц в городе (вершины – перекрестки, улицы – ребра), блок-схемы программ (вершины – блоки, ребра – переходы), электрические цепи, географические карты и т.д. Более точно, граф определяется как упорядоченная пара (V, E), где V – непустое множество вершин, - множество ребер. Граф будем обозначать G. Число вершин графа называется его порядком и обозначается , число ребер обозначается как . Вершины u и v называются смежными, если существует ребро их соединяющее. Вершина v и ребро e инцидентны, если v является концом е.

v 1

v 2

v 3

v 4

Пример 4.1.

Вершины v ₁ и v ₂ являются смежными,

вершина v ₁ инцидента ребрам (v _1, v ₂) и (v _1, v ₃). .

 

 

Граф называется полным, если любые две его вершины смежны. Такие графы обозначаются K_n.

Пример 4.2.

K3

K4

K5

Различные ребра графа могут быть инцидентны одной и той же паре вершин, в этом случае они называются кратными, а сам граф – мультиграфом. Ребро может соединять вершину саму с собой, тогда такое ребро называется петлей, а граф – псевдографом. В некоторых задачах инцидентные ребру вершины рассматриваются в определенном порядке, тогда ребру приписывается направление от одной вершины к другой, и ребро называется дугой. Граф, все ребра которого являются дугами, называется орграфом. Иногда ребрам и дугам графа приписывают некоторые числа, такой граф называется взвешенным.

Граф называется помеченным, если всем его вершинам присвоены некоторые метки 1,2,…, n. Степенью вершины v называется число инцидентных ей ребер. Степень вершины обозначается deg v.

 

Пример 4.3.

v 3

v 1

v 2

v 4

 

 

 

Лемма ("о рукопожатиях"). Сумма степеней всех вершин графа равна удвоенному числу его ребер, т.е.

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

Пример 4.4.

v 1

v 2

v 3

v 4

v 5

Найдем степенную последовательность для графа G.

Выпишем степени всех вершин графа в соответствии с их номерами (2,2,3,2,1).

 

 

4.1 Способы задания графов

Пусть G – помеченный граф с n вершинами и m ребрами. Определим матрицу смежности A(G) следующим образом:

Матрица смежности квадратная, размера n ´ n.

Пример 4.5.

 

Можно заметить, что матрица смежности является симметричной, и количество единиц в каждой строке равно степени вершины, которой соответствует эта строка. По матрице смежности легко построить графическое представление графа.

Пример 4.6. Построить граф по матрице смежности

v 1

v 2

v 3

v 4

v 5

v 6

 

Можно определить матрицу инцидентности I(G), имеющую n строк и m столбцов, элементы которой задаются следующим образом:

 

Пример 4.7. Рассмотрим граф из примера 4.6, обозначив ребра.

v 2

e 1

v 1

v 3

v 4

v 5

v 6

e 2

e 3

e 4

e 7

e 5

e 6

 

В каждой строке матрицы инцидентности только два элемента отличные от 0 (или один, если ребро является петлей). Поэтому такой способ описания оказывается неэкономным. Отношение инцидентности можно задать также списком ребер графа. Каждая строка этого списка соответствует ребру, в ней записаны номера вершин, инцидентных ему.

Пример 4.8. Рассмотрим граф из примера 4.7. Список ребер имеет вид:

, , , , , , .

По списку ребер графа легко построить матрицу инцидентности, т.к. каждое ребро этого списка соответствует столбцу матрицы, а номера вершин в каждом элементе списка – это номера элементов строки матрицы инцидентности, которые равные 1.

Граф может быть представлен различными способами. Иногда не легко понять, одинаковы ли графы, изображенные разными чертежами или разными матрицами. Графы, отличающиеся только нумерацией вершин, называются изоморфными. Перенумерация задается строкой новых номеров вершин, расположенных в исходном порядке. Новая матрица смежности получается в результате перемещения каждого элемента a_ij в строку и столбец, т.е. в результате перестановки () строк и столбцов исходной матрицы. Можно выполнить все возможные перестановки строк и столбцов для того, чтобы убедиться в неизоморфности графов, но это потребует n! перестановок, что достаточно трудоемко.

Маршруты, цепи, циклы

Маршрутом от вершины u к вершине v или (u,v) маршрутом в графе G называется всякая последовательность вида

,

где e_k – ребро, соединяющее вершины и В случае орграфа – начало ребра е_k, a v_k – его конец. При этом вершину u называют началом маршрута, а вершину v – его концом. В маршруте некоторые вершины и ребра могут совпадать. Маршрут можно задавать последовательностью вершин а также последовательностью ребер . Число ребер в маршруте называется его длиной. Маршрут называется цепью, если в нем нет совпадающих ребер, и простой цепью – если дополнительно нет совпадающих вершин, кроме, может быть, начала и конца цепи. Если начало цепи (простой цепи) совпадает с ее концом, то такая цепь называется циклом (простым циклом). Граф без циклов называется ациклическим.

Пример 4.9.

(1,2,4,7) – простая цепь;

(1,2,4,7,8,4) – цепь, не являющаяся простой;

(1,2,4,7,8,4,2) – маршрут, не являющийся цепью;

(1,2,4,7,8,4,1) – цикл, не являющийся простым;

(1,2,4,1) – простой цикл.

Граф называется связным, если любые две вершины u и v в нем можно соединить (u,v) маршрутом. Легко видеть, что отношение связности на множестве вершин является отношением эквивалентности. Данное отношение разбивает множество вершин графа на классы, объединяющие вершины, которые можно связать друг с другом маршрутом. Такие классы называются компонентами связности. Связный граф имеет одну компоненту связности.

Пример 4.10.

v 1

v 2

v 3

v 4

v 5

v 6

v 7

Граф на рисунке имеет две компоненты связности.

 

Эйлеровы графы

Цикл в графе называется эйлеровым, если он содержит все ребра графа. Связный граф, в котором существует эйлеров цикл, также называется эйлеровым. Эйлеровый граф можно нарисовать не отрывая карандаша от бумаги.

сабли Магомета

звезда Давида

Пример 4.11.

Теорема Эйлера. Связный граф является эйлеровым тогда и только тогда, когда степени всех его вершин четные.

Для нахождения эйлеровой цепи в связной графе, который имеет вершины только четной степени, используют алгоритм Флери. Этот алгоритм использует два правила:

1. Стартуем из произвольной вершины графа и идем по ребрам, включая эти ребра в эйлерову цепь и удаляя их из графа.

2. Выбираем в очередной вершине путь по перешейку только в том случае, если нет пути по циклу. Перешейком называется ребро, не принадлежащее никакому циклу.

Пример 4.12.

v 1

v 2

v 3

v 4

v 5

e 1

e 2

e 3

e 4

e 5

e 6

e 7

e 8

Начать построение эйлерового цикла можно с любого ребра графа. Начиная с е₁, получим цикл

v ₁, e ₁, v ₅, e ₂, v ₄ ,e ₃, v ₃ ,e ₄, v ₄ ,e ₅ ,v ₁ ,e ₆ ,v ₃, e ₈, v ₂, e ₇ ,v ₁.

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