Упражнения для самостоятельного решения.

1. Являются ли формулы тождественно истинными:

1. 

2. (

3. (x y)  ((x  z)  y  z).

2. Построить таблицу значений функции алгебры логики:

а)

б)

в)

г)

д)

3. Приведите к СДНФ функцию .

4. Приведите к СКНФ функции

1)

2)

5. Привести двумя способами (алгебраическими преобразованиями и методом неопределенных коэффициентов) к виду полинома Жегалкина h = y  z  yz.

6. Построить полином Жегалкина функции

а)

б)

в)

г)

д)

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

а) .

б)

в)

г)

д)

е)

Графы и сети

Графом называется пара множеств (V, X), где V – множество вершин, а X – некоторое множество неупорядоченных пар элементов и из V, множество рёбер. Граф называется ориентированным (орграфом), если пары упорядочены. В этом случае ребра называют дугами. Граф конечен, если множества V, X конечны. Ребро вида называется петлёй. Рёбра и называются кратными. Договоримся под словом граф подразумевать, если не оговорено противное, конечный граф без кратных рёбер и без петель. Если в графе существует ребро , которое соединяет вершины а и b, то вершины а и b называют смежными, а вершину а и ребро x – инцидентными. Граф называется полным, если в нём любые две вершины смежны. Полный граф с р вершинами обозначается K_p. Например,

K ₂ : К₃ : К₄ : К₅ :

Рис.1

Степень вершины графа

Совокупность рёбер, инцидентных вершине , называется звездой вершины Число рёбер графа, инцидентных вершине называется степенью вершины обозначение deg , т.е. deg = .

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

Задать граф – описать множества его вершин и рёбер, а также отношения инцидентности. Для описания конечных графов достаточно перенумеровать вершины и рёбра.

Способ 1. Пусть – вершины графа G, x₁, … , x_h – рёбра. Отношение инцидентности можно определить матрицей инцидентности , имеющей h строк и n столбцов. Если ребро x инцидентно вершине , то = 1, в противном случае = 0. В матрице инцидентности ориентированного графа G, если вершина – начало ребра x_i, то = 1, а если конец ребра, то +1. Если x_i – петля, а – инцидентная ей вершина, то , где – любое число, отличное от 1, 0, 1. В остальных случаях = 0.

Способ 2. Отношение инцидентности можно задать списком рёбер графа. Каждая строка этого списка соответствует ребру, а в ней записаны номера вершин, этому ребру инцидентных.

Способ 3. В матрице смежности графа столбцам и строкам соответствуют вершины графа. Элемент этой матрицы равен количеству рёбер, инцидентных i-й и j-й вершинам, если в графе допускаются кратные рёбра.. Для ориентированного графа этот элемент равен количеству рёбер с началом в вершине i и концом в вершине j.

Изоморфизм графов

Пусть даны два графа Графы G₁ и G₂ называются изоморфными, если существуют взаимнооднозначные соответствия между множествами вершин и множествами рёбер этих графов, при этом соответствующие рёбра соединяют соответствующие вершины, т.е. если , , то = .

Изоморфизм графов обозначаем G₁  G₂. Множество всех графов разбивается на непересекающиеся классы изоморфности графов.

Пример. Все представители классов изоморфности орграфов с тремя вершинами и тремя рёбрами:

Рис. 2

Изоморфизм графа на себя называется автоморфизмом графа. Все автоморфизмы графа образуют группу относительно операции композиции отображений.

Дополнение графа G имеет в качестве множества вершин множество V, а две вершины в смежны  не смежны в G.

П ример. G: :

Рис. 3

Самодополнительный граф – это граф, который изоморфен своему дополнению. Наименьшие по числу рёбер нетривиальные самодополнительные графы.

Рис. 4

Подграф, маршрут, цепь, цикл

Граф называется подграфом графа , если . Подграф, не совпадающий с графом G и не являющийся пустым, называется собственным подграфом графа G. Подграф, содержащий все вершины графа, называется остовным. Маршрутом (путём) длины называется последовательноcть вершин и рёбер где ребро соединяет вершины и , , – начало пути, – конец. Если , то маршрут называется замкнутым. Если , то маршрут называется открытым. Открытый маршрут, в котором все вершины различны, называется цепью. Маршрут, в котором все рёбра различны, называется простым. Замкнутый (простой) маршрут называется циклом (простой цикл или элементарный). Если существует маршрут, соединяющий две вершины, то из рёбер этого маршрута можно построить цепь (для этого следует выбрать маршрут минимальной длины из рёбер данного). Длина кратчайшей цепи, соединяющей вершины a и b, называется расстоянием между этими вершинами . Если рёбра a и b не соединены цепью, то .

Свойства расстояния:

(1)

(2) ;

3. .

Пусть S – некоторое непустое множество вершин V графа , а – совокупность рёбер графа, обе вершины которых . Подграф графа G называется подграфом, порождённым S.