Алексеев В.Б. Лекции по дискретной математике, страница 4

k-значные функции. Теорема о существовании конечной полной системыв множестве k-значных функций.1°. k-значные функции. Будем рассматривать конечный алфавит Ek = {0, 1, 2, …, k – 1}.Функцией k-значной логики назовём отображение вида f (x1, x2, …, xn): Ekn → Ek .Некоторые функции k-значной логики.1) Константы 0, 1, 2, …, k – 1 (всего — k);2) Тождественная функция f (x) = x;3) Отрицания: f (x) = x = x + 1 (mod k)— отрицание Поста,f (x) = ~ x = (k – 1) – x— отрицание Лукасевича;4) Сложение по модулю k: f (x, y) = x + y (mod k);5) Умножение по модулю k: f (x, y) = xy (mod k);136) Максимум: max (x, y);7) Минимум: min (x, y);k − 1, x = σ8) J σ (x ) = . 0, x ≠ σТеорема 15.

Система {0, 1, …, k – 1, max (x, y), min (x, y), J0 (x), J1 (x), …, Jk – 1 (x)} полна в Pk.Доказательство. Утверждается, что для любой функции f (x1, …, xn) ∈ Pk справедливопредставлениеf (x1 ,!, xn ) =max(σ1 ,!,σ n )∈Ekn{min(J (x ),", J (x ), f (σ ,σσ11σnn12)}, !, σ n ) .Действительно, для любого набора α~ = (α1 ,α 2 ,!,α n ) ∈ Ekn рассмотрим значение правой части: если существует такое i , что σi ≠ αi, то Jσ i (α i ) = 0 и весь минимум станет равным нулю.Таким образом, правая часть станет равна{()}max 0,0,!,0, min J α1 (α1 ), Jα 2 (α 2 ),!, J α n (α n ), f (α1 , α 2 ,!, α n ) ,0,!,0 ,а учитывая то, что в PkJa (a) = k – 1,получим, что правая часть равна просто f (α1 ,α 2 ,!,α n ) . Теорема доказана.Замечание.

min (x1, x2, x3) = min (x1, min (x2, x3)); min (x1, x2, …, xn) = min (x1, min (x2, … ,xn)).Аналогично определяется функция максимума от n переменных.2°. Особенности k-значной логики.1) В Pk существует континуум замкнутых классов (при k ≥ 3).2) В Pk существуют замкнутые классы с бесконечным базисом (при k ≥ 3).3) В Pk существуют замкнутые классы, не имеющие базиса (при k ≥ 3).14Глава II. Основы теории графов.§15.

Основные понятия теории графов. Изоморфизм графов. Связность.Определение 1. Графом называется произвольное множество элементов V и произвольное семейство E пар из V. Обозначение: G = (V, E).В дальнейшем будем рассматривать конечные графы, то есть графы с конечным множеством элементов и конечным семейством пар.Определение 2. Если элементы из E рассматривать как неупорядоченные пары, то графназывается неориентированным, а пары называются рёбрами.

Если же элементы из E рассматривать как упорядоченные, то граф ориентированный, а пары — дуги.Определение 3. Пара вида (a, a) называется петлёй, если пара (a, b) встречается в семействе E несколько раз, то она называется кратным ребром (кратной дугой).Определение 4. В дальнейшем условимся граф без петель и кратных рёбер называть неориентированным графом (или просто графом), граф без петель — мультиграфом, а мультиграф, в котором разрешены петли — псевдографом.Определение 5.

Две вершины графа называются смежными, если они соединены ребром.Определение 6. Говорят, что вершина и ребро инцидентны, если ребро содержит вершину.Определение 7. Степенью вершины (deg v) называется количество рёбер, инцидентныхданной вершине. Для псевдографа полагают учитывать петлю дважды.251743.86Утверждение 1. В любом графе (псевдографе) справедливо следующее соотношеpние: ∑ deg vi = 2q , где p — число вершин, а q — число рёбер.i =1Доказательство. Когда мы считаем степень одной вершины, мы считаем все рёбра, выходящие из неё.

Вычисляя сумму всех степеней, мы получаем, что каждое ребро считаетсядважды, так как оно инцидентно двум вершинам (петли по определению степени также посчитаются дважды). Поэтому общая сумма будет равна удвоенному числу рёбер. Утверждение доказано.Определение 8. Пусть множество вершин графа V = {v1, v2, …, vp}. Тогда матрицейсмежности этого графа назовём матрицу A = ||aij||, где aij = 1, если вершины vi и vj смежны(2, 3, … для мультиграфа или псевдографа) и 0 в противном случае, aii при этом равно числупетель в вершине vi.Определение 9. Два графа (или псевдографа) G1 = (V1 , E1 ) и G2 = (V2 , E2 ) называются изоморфными, если существуют два взаимно однозначных отображения φ1 : V1 → V2 иφ2: E1 → E2 такие, что для любых двух вершин u и v графа G1 справедливо φ2 (u, v) == (φ1 (u), φ1 (v)).Определение 10 (изоморфизм графов без петель и кратных рёбер).

Два графа G1 == (V1, E1) и G2 = (V2, E2) называются изоморфными, если существует взаимно однозначноеотображение φ1: V1 → V2 такое, что (u, v) ∈ E1 ⇔ (φ (u), φ (v)) ∈ E2.Определение 11. Граф G1 = (V1 , E1 ) называется подграфом графа G = (V, E), еслиV1 ⊆ V, E1 ⊆ E.15Определение 12. Путём в графе G = (V, E) называется любая последовательность видаv0, (v0, v1), v1, (v1, v2), …, vn – 1, (vn – 1, vn), vn.Число n в данных обозначениях называется длиной пути.Определение 13.

Цепью называется путь, в котором нет повторяющихся рёбер.Определение 14. Простой цепью называется путь без повторения вершин.Утверждение 2. Пусть в G = (V, E) v1 ≠ v2 и пусть P — путь из v1 в v2. Тогда в P можновыделить подпуть из v1 в v2, являющийся простой цепью.Доказательство. Пусть данный путь — не простая цепь. Тогда в нём повторяется некоторая вершина v, то есть он имеет вид: P1 = v0C1vC2vC3v2. Тогда он содержит подпуть P2 == v0C1vC3v2. Если в P2 повторяется некоторая вершина, то аналогично удалим ещё кусок итак далее.

Процесс должен закончиться, так как P1 — конечный путь. Утверждение доказано.Определение 15. Путь называется замкнутым, если v0 = vn.Определение 16. Путь называется циклом, если он замкнут, и рёбра в нём неповторяются.Определение 17. Путь называется простым циклом, если v0 = vn и вершины не повторяются.Определение 18. Граф G = (V, E) называется связным, если для любых вершин vi, vj ∈ V(vi ≠ vj) существует путь из vi в vj.Рассмотрим отношение vi → vj существования пути из vi в vj. Оно1) симметрично, так как (vi → vj) ⇒ (vj → vi),2) транзитивно, так как (vi → vj) & (vj → vk) ⇒ (vi → vk),3) рефлексивно, так как ∀i (vi → vi).Таким образом, получено, что vi → vj — отношение эквивалентности и множество вершинразбивается на конечное число классов эквивалентности: V → V1 ∪ V2 ∪ … ∪ Vk, Vi ∩ Vj = ∅ ⇐⇐ i ≠ j. При этом граф G разбивается на связные подграфы, которые называются компонентамисвязности.V1V2Vk…Связные компоненты графа G§16.

Деревья. Свойства деревьев.Определение 1. Деревом называется связный граф без циклов.Определение 2. Подграф G1 = (V1, E1) графа G = (V, E), называется остовным деревом вграфе G = (V, E), если G1 = (V1, E1) — дерево и V1 = V.Лемма 1. Если граф G = (V, E) связный и ребро (a, b) содержится в некотором цикле вграфе G, то при выбрасывании из графа G ребра (a, b) снова получится связный граф.Доказательство. Это утверждение следует из того, что при выбрасывании из графа Gребра (a, b) вершины a и b всё равно остаются в одной связной компоненте, поскольку из a вb можно пройти по оставшейся части цикла. Лемма доказана.Теорема 1. Любой связный граф содержит хотя бы одно остовное дерево.Доказательство.

Если в G нет циклов, то G является искомым остовным деревом. Если в G есть циклы, то удалим из G какое-нибудь ребро, входящее в цикл. Получится некоторый подграф G1. По лемме 1 G1 — связный граф. Если в G1 нет циклов, то G1 и есть искомое остовное дерево, иначе продолжим этот процесс. Процесс должен завершиться, таккак E — конечное множество. Теорема доказана.16Лемма 2.

Если к связному графу добавить новое ребро на тех же вершинах, то появится цикл.Доказательство. Рассмотрим произвольный связный граф G = (V, E). Пусть u ∈ V,v ∈ V, (u, v) ∉ E. Так как G — связный граф, то в нём есть путь из v в u. Тогда в G есть и простая цепь C из v в u. Поэтому в полученном графе есть цикл C, (u, v), v. Лемма доказана.Лемма 3. Пусть в графе G = (V, E) p вершин и q рёбер. Тогда в G не менее p – q связныхкомпонент.

Если при этом в G нет циклов, то G состоит ровно из p – q связных компонент.Доказательство. Пусть к некоторому графу H, содержащему вершины u и v, добавляется ребро (u, v). Тогда если u и v лежат в разных связных компонентах графа H, то число связных компонент уменьшится на 1. Если u, v лежат в одной связной компоненте графа H, точисло связных компонент не изменится. В любом случае, число связных компонент уменьшается не более чем на 1.

Значит, при добавлении q рёбер число связных компонент уменьшается не более чем на q. Так как граф G получается из графа G1 = (V, ∅) добавлением q рёбер, то в G не менее p – q связных компонент. Пусть теперь в G нет циклов, и пусть в процессе получения G из G1 добавляется ребро (u, v). Если бы u, v лежали уже в одной связнойкомпоненте, то в G, согласно лемме 2, возникал бы цикл. Следовательно, u, v лежат в разныхсвязных компонентах и при добавлении ребра (u, v) число связных компонент уменьшаетсяровно на 1.

Тогда G состоит ровно из p – q связных компонент. Лемма доказана.Теорема 2 (о различных определениях дерева). Следующие пять определений эквивалентны (p — число вершин, q — число рёбер):1) G — дерево;2) G — без циклов и q = p – 1;3) G — связный граф и q = p – 1;4) G — связный граф, но при удалении любого ребра становится несвязным;5) G — без циклов, но при добавлении любого ребра на тех же вершинах появляется цикл.Доказательство. Докажем следующие переходы: 1) ⇒ 2) ⇒ 3) ⇒ 4) ⇒ 5) ⇒ 1), откудабудет следовать, что из любого условия вытекает любое другое.1) ⇒ 2): так как G — связный граф и G не содержит циклов, то p – q = 1 по лемме 3.