WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     | 1 | 2 || 4 | 5 |   ...   | 7 |

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);

6) Максимум: 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 {min(J (x1),, J (xn), f (1,,…,n))}.

n 1 n (1,…,n )Ek n ~ Действительно, для любого набора = (1,2,…,n) Ek рассмотрим значение правой части: если существует такое i, что i i, то J (i)= 0 и весь минимум станет равным нулю.

i Таким образом, правая часть станет равна max{0,0,…,0,min(J (1), J (2),…, J (n), f (1,2,…,n)),0,…,0}, 1 2 n а учитывая то, что в Pk Ja (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).

Глава II. Основы теории графов.

§15. Основные понятия теории графов. Изоморфизм графов. Связность.

Определение 1. Графом называется произвольное множество элементов V и произвольное семейство E пар из V. Обозначение: G = (V, E).

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

Определение 2. Если элементы из E рассматривать как неупорядоченные пары, то граф называется неориентированным, а пары называются рёбрами. Если же элементы из E рассматривать как упорядоченные, то граф ориентированный, а пары — дуги.

Определение 3. Пара вида (a, a) называется петлёй, если пара (a, b) встречается в семействе E несколько раз, то она называется кратным ребром (кратной дугой).

Определение 4. В дальнейшем условимся граф без петель и кратных рёбер называть неориентированным графом (или просто графом), граф без петель — мультиграфом, а мультиграф, в котором разрешены петли — псевдографом.

Определение 5. Две вершины графа называются смежными, если они соединены ребром.

Определение 6. Говорят, что вершина и ребро инцидентны, если ребро содержит вершину.

Определение 7. Степенью вершины (deg v) называется количество рёбер, инцидентных данной вершине. Для псевдографа полагают учитывать петлю дважды.

2.

4 3 Утверждение 1. В любом графе (псевдографе) справедливо следующее соотношеp ние: vi = 2q, где p — число вершин, а q — число рёбер.

deg i=Доказательство. Когда мы считаем степень одной вершины, мы считаем все рёбра, выходящие из неё. Вычисляя сумму всех степеней, мы получаем, что каждое ребро считается дважды, так как оно инцидентно двум вершинам (петли по определению степени также посчитаются дважды). Поэтому общая сумма будет равна удвоенному числу рёбер. Утверждение доказано.

Определение 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.

Определение 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 разбивается на связные подграфы, которые называются компонентами связности.

V1 V2 Vk … Связные компоненты графа 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 — конечное множество. Теорема доказана.

Лемма 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. Отсюда q = p – 1.

2) 3): по лемме 3 в G число связных компонент равно p – q = 1, то есть G — связный граф.

3) 4): при удалении одного ребра p – q = 2. Тогда по лемме 3 число связных компонент не менее чем p – q = 2.

4) 5): если G имеет цикл, то согласно лемме 1 можно выбросить одно ребро так, что граф останется связным. Согласно лемме 2, если добавить любое новое ребро к связному графу G на тех же вершинах, то появится цикл.

5) 1): если G не связный граф и вершины u, v лежат в разных связных компонентах графа G, то добавление к G ребра (u, v), очевидно, не порождает циклов, что противоречит 5). Отсюда следует, что G — связный граф. Теорема доказана.

§17. Корневые деревья. Верхняя оценка их числа.

Определение 1. Любое дерево, в котором выделена одна вершина, называемая корнем, называется корневым деревом.

Определение 2. 1) Граф, состоящий из одной вершины, которая выделена, называется корневым деревом.

2) Пусть имеются корневые деревья D1, D2, …, Dm с корнями v1, v2, …, vm, Di = (Vi, Ei), Vi Vj = (i j). Тогда граф D = (V, E), полученный следующим образом:

V = V1 V2 … Vm {v} (v Vi, i ), E = E1 E2 … Em {(v, v1), (v, v2), …,(v, vm)} и в котором выделена вершина v, называется корневым деревом.

3) Только те объекты являются корневыми деревьями, которые можно построить согласно пунктам 1) и 2).

При таком определении D1,D2,…,Dm называются поддеревьями дерева D.

v1 v2 vm … D1 D2 Dm … v Утверждение. Определения 1 и 2 эквивалентны.

Определение 3. Упорядоченным корневым деревом называется корневое дерево, в котором 1) задан порядок поддеревьев и 2) каждое поддерево Di является упорядоченным поддеревом.

Дерево с одной вершиной также является упорядоченным поддеревом.

Теорема 3. Число упорядоченных корневых деревьев с q рёбрами не превосходит 4q.

Доказательство. Рассмотрим алгоритм обхода упорядоченного дерева, называемого «поиском в глубину». Этот обход описывается рекурсивно следующим образом:

1) Начать с корня. Пока есть поддеревья выполнять:

2) перейти в корень очередного поддерева, обойти это поддерево «в глубину».

3) Вернуться в корень исходного поддерева.

В результате обход «в глубину» проходит по каждому ребру дерева ровно 2 раза: один раз при переходе в очередное поддерево, второй раз при возвращении из этого поддерева. В соответствии с обходом «в глубину» будем строить последовательность из нулей и единиц, записывая на каждом шаге нуль или единицу, причём нуль будем записывать, если происходит переход в очередное поддерево, а единицу, если мы возвращаемся из поддерева. Получим последовательность из 0 и 1 длины 2q, которую назовём кодом дерева. По этому коду однозначно восстанавливается дерево, поскольку каждый очередной разряд однозначно указывает, начинать ли строить новое очередное поддерево или возвращаться на ярус ближе к корню. Таким образом, упорядоченных корневых деревьев с q рёбрами не больше, чем последовательностей из 0 и 1 длины 2q, а их число равно 22q = 4q. Теорема доказана.

Изоморфизм корневых деревьев определяется так же, как и изоморфизм графов, но с дополнительным требованием: корень должен отображаться в корень. Для упорядоченных корневых деревьев также требуется сохранение порядка поддеревьев.

Следствие. Число неизоморфных корневых деревьев с q рёбрами и число неизоморфных деревьев с q рёбрами не превосходит 4q.

Доказательство. Выделяя в неизоморфных деревьях по одной вершине, мы получим неизоморфные корневые деревья. Упорядочивая поддеревья в неизоморфных корневых деревьях, мы получим различные упорядоченные корневые деревья. Поэтому число неизоморфных деревьев с q рёбрами не превосходит числа неизоморфных корневых деревьев с q рёбрами, которое, в свою очередь, не превосходит числа различных упорядоченных корневых деревьев с q рёбрами. Отсюда и из теоремы следует утверждение следствия. Следствие доказано.

§18. Геометрическая реализация графов.

Теорема о реализации графов в трёхмерном пространстве.

Определение. Пусть задан некоторый неориентированный граф G = (V, E). Пусть любой вершине vi графа G сопоставлена некоторая точка ai: vi ai, ai aj (i j), а любому ребру e = (a, b) сопоставлена некоторая непрерывная кривая L, соединяющая точки ai и aj и не проходящая через другие точки ak (k i, j). Тогда если все кривые, сопоставленные рёбрам, не имеют общих точек, кроме концевых, то говорят, что задана геометрическая реализация графа G.

геометрическая реализация графа Kне является геометрической реализацией графа KТеорема 4. Для любого графа существует его реализация в трёхмерном пространстве.

Доказательство. Возьмём в пространстве любую прямую l и разместим на ней все вершины графа G. Пусть в G имеется q рёбер. Проведём связку из q различных полуплоскостей через l. После этого каждое ребро графа G можно изобразить линией в своей полуплоскости и они, очевидно, не будут пересекаться. Теорема доказана.

§19. Планарные (плоские) графы. Формула Эйлера.

Определение 1. Граф называется планарным, если существует его геометрическая реализация на плоскости.

Определение 2. Если имеется планарная реализация графа и мы «разрежем» плоскость по всем линиям этой планарной реализации, то плоскость распадётся на части, которые называются гранями этой планарной реализации (одна из граней бесконечна, она называется внешней гранью).

Теорема 5 (формула Эйлера). Для любой планарной реализации связного планарного графа G = (V, E) с p вершинами, q рёбрами и r гранями выполняется равенство: p – q + r = 2.

Доказательство. Докажем теорему при фиксированном p индукцией по q. Так как G — связный граф, то q p – 1.

Pages:     | 1 | 2 || 4 | 5 |   ...   | 7 |



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.