МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РЕСПУБЛИКИ КАЗАХСТАН

Некоммерческое акционерное общество

«Алматинский университет энергетики и связи»

Кафедра высшей математики

 

 

 

 

 

 

Л.Н. Астраханцева

ДИСКРЕТНАЯ МАТЕМАТИКА

Учебное пособие

для студентов всех форм обучения специальностей

5B0704 – Вычислительная техника и программное обеспечение,

5B0703 – Информационные системы

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Алматы 2011

 

 

УДК 519.6 (075.8)

ББК 22.176 Я 73

А 91 Дискретная математика:

Учебное пособие /Л.Н. Астраханцева;

АУЭС. Алматы, 2011.- 78 с.

 

ISBN – 601 – 7098 – 78 - 0

 

         

          Пособие представляет собой переработанные и дополненные лекции по дискретной математике, читаемые автором в АУЭС, оно включает четыре раздела, традиционно изучаемые в курсе дискретной математики: элементы теории множеств и отношений, элементы математической логики, теории графов и комбинаторики. Содержание разделов взаимно связано друг с другом. В доступной форме изложены основные теоретические сведения, приведены примеры и решённые задачи, помогающие усвоить и закрепить изучаемый материал. Пособие предназначено для студентов всех форм обучения специальностей 5В070400 – Вычислительная техника и программное обеспечение и 5В070300 – Информационные системы.

Ил. 72, табл. 14, библиогр. – 16 назв.

                                                                                     

 

                                                                                               ББК 22.176 Я 73

 

 

 

РЕЦЕНЗЕНТ: КазНУ, канд. физ.-мат. наук, доц. У.К. Койлышов.
    АУЭС, канд. физ.-мат. наук, доц. М.Ж. Байсалова.

                             

 

 

 

Печатается по плану издания Министерства образования и науки Республики Казахстан на 2011г.

 

 

 

 

 

 

© НАО «Алматинский университет энергетики и связи», 2011г.

 

 

 

 

1 Элементы теории множеств.

 

1.1  Множества

 

Понятия множества и элемента множества являются первичными (т.е. не определяемыми с помощью других, более простых понятий) такими, как, например, точка и прямая. Под множеством понимается совокупность некоторых объектов (предметов), которые называются элементами множества. Элементы множеств различны. Приняты следующие обозначения: A, B, X,… - множества; a, b, x, x1, x2,…- элементы множеств;- элемент  принадлежит А, - элемент не принадлежит А; N – множество натуральных чисел; Z – множество целых чисел; Q – множество рациональных чисел; I - множество иррациональных чисел; R – множество действительных чисел; C – множество комплексных чисел; Ø – пустое множество (не содержит ни одного элемента).

Конечные множества состоят из конечного числа элементов.

Бесконечные – из бесконечного числа элементов.

Способы задания множеств:

а) перечислением элементов, например,  X={x1, x2,…, xn},

A = {2,4,5,6,8,…};

б) с помощью характеристического свойства:  A={x| Р(x)}, где P(x) – свойство Р, которым обладает элемент x, например, A={x| x=};

в) порождающей процедурой, которая описывает способ получения элементов из уже имеющихся элементов, например, множество M={1,2,4,8,16,…} можно задать так: 1) 1M; 2)mM → 2mM.

Определения:

          а) множество В называется подмножеством множества А (обозначается ), если каждый элемент множества В является элементом множества А: ,  - знак включения;

б) множества А и В называют равными, если они состоят из одних и тех же элементов:  и ;

в) если  и , то В является собственным подмножеством множества А:  - строгое включение.

Заметим, что для обозначения отношения включения применяют как знак строгого, так и не строгого включения, как для собственных, так и для несобственных подмножеств. И только если требуется различить эти подмножества, различают и эти знаки. Не следует путать знаки и  - верно, - не верно.

Множества могут быть элементами других множеств. Множество, элементами которого являются множества, иногда называют семейством и обычно обозначают прописными (готическимими) буквами латинского алфавита. Совокупность всех подмножеств множества А называется его булеаном или множеством-степенью. Обозначается Р(А) или 2А. Таким образом, Р(А) = {B|BA}. Булеан множества из n элементов, содержит 2n элементов.

Пример 1.1.1 - A={1,2,3},Р(А) ={Ø,{1},{2},{3},{1,2},{1,3},{2,3}, A}.

Р(А) содержит 8 элементов, 8=2.

Обычно в конкретных рассуждениях элементы всех множеств берутся из одного достаточно широкого множества U, которое называется универсальным или универсумом. Для наглядного изображения множеств используют диаграммы Эйлера-Венна, на которых множества обозначаются точками кругов внутри прямоугольника, точки которого – множество U- универсум (см, рисунок 1.1.1, где A Р(U)).

 

 

 

 


                             

Рисунок 1.1.1

 

Операции над множествами.

 Р(U) следующие операции определяются так:

а) объединение (сумма) (обозначается , +): АВ = {x| xА или xВ}; б) пересечение (произведение) (, ):  АВ = {x| xА и xВ};

в) разность ( А \ В; А – В):  А \ В = {x| xА и xВ};

г) симметрическая разность или кольцевая сумма (, , +): АВ=

=(А \ В)(В \ А) = {x| (xА и xВ) или (xВ и xА)};

д)дополнение множества А ():={x|x и xА}= U \ A. Иллюстрация

операций над множествами диаграммами Эйлера-Венна на рисунке 1.1.2.

 

                                                                              

                           АВ                                                    AB

                                                     

                            А \ В                                                     АВ

 

 

                                                                                

 

                                                    Рисунок 1.1.2

         

 

          Операции объединения и пересечения допускают обобщения:

A1 A2An = ,   A1A2An = .

 

          Свойства операций над множествами

          Для преобразования теоретико-множественных выражений, упрощения записей, доказательств теорем и свойств необходимо знать свойства операций над множествами. Рассмотрим важнейшие из этих свойств. Пусть задан универсум U, тогда A, B, C U выполняются свойства:

 

Т а б л и ц а 1.1.1

1        Идемпотентность        

           АА=А                                                         АА=А

2        Коммутативность

          АВ= ВА                                                    АВ=ВА

3        Дистрибутивность

          АС)=( АВ)( АС)               АС)=( АВ)( АС)

4        Ассоциативность

          АС)=( АВ)С                         АС)=( АВ)С

5        Свойство поглощения

          АА)=А                                               А А)=А

     6 Свойства нуля и единицы (констант)

              АØ=А                                                             АØ= Ø

              АU=U                                                             АU= A

 7 Закон де Моргана

          =                                                     =

     8 Закон двойного отрицания ( двойного дополнения или инволютивности)

                =A

    9 Свойство дополнения

                  A=U                                                              A= Ø

         

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

1 Доказательство с помощью диаграмм:

 

 

 

 

 

 

а)

                           АВ                                 

                                                                      

          в)                                                                   

                            

                                                            

                                              

                                                       Рисунок 1.1.3

 

          На последних рисунках в пунктах а) и в) отмечена одна и та же область, что доказывает тождество.

          2 Докажем = формальными рассуждениями.ем

В формальных рассуждениях исходят из того, что А=В А  В и

В  А, а последнее имеет место по определению отношения включения: АВ(xA  xB) и ВА(xB  xA), поэтому:

          а) x xАВ  xA и xB  x и x  x;

          б) x  x и x  xA и xB  xАВ.

          Теорема. Для любых множеств А и В следующие условия эквивалентны:

          а) АВ;

          б) АВ=А;

          в) АВ =В;

          г) А \ В = Ø;

          д) В =U.

          В примере 1.1.2 свойства операций использованы для упрощения выражения.

          Пример 1.1.2 - .

 

          Разбиения и покрытия множеств

          Пусть дано множество А. А ={A1, A2, A3, … An}- множество подмножеств А (семейство подмножеств).

          Определение. А  называется покрытием множества A, если

1. Ai  А (AiA, Ai≠Ø);    2. A=.

          Определение. А  называется разбиением множества А, если

1. Ai  А (AiA, Ai≠Ø);   2. A=;  3.Ai, Aj А  [AiAj  А iАj = Ø].

          Пример 1.1.3 -  А={1,2,3}. А1= {{1,2},{2,3},{1,3}} – покрытие;

А2= {{1},{2},{3}} – разбиение; А3= {{1},{2,3}} – разбиение;

А4= {{1},{3}} – множество подмножеств множества А (ни булеан, ни

покрытие, ни разбиение).

          Пример 1.1.4. - N– множество натуральных чисел.

N0 , N1 - множества чётных и нечётных чисел.  N ={ N0, N1}- разбиение N.

         

          Прямое произведение множеств

          Упорядоченную последовательность из элементов x1,x2,…,xn будем обозначать (x1,x2,…,xn) или <x1,x2,…,xn> и называть          кортеж  длины n,

упорядоченный набор из n элементов, вектор длины nn-ка (энка). xii-ая координата или компонента. Если n=2, то (x1,x2) – пара, упорядоченная двойка; n=3 -  (x1,x2,x3) – тройка, упорядоченная тройка; n=0 -  < > - кортеж, не содержащий элементов.

          Если =(x1,…xn), =(y1,…yn), то . Ясно, что (1,2) ≠ (2,1), {1,2}={2,1}.

          Определение. Прямым (декартовым) произведением множеств А и В (обозначается А×В) называется множество таких пар (a,b), что aA и bВ:

А×В = {(a,b)| aA и bВ}.

Обобщение прямого произведения: A1×A2×…×An={(a1,a2,…,an)| a1A1, a2A2 ,…, anAn}. Если A=B, то A×A=A2 ;   A×A×…×A=An ;  A1=A; A0={Ø}.

 

                                                                                   n 

          Пример 1.1.5  - A={1,2}, B={1,2,3}.

A×B ={(1;1),(1;2),(1;3),(2;1),(2;2),(2;3)};

B×A = {(1;1),(1;2),(2;1),(2;2),(3;1),(3;2)}; A×B ≠ B×A;

A= {(1,1),(1,2),(2,1),(2,2)};

          Пример 1.1.6  -  R×R = R2 = {(a,b)|a,bR, (a,b) – точки плоскости}.

 

1.2  Отношения

 

          При решении различных задач практики часто требуется учитывать связи или отношения между элементами одного и того же или разных множеств. Например, если имеем множество стран мира, то можно рассматривать между странами такие отношения: «в стране x населения больше, чем в стране y» или «страны х и у имеют общую границу»; если имеем множества мужчин, женщин и детей, то можно рассматривать отношение «х и у родители z» и т.д.

           Определение. n-местным отношением P (n-местным предикатом) на множествах А12,…,Аn называется любое подмножество прямого произведения этих множеств: PA1×A2×…×An и P={(x1,x2,…xn)|A1,…,xnAn}. То, что элементы x1,x2,…xn связаны соотношением Р записывается  (x1,…,xn) P или P(x1,…,xn). Если PAn, то Р – n-местное отношение на множестве А. n=1, то P- одноместное (унарное) отношение или свойство; n=3, то PA1×A2×A3 – трёхместное (тернарное) отношение.

          Наиболее часто встречаются и хорошо изучены бинарные отношения (n=2) или соответствия PA1×A2 или P={(x,y)|xA1, yA2}. Записывают P(x,y) или xPy . Например, вместо <(x,y) или (x,y)< записывают  x<y. Далее будем рассматривать бинарные отношения, называя их просто отношениями.

          Определение. Областью определения отношения Р (обозначается DP) называется DP ={x| (x,y)P для некоторого y}; областью значений (обозначается EP) называется EP ={y| (x,y)P для некоторого x} (т.е. DP- это множество первых координат пар Р, EP – вторых).

          Отношение можно задать перечислением элементов, характеристическим свойством, графически, с помощью матриц.

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

          Определение. Пусть A={a1,a2,…,am}, B={b1,b2,…,bn} и P  A×B. Матрица [P] =(pij), размера m×n, называется матрицей отношения Р , если , i=1,2,…,m; j=1,2,…,n.

          Пример 1.2.1 -  A1={1;2}, A2={3;4}. A1×A2={(1,3), (1,4),(2,3),(2,4)}.

P1={(1;3)}, P2={(1;3);(1;4);(2;3)}, тогда , .

          Пример 1.2.2 -  A={2,3,4,5,6,7,8}; P={(x,y) | x,yA, y делится на x, x ≤3}  = {(2,2) (2,4),(2,6),(2,8),(3,3),(3,6)}.

          Графическое задание Р, где по осям координат отмечены элементы множества А, а на плоскости –точки с координатами (x,y), такие что (x,y)P:  

 

Рисунок 1.2.1

 

          Матричное задание Р: .

     Рассмотрим примеры других способов графического задания отношений: пусть A={a,b,c}, B={1,2,3}, P1={(a,2),(b,1),(c,2)}, P2 ={(a,b),(b,b),(c,a)}. На рисунке 1.2.2 показаны отношение P1 между множествами А и В и отношение P2 на множестве A.

Рисунок 1.2.2

 

     Определения. Пусть P  A×B, P={(a,b)|aA, bB}.

а) P-1обратное Р P-1 = {(b,a)|(a,b)P}, P-1 B×A;

б) - дополнение P={(a,b)|(a,b)P},  A×B;

в) I – тождественное отношение на множестве А (иногда обозначается

id). I={(a,a)|aA}, IA2 (называют также диагональю в A2 , т.к. его матрицей является единичная матрица);

г) U – универсальное отношение  U ={(a,b)|aA и bA}, т.е. U=A2.

          Определение. Композицией (произведением) бинарных отношений

P1  A×B и P2  B×C (обозначается P1P2) называется отношение

Р=P1P2 = {(a,c)|aA, cC и bB, что (a,b) P1 и (b,c)  P2}.

Рисунок 1.2.3

 

          Пример 1.2.3 -  A={1,2,3}, B={x,y}; C={ ■, ▲, ●, *}.

Пусть P1={(1,x),(1,y),(3,x)}, P2={(x,■),(x,▲),(y,●),(y,*)}, тогда

P1P2={(1,■),(1,▲),(1,●),(1,*),(3,■),(3,▲)}.

          Пример 1.2.4 -  P1={(x,x+2)|xZ+}, P2={(x,x2)|xZ+}, тогда

P1P2={(x,(x+2)2)| xZ+},  P2P1={(x,x2+2)| xZ+}, где Z+ множество целых положительных чисел.

          Теорема. Для любых бинарных отношений P, Q, R выполняются следующие свойства:

а) (P-1)-1=P;

б) (PQ)-1=Q-1P-1;

в) (PQ) R=P(QR).

        

         Основные свойства матриц бинарных отношений

1        Пусть P,Q A×B, [P]=(pi,j), [Q]=(qi,j).

[PQ] =(pij+qij) =[P]+[Q], где элементы матриц складываются по

 правилам: 0+0=0, 1+0=0+1=1+1=1; [PQ]=(pij*qij)=[P]*[Q], где  элементы матриц перемножаются по обычным правилам: 0*0=0*1=0*1=0, 1*1=1.

          2 Если PA×B, QB×C, то [PQ]= - обычное умножение матриц, но элементы матриц [P] и [Q] складываются и умножаются по правилам из свойства 1.

          3 Если P-1 отношение, обратное к  P, то [P-1]=[P]T.

          4 Если PQ и [P]=(pij), [Q]=(qij), тогда  pij≤qij.

          5 Если I–тождественное отношение, то-единичная матрица.

          6 Если - дополнение Р, то [] равна матрице отношения Р, в которой нули заменены единицами и единицы нулями.

          Пример 1.2.5 -

, ,  тогда ;

; ;

, .

 

     Свойства отношений

          Пусть PA2. Отношение Р называется

          а) рефлексивным aA (a,a)P;

          б) антирефлексивным aA (a,a)P или  [(a,b)P a≠b];

          в) симметричным a,bA (a,b)P (b,a)P;

          г) антисимметричным a,bA (a,b)P и (b,a)Pa=b;

          д) транзитивнымa,b,cA (a,b)P и (b,с)P(a,c)P.

          Заметим, что если

          а) P-рефлексивное IP,  [P]= ;

          б) P – симметричное P=P-1,  [P]=[P]T;

          в) Р - антисимметричное РР-1 I, [PP-1]=[P]*[P-1], все элементы последней матрицы вне главной диагонали равны 0;

          г) P- транзитивное PPP, т.е. если [PP]=(aij),  [P]=(pij), то aij≤pij.

          Пример 1.2.6 -  Проверим, какими свойствами обладает  отношение P = {(1,2),(2,3),(3,2)}A2, А = {1,2,3}. Составим матрицу этого отношения [P]=. P не рефлексивное, т.к. на главной диагонали матрицы нет единиц; P не симметричное, т.к. (1;2)P, но (2;1)P или [P]≠[P]T; P не антисимметричное,  т.к. (2;3)P, (3;2)P, но 2≠3, или в матрице                не все элементы вне главной диагонали нули; P не транзитивное, т.к., например, (1,2)P, (2,3)P, но (1,3)P.

          Пример 1.2.7 -  Дано отношение P={(x;y)|x-y<1; x,yZ}.

          а) Р рефлексивное, т.к. (x;x)P(x-x=0<1);

          б) Р не симметричное, т.к., например, (2;4)P, (4;2)P;

          в) P антисимметричное, т.к. из (x-y)<1, y-x<1 следует x=y, потому, что если  xy, то при x<yx-y<0, при x>yx-y>0 , т.е. >0→≥1;

          г) P транзитивное, т.к. x-y<1,  y-z<1 →x-z<1, действительно:

                   x-y<1

                 +y-z<1          x-z=1

                   x-z<2          x-z<1,

но x-z=1 противоречит условию x-y<1, остаётся x-z<1.

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

 

           Отношение эквивалентности

          Определение. Отношение P называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно (обозначается ~, E, ≡).

          Примеры отношений эквивалентности:

          а) отношение равенства на любом множестве:

            1)x=x;

            2) x=yy=x;

            3) x=y; y=zx=z;

          б) отношение подобия на множестве треугольников.

          Определение. Пусть Е – отношение эквивалентности на множестве А и хА. Подмножество элементов множества А, эквивалентных x, называется классом эквивалентности элемента х. Обозначается: [x]E, E(x). Таким образом, E(x)={y | yEx}.

          Определение. Множество классов эквивалентности называется фактор -множеством множества А относительно эквивалентности Е, обозначается А/Е: А/Е={E(x)|xA}. Фактор –множество  является подмножеством булеана.

          Пример 1.2.8 - А – множество студентов в институте. Е – отношение принадлежности  к одной группе. [x]E-студенты одной группы. А/Е– множество студенческих групп института.

          Из определений ясно, что

          1) любой элемент класса эквивалентности порождает класс эквивалентности, т.е. b[a] → [a]=[b];

          2) каждый класс эквивалентности содержит хотя бы один элемент, т.е.аА [a]≠Ø;

          3) никакой элемент множества А не может принадлежать двум различным классам: aEb → [a] = [b].

          Теорема. Фактор – множество А/Е является разбиением множества А. Обратно, если А={Ai} какое-то разбиение множества А, то ему соответствует некоторое отношение эквивалентности Е: xEyx,yAi  для некоторого i.

          Таким образом, существует взаимно однозначное соответствие между множеством всех разбиений А и множеством всех отношений эквивалентности на множестве А.

          Пример 1.2.9 -  А={1,2,3,4}. А={{1},{2,3,4}}={A1,A2}- разбиение А.

E={(x;y)|x,yAi,i=1,2}={(1,1),(2,2),(2,3),(2,4),(3,2),(3,3),(3,4),(4,2),(4,3),(4,4)}- отношение эквивалентности, соответствующее данному разбиению.  

          Пример 1.2.10 -  A={1,2,3,4,5,6}, PA2,

 P={(1;1);(2;2);(3;3);(4;4);(5;5);(6;6);(1;2);(1;4);(2;1);(2;4);(3;5);(5;3);(4;1);(4;2)}.

          Покажем, что данное отношение является отношением

 эквивалентности. По его матрице

[P] =

определяем, что P рефлексивно, симметрично, транзитивно (см. выше),  следовательно Р есть отношение эквивалентности на множестве А. Построим классы эквивалентности и фактор – множество:

     [1]P={x|(x;1)P}={1,2,4};

     [2]P={x|(x;2)P}={1,2,4};

     [3]P={x|(x;3)P}={3,5};

     [4]P={x|(x;4)P}={1,2,4};

     [5]P={x|(x;5)P}={3,5};

     [6]P={x|(x;6)P}={6}.

          Таким образом, имеется только три различных класса эквивалентности [1]=[2]=[4]={1,2,4}, [3]=[5]={3,5}, [6]={6}. Фактор – множество A/Р= ={[1],[3],[6]}={{1,2,4},{3,5},{6}} является разбиением множества А, которое  соответствует данному отношению эквивалентности.

          Отношение порядка

          Определение. Отношение Р на множестве А называется отношением порядка если оно антисимметрично и транзитивно. Часто обозначается символом  .

          Если к тому же оно:

          1) рефлексивно, то называется частичным или нестрогим порядком (≤);

          2) антирефлексивно, то называется отношением строгого порядка (<).

          Определение. Пусть на множестве А задано отношение порядка, если для любых двух элементов a и b этого множества имеет место ab или ba, то элементы называются сравнимыми, в противном случае несравнимыми.

          Определение. Частичный порядок на множестве А называется  линейным или цепью, если любые два элемента этого множества сравнимы.

          Множество А, на котором определен частичный (линейный) порядок , называется частично упорядоченным множеством (ч.у.м) ( линейно упорядоченным множеством (л.у.м)). Обозначается (А, ).

          Пример 1.2.11 - A={a,b,c}. P={(a,a),(a,b),(b,b),(c,c)} – отношение частичного порядка (т.е. рефлексивно, антисимметрично, транзитивно), что легко проверить по его матрице [P]=. Р не является линейным порядком, т.к. a и c, b и c не сравнимы.

          Примерами линейно упорядоченных множеств являются множества N, Z, Q, R, где определён  естественный порядок.

          Определение. Элемент a упорядоченного множества А называется наибольшим (наименьшим), если в А нет таких x, что x<a (x>a). Л.у.м. называется вполне упорядоченным множеством (в.у.м), если любое его непустое подмножество имеет наименьший элемент.

          Пример 1.2.12 - (N; ≤) – в.у.м. ([0;1]; ≤) – не является в.у.м., т.к., например, (0;1] [0;1], но (0;1]  не содержит  наименьшего элемента.

          Определение. Рассмотрим ч.у.м. (Х,≤). Говорят, что элемент у покрывает элемент х , если х≤у и не существует такого элемента z, что х<z<y.

В случае конечного множества Х, ч.у.м. (Х,≤) можно представить в виде схемы, в которой каждый элемент изображается точкой на плоскости. Если у покрывает х, то точки х и у соединяют отрезком, причём точку, соответствующую х, располагают ниже точки у. Такие схемы называют диаграммами Хассе.

           Пример 1.2.13 - . Рассмотрим ч.у.м. (Р(А), ) = , где  Р(А) булеан А. Диаграмма Хассе для ( Р(А), ) на рисунке 1.2.4.

                                                   

                              Рисунок 1.2.4                                   Рисунок 1.2.5

 

          Пример 1.2.14 - Для л.у.м.  с обычным отношением порядка на множестве натуральных чисел, не превосходящих четырёх, диаграмма Хассе изображена на рисунке 1.2.5.

    

      Лексикографический порядок

          Лексикографический порядок лежит в основе упорядочения слов в различных словарях. Рассмотрим непустое множество символов Х={x,y,…}, называемое алфавитом. Словами будем называть конечные наборы написанных друг за другом элементов Х. Элемент xi  слова x1,x2,…,xn  назовём его i-ой координатой, а число n - его длиной.

          Определение. Пусть W(X) – множество слов алфавита Х, пусть ≤ - отношение порядка на множестве Х, т.е.  (Х,≤) – упорядоченное множество.

Отношение лексикографического порядка (обозначается  или L) на W(X) задаётся по правилу: x1,х2,…,xm L y1,y2,…,yn , если выполнено одно из условий: а) x1< y1; б) xi=yi i:1≤im, m<n; в) xi=yi i:1≤ik, xk+1< yk+1.

    

     Функциональные отношения (функции)

          Определение. Бинарное отношение fА×В называется функциональным или функцией из множества А в множество В, если:

          а) (x,y1)f, (x,y2)f → y1=y2  или xA! yB, (x,y) f;

          б) Df=A, EfB, где Df - область определения функции, Ef  - область значений.

           В этом случае функцию иногда называют тотальной  или всюду

определённой; если DfA, то f называют  частичной функцией или частично определённой. В математике, как правило, рассматривают тотальные функции и называют их просто функциями.

          Пример1.2.15 ,  - функция, т.к. ,

; – не функция, т.к. содержит пары  и  с одинаковыми первыми и разными вторыми элементами; отношение  - функция, т.к. из того, что  следует   ;  – не функция, т.к. содержит пары с одинаковыми первыми и разными вторыми элементами, например, , ;

  - частичная функция, т.к. , .

         Если задана функция  f = {(x,y)|xA, yB}, то x- аргумент, y- значение функции. Различные обозначения функции: y=f(x), f: AB, f: xyA   f      B

x  f   у. Говорят также, что f ставит в соответствие элементу х элемент у.

          Пусть  f = {(x,y)| xA, yB} – функция. Она называется:

          а) инъективной (инъекцией, разнозначной), если (x1,y) f и (x2,y) fx1=x2 (или  x1x2f(x1) ≠ f(x2)), при этом - частичная функция;   

          б) сюръективной (сюръекцией, отображением А на В),

если yBxA, что (x;y)f, т.е. Ef = B;         

          в) биективной (биекцией, взаимно-однозначным соответствием), если  является и инъективной и сюръективной (для тотальной функции).  Обозначается  АВ.

          Заметим, что если функция частичная, то, в случае её инъективности и сюръективности, она не всегда биективна, например,  () - частичная функция, т.к. , . Она инъективна, т.к. для любых  из области определения выполняется ; она сюръективна, т.к. , но биекции нет, т.к. существуют  ( например, ),   которым не соответствует ни один .

          Если биекция f: АА, то она называется подстановкой множества А. Простейший пример подстановки есть тождественное отношение I.

          Пример 1.2.16 - Рассмотрим три функции : .

          1)  - инъективна, т.к. для любых  выполняется ; но не сюръективна, т.к.  ( см. рисунок 1.2.7);

          2)  -  сюръективна, т.к., но не инъективна, поскольку существуют , но  (см. рисунок 1.2.8);

           3)  - биективна, каждому  соответствует один  и, наоборот, (график – прямая линия).

                                 

                    Рисунок 1.2.7                                         Рисунок 1.2.8

 

          Заметим, что свойства этих, а также других функций проще всего определять по их графикам.

          Пример 1.2.17 - Рассмотрим функции : , графики которых изображены на рисунке 1.2.9:

 

 


Рисунок 1.2.9

 

По графикам можно установить, что а) - сюръекция (не инъекция);

б)  - инъекция (не сюръекция); в)  - биекция; г)  - не инъективная и не сюръективная функция.

 

                 1.3 Понятие о мощности множеств

 

          Часто возникает необходимость сравнивать множества по числу элементов. В этом случае возникает понятие мощности множества.

Определение. Множества А и В называются эквивалентными (обозначается А~В) если существует биекция f: АВ (т.е. между ними можно установить взаимно однозначное соответствие (в.о.с.)).

          Очевидно, что два конечных множества эквивалентны тогда и только тогда, когда они имеют одинаковое число элементов. Если два множества бесконечны и между ними можно установить в.о.с., то они обладают также чем-то общим, что мы будем называть мощностью. Итак, любые два эквивалентных множества (конечные или бесконечные) имеют одинаковую мощность или являются равномощными. Или более точное определение.

          Определение. Мощностью множества А называется класс всех множеств, эквивалентных множеству А (мощность обозначается ).

          Имеется три возможности:

          а) если А - конечное множество, имеет n элементов, то = n;

          б) если А - бесконечное множество и эквивалентно множеству натуральных чисел N, то А называют счётным множеством, записывают = . Таким образом, у счётного множества все элементы можно пронумеровать;

          в) существуют бесконечные множества, которые нельзя привести во в.о.с. с множеством натуральных чисел. Например, установлено, что множество всех действительных чисел отрезка [0,1] не является счётным (теорема Кантора). Принято мощность этого множества называть континуум (часто обозначается с), а множества такой мощности континуальными.

          Доказано, что если А континуальное множество, то , т.е. мощность континуума равна мощности множества всех подмножеств счётного множества. Вообще, для любого множества А: Р(А)=,  где Р(А) – булеан.

          Примеры счётных множеств:

          а) множество целых чисел Z, а также ;

          б) множество рациональных чисел Q;

          в) любое бесконечное подмножество множества N,  например, {2,4,6,8,…};

          г) ( вообще ).

          Примеры континуальных множеств:

          а) множество всех действительных чисел R или множество точек числовой оси;

          б) множество всех точек плоскости (пространства) ;

          в) множество всех подмножеств счётного множества ( т.е. булеан счётного множества).

          Как показано в теории множеств, для множества любой мощности множество его подмножеств имеет более высокую мощность. Поэтому не существует множества максимальной мощности. На мощность множеств можно смотреть как на новый объект, называемый кардинальным числом или кардиналом. Примерами кардиналов могут быть:

          а) любое натуральное число (как мощность конечного множества);

          б) и т.д.

          Отметим, что существование биекции между двумя множествами позволяет перенести изучение свойств с одного множества на другое, что многое упрощает, например, некоторые свойства конечного множества А, = n можно изучать по множеству {0,1,2,3,…n-1}.

 

         

          2 Элементы математической логики

 

          2.1 Высказывания и логические операции

 

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

          Определение. Высказыванием называется повествовательное предложение, о котором в данной ситуации можно говорить, что оно истинно или ложно.      

               Пример 2.1.1 Высказывание: «дважды два – четыре» - истинно; высказывание:  «тенге – российская валюта» - ложно.     

               Определение. Простое (элементарное) высказывание рассматривается как некое неделимое целое. Обозначается  А, В, С,...,Р,…; сложным (составным) называется высказывание, составленное из простых с помощью логических связок (операций).

          Основными логическими операциями (связками) являются:

          а) конъюкция (операция «и», логическое произведение).

Конъюнкцией двух высказываний P и Q (обозначается , читается “Р  и Q”) называется высказывание, истинное тогда и только тогда, когда истинны оба высказывания и ложное во всех остальных случаях;

          б) дизъюнкция (операция «или», логическая сумма). Дизъюнкцией двух высказываний P и Q (обозначается , читается “Р  или Q”) называется высказывание, ложное, если оба  высказывания ложные и истинное во всех остальных случаях;

          в) отрицание (инверсия). Отрицанием высказывания P (обозначается , читается “не Р”) называется высказывание, истинное, когда P ложное и ложное, когда P  истинное;

          г) импликация (логическое следование). Импликацией двух высказываний P и Q (обозначается , , читается, “если  Р, то Q”, “Р влечёт Q”) называется высказывание, ложное, когда Р истинное, а Q ложное и истинное во всех остальных случаях;

д) эквиваленция (эквивалентность). Эквиваленцией двух высказываний

P и Q (обозначается , читается “Р  эквиваентно Q”, “Р тогда и только тогда, когда Q”) называется высказывание, истинное, когда P и Q - оба истинны  или оба ложны и ложное во всех остальных случаях.

 

          Формулы алгебры логики

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

          Поставим в соответствие высказыванию P логическую переменную х, которая принимает значение 1, если Р истинно, 0, если Р ложно. Из логических переменных можно с помощью логических операций составлять различные конструкции, которые являются формулами алгебры логики.

          Определение формулы:

          а) любая логическая переменная является формулой;

          б) если  и  формулы, то выражения ,   являются формулами;

          в) никаких других формул, кроме построенных в а) и б) нет.

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

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

                                   

Т а б л и ц а 2.1.1                             

0

0

0

0

1

1

1

0

1

0

1

1

0

 

1

0

0

1

0

0

0

1

1

1

1

1

1

 

         

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

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

          Пример 2.1.2 - Для формулы = таблица истинности имеет вид:                 

 

 

 

 

 

                                      Т а б л и ц а 2.1.2

0

0

0

1

1

1

1

0

0

1

1

1

1

1

0

1

0

1

0

1

1

0

1

1

1

0

1

1

1

0

0

0

1

1

1

1

0

1

0

1

1

1

1

1

0

0

0

0

1

1

1

1

0

0

0

0

 

Введём новые важные логические операции, добавляя к пяти основным ещё три операции (тем самым расширим понятие логической формулы):

е) штрих Шеффера (антиконъюнкция). Обозначается .

По определению , или ;

ж) стрелка Пирса (антидизъюнкция). Обозначается .

По определению  или ;

и) кольцевая сумма (логическое сложение, сложение по модулю два).

Обозначается . Определяется  или .

          Составим таблицы истинности этих операций, исходя из определений.

                                      

                                       Т а б л и ц а 2.1.3

0

0

1

1

0

0

1

1

0

1

1

0

1

0

1

1

1

0

0

0

         

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

          а) внешние скобки не пишутся, например, вместо , будем писать ;

          б) на множестве  вводится транзитивное отношение

«>» - быть более сильным и отношение «~» - быть равносильным, по правилам, указанным на схеме:

Рисунок 2.1.1

 

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

          Пример 2.1.3

          а) в формуле  скобки расставляются так: ;

          б) в формуле  скобки расставляются так: ;

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

 

          2.2 Функции алгебры логики

 

          Каждая формула представляет логическую функцию от логических переменных, которые могут принимать только два значения 0 и 1.     

Определение. Функцией алгебры логики (логической функцией) от n переменных  (обозначается) называется любая функция, которая произвольному набору  нулей и единиц ставит в соответствие значение , т.е. .

          Функции алгебры логики называются также булевыми, двоичными или переключательными (обозначаются в некоторых учебниках ).

Эти функции описывают преобразование некоторым устройством входных сигналов в выходные. Пусть устройство имеет n входов , на которые может подаваться или не подаваться ток, и один выход, на который ток подаётся или не подаётся, в зависимости от подачи тока на входы (см. рисунок 2.2.1).                                                            

 

 

 

 


                     Рисунок 2.2.1                                          Рисунок 2.2.2

 

          Значение  понимается как поступление тока на i-ый вход;  - как не поступление. Значение  (где ), если ток на выходе проходит и  - если не проходит.

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

 

          Способы задания логических функций

          Наиболее распространённые способы задания функций следующие:

     а) задание таблицей истинности, в левой части которой выписаны все возможные наборы значений аргументов , а в правой – столбец значений , соответствующих этим наборам. Число всех наборов 0 и 1 функции n переменных будет равно , т.е. для функции одной переменной -  , двух - , трёх -  и т.д. Таким образом, таблица истинности функции одной переменной содержит 2 строки, двух – 4, трёх – 8 и т.д. При этом множество значений аргументов принято упорядочивать по лексикографическому порядку, который легко запомнить, например, используя понятие дерева из теории графов. На каждом этаже этого дерева расположены всевозможные наборы 0 и 1 длины n: на первом – n=1, на втором  – n=2, на третьем - n=3 и т.д. (см. рисунок 2.2.3);

 

Рисунок 2.2.3

 

     б) задание функций перечислением всех наборов, на которых  принимает значение 0 (нулевые наборы) и всех наборов, на которых она принимает значение 1 (единичные наборы);

     в) задание функции формулой;

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

     Рассмотрим на примере эти способы задания функции.

          Пример 2.2.1 - Имеется устройство, фиксирующее принятие некоторой резолюции тремя персонами (комитетом трёх). Каждый член комитета при одобрении резолюции нажимает свою кнопку. Если большинство членов согласны, то резолюция принята, что фиксирует устройство. Таким образом, устройство реализует функцию , таблица истинности которой имеет вид:                             

                                        Т а б л и ц а 2.2.1

x

y

z

0

0

0

0

0

0

1

0

0

1

0

0

0

1

1

1

1

0

0

0

1

0

1

1

1

1

0

1

1

1

1

1

 

Зададим эту функцию нулевыми и единичными наборами:  - нулевые наборы;   - единичные наборы. Если задавать эту функцию с помощью вектора значений, то это будет набор (00010111).

Иногда применяют и другие способы задания функций (см., например, [3], стр.124 или [9], стр.124).

Итак, число всех наборов 0 и 1 для функции n переменных равно . Число же всех возможных различных функций  n переменных равно числу всех возможных расстановок 0 и 1 в столбце с  строками, т.е. равно . Значит, если - множество всех значений аргументов функции , а - множество всех функций от , то мощности этих множеств будут . Таким образом,  растёт очень быстро: , ,  и т.д.

Особую роль в алгебре логики играют функции одной и двух переменных. Например, множество всех логических функций одной переменной  состоит из четырёх функций, которые можно представить их таблицей истинности.

 

Т а б л и ц а 2.2.2

0

0

0

1

1

1

0

1

0

1

 

0

1

 

Функции  и  константы 0 и 1, =х – повторяет переменную х, (т.е. значения этих функций не зависят от переменной х, поэтому говорят, что переменная х не существенна или фиктивна для этих функций). Наибольший интерес представляет функция =- унарная операция отрицания. Аналогичным образом можно построить таблицу истинности для всех 16 () функций двух переменных. Среди них 7 логических операций (конъюнкция, дизъюнкция, и т.д.), остальные не представляют интереса. Заметим, что функция может быть представлена как операция, если её значения лежат в области определения этой функции. В этом смысле все функции математической логики могут быть представлены операциями.

Логические функции трёх и более переменных обычно задаются либо таблицей истинности, либо формулой, состоящей из знаков переменных и знаков унарных и бинарных операций. В общем случае формула описывает логическую функцию как суперпозицию других, более простых функций.

Определение. Функцию называют суперпозицией функций   и ,, если =.     =.     

Пример 2.2.2 - Функция  есть суперпозиция   и , .      

 

          Эквивалентность формул. Основные эквивалентные

 соотношения алгебры логики

          Одна и та же функция может быть представлена различными формулами. В этом случае возникает понятие эквивалентности формул.

          Определение. Формулы  и  называются эквивалентными или равносильными (обозначается , ), если они представляют одну и ту же функцию.

          Пример 2.2.3 - Построим таблицы истинности для формул  и .

      Т а б л и ц а 2.2.3

x

y

0

0

1

1

1

1

0

1

0

1

1

1

1

0

1

0

0

0

1

1

0

0

1

1

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

.

 

          В этом примере для установления эквивалентности формул применён метод построения их таблиц истинности и сравнения полученных таблиц по каждому набору значений переменных.

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

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

а) (правило подстановки): если в исходном эквивалентном соотношении

 все вхождения переменной х одновременно заменены формулой , то получим новое эквивалентное соотношение;

б) (правило замены): если какая-либо формула , описывающая функцию

, содержит подформулу , то замена  на  () не изменит функции.

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

Т а б л и ц а 2.2.4

1

Коммутативность

2

Ассоциативность

3

Дистрибутивность

4

Идемпотентность

5

Закон поглощения

6

Закон де Моргана

7

Закон двойного отрицания                 

8

Свойство констант

9

- закон противоречия

- закон исключённого третьего

 

Наряду с основными эквивалентностями, часто используют ещё некоторые, которые можно вывести из основных или доказать с помощью таблиц истинности, сведём их также в таблицу.

         

Т а б л и ц а 2.2.5

10

Закон склеивания

10 а

Закон расщепления

11

Обобщённое склеивание

12

13

14

15

16

                        

         

          Определение. Формула  называется выполнимой (опровержимой), если существует такой набор значений переменных, при котором формула принимает значение 1 (0).  

Пример 2.2.4 -  Формула = является одновременно и выполнимой, и опровержимой, т.к.  и .

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

            Пример 2.2.5 -  Формула   тождественно истинна, т.к. =1 для всех х ; формула   тождественно ложна, т.к. =0 для всех х.

                                    

                                             Т а б л и ц а 2.2.6

 

0

1

1

0

1

0

1

0

          

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

 

           Двойственность

          Определение. Функция называется двойственной к функции , если  ; функция, двойственная к самой себе, называется самодвойственной, т.е. .

         Отношение двойственности симметрично, т.е., если , то .     Пример 2.2.6 - Дизъюнкция двойственна конъюнкции, конъюнкция –

дизъюнкции, константа 1 –  константе 0 и  константа 0 – константе 1, отрицание самодвойственно. Действительно, например, для = имеем ; для , т.е. .

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

Пример 2.2.7 - Для функции  получим двойственную функцию двумя способами:

I способ. , т.е. .

II способ. Построим таблицу истинности для (см. таблицу 2.2.7), затем заменим в ней все значения на противоположные, получим таблицу для  (см. таблицу 2.2.8). По таблицам видно, что эта функция самодвойственна . Заметим, что для получения таблицы функции  в обычном виде, где значения переменных расположены в лексикографическом порядке, нужно все столбцы последней таблицы «перевернуть».

 

Т а б л и ц а 2.2.7                                      Т а б л и ц а 2.2.8

0

0

0

0

0

0

0

0

0

1

0

0

0

0

0

1

0

0

0

0

0

0

1

1

0

0

1

1

1

0

0

0

0

0

0

1

0

1

0

1

0

1

1

1

0

1

0

0

1

1

1

1

1

1

1

1

1

1

1

1

1

1

0

1

1

0

1

1

1

0

0

0

0

1

1

1

0

1

0

0

0

0

1

0

0

0

0

0

 

 

 

 

 

 

 

 

 

 

  

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

    

          Классы Поста. Полные системы логических функций

          Пусть дана булева функция . Введём определение классов булевых функций или классов Поста:

          а) говорят, что функция  сохраняет константу 0, если .

 Множество всех функций, сохраняющих 0, образует класс  ();

б) говорят, что функция  сохраняет константу 1, если .

 Множество всех функций, сохраняющих 1, образует класс  ();

в) обозначим через  множество или класс самодвойственных

функций;

г) функция называется линейной, если она может быть записана в

 виде , где . Класс линейных функций обозначается ;

д) функция называется монотонной, если для любых наборов нулей и

 единиц  и  из условий ,…,  следует . Обозначим через  класс монотонных функций.

          Каждый класс Поста замкнут относительно операций замены переменных и суперпозиции, т.е. с помощью этих операций из функций данного класса можно получить только функции этого же класса.

          В таблице ниже рассмотрены примеры принадлежности некоторых булевых функций к классам Поста (принадлежит – (+); не принадлежит – (-)).

 

          Т а б л и ц а 2.2.9

Функция

Отрицание

-

-

+

-

+

Конъюнкция

+

+

-

+

-

Дизъюнкция

+

+

-

+

-

Импликация

-

+

-

-

-

         

          Одна и та же логическая функция может быть задана формулами,

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

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

          Ответ на вопрос о полноте произвольной системы функций даёт следующая теорема.

          Теорема Поста. Для того чтобы система булевых функций была полной, необходимо и достаточно, чтобы она содержала хотя бы одну функцию, не сохраняющую 0,  хотя бы одну функцию, не сохраняющую 1,  хотя бы одну  не самодвойственную функцию, хотя бы одну нелинейную и хотя бы одну не монотонную функции.

          При определении полноты булевых функций можно пользоваться таблицами принадлежности этих функций классам Поста. Например, так как в системе  отрицание не сохраняет констант и не монотонно, а конъюнкция не линейна и не самодвойственна (см. таблицу 2.2.9) , то эта система полна. Примерами функционально полных систем являются   и другие. Формулы, содержащие, кроме переменных и скобок, только операции конъюнкции, дизъюнкции и отрицания, называются булевыми.

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

          Отсюда следует, что системa  функционально полна. Для доказательства функциональной полноты какого-либо другого набора операций, кроме указанного выше способа,  достаточно показать, что через операции набора можно выразить конъюнкцию, дизъюнкцию и отрицание. Справедливо и более общее утверждение, позволяющее доказать полноту системы другим способом.              

          Теорема. Если все функции функционально полной системы  представимы формулами над , то  также функционально полна.

          Пример 2.2.8 - Рассмотрим системы  и  и базис =. Докажем, что ,  также базисы. Действительно, в каждой из этих систем недостающая до  операция может быть выражена через остальные две: для  не достаёт «»:   

                           для  не достаёт «»:       () .

Формула    в системах ,  перейдёт соответственно в формулы:  =[],  [].

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

 

      2.3 Дизъюнктивные и конъюнктивные нормальные формы

 

          Базис  = наиболее изучен и имеет самое широкое применение на практике.         

          Определение. Элементарной конъюнкцией (дизъюнкцией) называется конъюнкция (дизъюнкция) переменных или их отрицаний.

          Пример 2.3.1

          а)  и элементарные дизъюнкции;

          б)  и элементарные конъюнкции;

          в)одновременно является и элементарной дизъюнкцией и  элементарной конъюнкцией.

          Определение. Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция элементарных конъюнкций. Конъюнктивной нормальной формой (КНФ) называется конъюнкция элементарных дизъюнкций.  

          Пример 2.3.2

          а)ДНФ;

          б) КНФ.

          Теорема. Любая формула может быть приведена к ДНФ (КНФ) (т.е. любая формула эквивалентна некоторой ДНФ (КНФ)).

          Правило приведения формулы к ДНФ:

          а) все логические операции, присутствующие в формуле, выразить через  , используя эквивалентности:

            1);

            2);

            3);

            4);

            5);

          б) перенести все отрицания к переменным по закону де Моргана:

;

          в) используя закон дистрибутивности, преобразовать формулы так, чтобы все конъюнкции выполнялись раньше дизъюнкций: .

          Пример 2.3.3 - Приведём к ДНФ формулу . Для этого

заменим  на , затем применим закон де Моргана и закон двойного отрицания:=.

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

          а)  (закон идемпотентности);

   б)  (закон исключённого третьего),  (закон противоречия); в) ,  - ( свойства констант).

          Поэтому, используя закон идемпотентности, в последнем примере получим ДНФ: .

          Приведение формулы к КНФ производится так же как к ДНФ, только вместо пункта в) применяется пункт в:

          в) используя закон дистрибутивности, преобразовать формулы так, чтобы все дизъюнкции выполнялись раньше конъюнкций, т.е. .

          Пример 2.3.4 - Приведём к КНФ формулу .

 Заменим операцию , используя формулу :

 [закон де Моргана, двойное

отрицание]  - КНФ.

          ДНФ и КНФ имеют тот недостаток, что они не обладают свойством единственности, т.е. одна и та же формула имеет несколько ДНФ и КНФ. Этим недостатком не обладают совершенные нормальные формы.

          Определение. Совершенной дизъюнктивной нормальной формой (СДНФ) называется ДНФ, в которой в каждую элементарную конъюнкцию каждая переменная входит ровно один раз, причём,  входит либо сама переменная, либо её отрицание, и среди элементарных конъюнкций не должно быть одинаковых; совершенной конъюнктивной нормальной формой (СКНФ) называется КНФ, в которой в каждую элементарную дизъюнкцию каждая переменная входит ровно один раз, причём,  входит либо сама переменная, либо её отрицание, и среди элементарных дизъюнкций не должно быть одинаковых.   

          Пример 2.3.5

          а)  - СДНФ;

          б) - СКНФ;

          в)  - не СДНФ, т.к. содержит две одинаковых элементарных конъюнкции;

          г)  - не СДНФ, т.к. в одной элементарной конъюнкции содержится  и переменная и её отрицание: .     

          Теорема. (Существование и единственность СДНФ и СКНФ). Всякая логическая формула единственным образом (с точностью до порядка следования элементарных конъюнкций (дизъюнкций)) может быть представлена в СДНФ (СКНФ). 

          Для приведения формулы к СДНФ можно использовать один из двух методов:

          І метод: приводим формулу к ДНФ; если какая-то элементарная конъюнкция не содержит некоторой переменной у, то добавляем её, используя закон расщепления: ; убираем одинаковые элементарные конъюнкции, используя закон идемпотентности .    

         Пример 2.3.6 - Получим СДНФ функции , заданной в ДНФ:

- СДНФ.

          ІІ метод: для данной формулы строим таблицу истинности, потом применяем правило, основанное на теореме Шеннона: СДНФ функции       содержит столько элементарных конъюнкций, сколько единиц в столбце значений ; каждому единичному набору нулей и единиц  соответствует элементарная конъюнкция всех переменных, в которой  взято с отрицанием, если  и без отрицания, если .

          Пример 2.3.7 - Для функции , заданной в ДНФ, найти СДНФ. Построим таблицу истинности:

                            Т а б л и ц а 2.3.1

0

0

0

1

1

0

1

0

0

0

0

0

1

1

1

0

1

1

0

1

0

1

0

1

0

0

0

0

0

0

0

1

1

1

0

1

0

0

1

1

1

0

0

0

1

0

0

0

1

1

1

0

1

0

1

0

0

0

1

1

1

1

0

0

0

0

0

0

1

1

1

1

1

0

0

1

0

0

1

1

         

          Функция принимает значение 1 при следующих значениях аргументов:   - это её единичные наборы. По выше приведённому правилу,  - СДНФ.

          Приведение формулы к СКНФ аналогично приведению к СДНФ. Также существует два метода:

          а) метод элементарных преобразований;

          б) СКНФ находят по таблице истинности: СКНФ функции  содержит столько элементарных дизъюнкций, сколько нулей в столбце значений ; каждому нулевому набору нулей и единиц  соответствует элементарная дизъюнкция всех переменных, в которой  взято с отрицанием, если  и без отрицания, если .

          Пример 2.3.8 - Рассмотрим функцию из предыдущего примера . Приведём её к СКНФ двумя способами:

          а)

          б) из таблицы истинности выпишем нулевые наборы:, значит, по выше приведённому правилу,  - СКНФ.

 

          Минимизация булевых функций в классе ДНФ. Карты Карно

          При решении практических задач часто возникает проблема минимизации логических формул, в смысле, например, найти формулу, содержащую наименьшее число переменных, или наименьшее число операций, или наименьшее количество подформул определённого вида и т.д. К настоящему времени наиболее изучена задача отыскания дизъюнктивных форм, минимальных по числу вхождений переменных. Под вхождением переменной понимается место, которое переменная занимает в формуле.

          Определение. Минимальной ДНФ (МДНФ) называется ДНФ с наименьшим числом вхождений переменных.     

          Существует много способов отыскания МДНФ (метод Квайна, неопределённых коэффициентов, с помощью гиперкубов и т.д.). Остановимся на наиболее простом – с использованием карт (диаграмм) Карно.     

          Карта Карно – это таблица, каждая клетка (ячейка) которой соответствует некоторой элементарной конъюнкции всех переменных. Для функции n переменных  существует  возможных комбинаций их значений,  состоящих из 0 и 1. То есть, например, для n=2 имеем  элементарные конъюнкции , которым соответствуют следующие наборы 0 и 1: (1,1), (1,0), (0,1), (0,0); для n=3 -  -  - (1,1,1), (1,1,0),…,(0,0,0) и т.д. Карты Карно строятся в виде таблицы размером  так, что её столбцы соответствуют значениям переменных , строки -  (или наоборот); вообще, для одной и той же функции может быть построено несколько карт, важно, чтобы соседние ячейки (как по вертикали, так и по горизонтали) отличались только значением одной переменной.

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

          а) для функции двух переменных х, у - рисунок 2.3.1;

          б)для функции трёх переменных  - рисунок 2.3.2;

          в) для функции четырёх переменных  - рисунок 2.3.3.

                                                                                     

                 Рисунок 2.3.1                Рисунок 2.3.2                    Рисунок 2.3.3

         

          Для определения МДНФ булевой функции, сначала надо найти её СДНФ, затем каждую элементарную конъюнкцию СДНФ отметить единицей  в соответствующей ячейке карты Карно.

          Пример 2.3.9 - Функции   и  заданы в форме СДНФ. Карта Карно для  на рисунке 2.3.4; для  - на рисунке 2.3.5.                                                                            

                                                                          

                         Рисунок 2.3.4                       Рисунок 2.3.5

Заметим, что, если в картах Карно две, четыре, восемь (для функции четырёх переменных) соседних ячеек по вертикали или по горизонтали содержат 1, то эти ячейки объединяют в блоки (на картах их отмечают овалами) и соответствующие этим блокам дизъюнкции элементарных конъюнкций можно упростить. Так, в примере 2.3.9 для функции  имеем блок из двух ячеек, на рисунке он отмечен овалом. Этому блоку соответствует дизъюнкция , упрощая которую, получим: . Таким образом, блоку из двух ячеек функции двух переменных отвечает одна переменная х, а именно та переменная, которая полностью «покрывает» этот блок. Формула упростилась .

          Для функции  также имеем один блок из двух ячеек, ему соответствует дизъюнкция элементарных конъюнкций , упрощая которую получим   , т.е. блоку из двух ячеек функции трёх переменных соответствует конъюнкция двух переменных, «покрывающих» этот блок. Формула упростилась .

          Рассмотрим ещё несколько примеров.

Пример 2.3.10 -  - СДНФ функции. Её карта Карно на рисунке 2.3.6. Так как z находится на обоих концах карты, то её (карту) можно «скрутить» и считать, что 1 в углах карты образуют блок из четырёх ячеек. Эти четыре ячейки полностью «покрывает» переменная z, т.о., МДНФ функции будет .

 

          Рисунок 2.3.6               Рисунок 2.3.7                      Рисунок 2.3.8

       

        Пример 2.3.11 -  - СДНФ функции. Её карта Карно на рисунке 2.3.7. На карте есть блок из четырёх ячеек, который покрывают переменные  и , поэтому МДНФ функции будет: .

          Пример 2.3.12 - Карта Карно для функции

 заданной в СДНФ на рисунке 2.3.8.

          На карте имеем: блок из 8 ячеек покрывает переменная y; двум блокам из 4 ячеек соответствуют элементарные конъюнкции  и , поэтому МДНФ будет: .

    

2.4 Булева алгебра и теория множеств. Коммутационные схемы

          

Можно легко заметить аналогию между свойствами операций над множествами и свойствами логических операций. Это не случайно.

         Множество  вместе с заданными на нём операциями  называется алгеброй и обозначается .

         Определение. Всякая алгебра, содержащая две бинарные и одну унарную операции, которые удовлетворяют соотношениям 1) - 9) (см. основные эквивалентные соотношения булевой алгебры, или основные свойства операций над множествами) называется булевой.

         Таким образом, булевыми алгебрами будут:

а)  - булева алгебра всех логических функций с операциями конъюнкции,  дизъюнкции, отрицания;

б)  - булева алгебра логических функций m переменных – это подалгебра алгебры , т.к. ;

в) (P - булева алгебра множеств над  - универсумом, с операциями пересечения, объединения, дополнения;

     г)   - булева алгебра двоичных векторов длины n с покомпонентными логическими операциями над двоичными векторами, определёнными следующим образом:

  имеет место:

  1) , где  если ; в любом другом случае .

  2) , где  если ; в любом другом случае .

  3) , где   если ,  если  .

Если мощности множеств P   и  равны (P ), то между ними можно установить взаимно однозначное соответствие, а соответствующие булевы алгебры будут изоморфны.

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

 

Коммутационные схемы

         Возможность применения математической логики к техническим вопросам была обнаружена в 30-х годах ХХ века. Была замечена, например, связь между электрическими цепями и логическими функциями. Это открытие дало толчок к развитию ЭВМ. Рассмотрим  упрощённо эту связь.

Основным элементом релейно-контактных устройств является электромеханическое реле (переключатель р). Реле может размыкать и замыкать цепь. Присвоим  р значение 1, когда цепь замкнута (ток проходит), и значение 0, когда цепь разомкнута (ток не проходит).

Рассмотрим электрическую цепь на рисунке 2.4.1. При таком расположении контактов p и q лампочка будет гореть (т.е. схема имеет значение 1), если оба переключателя p и q замкнуты (т.е. имеют значения 1). Таким образом, эта схема соответствует логической формуле , а такое расположение переключателей называется логическим элементом «p и q» или схемой логического умножения, его часто обозначают на схеме как на рисунке 2.4.2.

                            

       

       

                                                            

                                             

                         Рисунок 2.4.1                            Рисунок 2.4.2                                          

         

          Рассмотрим теперь схему на рисунке 2.4.3. В этой цепи лампочка будет гореть, и значение схемы равно 1, если хотя бы один из двух контактов p или q, или оба, будут замкнуты, т.е. или , или , или оба . Таким образом, эта схема соответствует логической формуле , а такое расположение переключателей называется логическим элементом «p или q» или схемой логического сложения. Этот элемент можно изображать на схемах, как на рисунке 2.4.4.                                                                                                                                                      

                                         

 

 


                                                 

                            

         

    

      Рисунок 2.4.3                  Рисунок 2.4.4             Рисунок 2.4.5

 

Если имеем схему с одним переключателем p, который обладает свойством, что лампочка загорается тогда и только тогда, когда p разомкнут (т.е. схема имеет значение 1, когда р=0, и значение 0, когда р=1), то эта схема

 соответствует . Такой логический элемент называется «не р» или инвертором, его часто изображают на схемах, как на рисунке 2.4.5.    

          Рассмотрим примеры схем, реализующих простейшие логические формулы.

          Пример 2.4.1 - Схема на рисунке 2.4.6 реализует формулу (переключательную функцию, или функцию проводимости) ; схема для формулы  изображена на рисунке 2.4.7; схема на рисунке 2.4.8 - для формулы .

 

 

 

 

 

 

 

 


Рисунок 2.4.6                   Рисунок 2.4.7                    Рисунок 2.4.8

         

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

         Пример 2.4.2 - Упростим схему на рисунке 2.4.9.  

                                          

                                 Рисунок 2.4.9                       Рисунок 2.4.10

         

          Решение: составим переключательную функцию  . Упростим эту функцию, используя эквивалентные преобразования:

.

Последней формуле соответствует упрощённая схема на рисунке 2.4.10.

 

 

            3 Элементы теории графов

 

3.1 Основные понятия и определения

         

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

          Графы описывают связи между объектами, а связи могут быть «направленными» (например, в генеалогическом дереве) или «ненаправленными» (например, сеть дорог с двусторонним движением). Поэтому в теории графов выделяют два основных типа графов: ориентированные (орграф) и неориентированные (неорграф, н-граф). Иногда рассматривают графы смешанного типа.

         Определение. Графом G называется совокупность двух множеств: V – вершин и E – рёбер ( для н-графа) или дуг ( для орграфа). Обозначается G=G(V,E) или G=(V,E).

 Пусть  - множество вершин. Тогда для н-графа , где ребра  - двухэлементные подмножества множества V; для орграфа , где дуги  - упорядоченные пары, т.е. .

Если  - ребро ( - дуга), то вершины  и  называются концами ребра (- началом, - концом дуги); вершины  и  называются инцидентными ребру (дуге) , а ребро (дуга)  инцидентным (ой)  вершинам  и ; вершины  и  называются смежными, если они являются концами одного ребра (дуги).

          Ребро (дуга), концевые вершины которого совпадают, называется петлёй. Рёбра (дуги) инцидентные одной и той же паре вершин, называются параллельными или кратными. Граф, содержащий кратные рёбра (дуги), называется мультиграфом. Граф называется конечным, если множетва V и E конечны, пустым – если множество его вершин V (а значит и рёбер) пусто. Некоторые вершины могут не войти в список пар множества E, они называются изолированными. Граф, у которого все вершины изолированные, называется нуль-графом; антиподом нуль-графа является полный граф: его рёбрами являются все возможные пары его вершин (у него нет петель и кратных рёбер).

         Заметим, что многие теоремы и определения в теории графов могут быть отнесены как к н-графам, так и к орграфам. Часто, когда совершенно ясно, о каком типе графов идёт речь, рёбра, как и дуги, обозначают круглыми скобками, т.е. вместо  записывают . Каждому н-графу канонически соответствует орграф с тем же множеством вершин, в котором каждое ребро заменено двумя дугами, инцидентными тем же вершинам и имеющими противоположные направления.

         Определение. Степенью (иногда валентностью) вершины  (обозначается  или d()) называется количество всех инцидентных ей рёбер.

          Если m – число рёбер н-графа G, то =2m. Предполагается, что петля даёт вклад 2 в степень вершины. Для вершин орграфа определяются также две локальные степени. 

            Определение. Степенью выхода вершины  (обозначается ,) называется число дуг с началом в вершине ; степенью входа вершины  (обозначается ,) - число дуг с концом в вершине ;=+. Если m – число дуг орграфа G, то==m, причём петля даёт вклад 1 в обе степени.

 

        

 

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

          1. Задание графа парой  множеств V и E , когда каждое  ребро (дуга) , определено парой инцидентных ему вершин.   

         Пример 3.1.1 -  G=G(V,E) - граф , где V={a,b,c}:

       а)  E={{a,b},{b,c}} -  для н-графа;

       б)  E={(a,b),(b,c)} - для орграфа.

        2. Задание графа рисунком. Вершины обозначаются точками, рёбра – линиями, соединяющими точки; дуги – стрелками. При этом один и тот же граф может быть задан разными рисунками. Например, граф G=G(V,E)  из примера 3.1.1, где  V={a,b,c}, E={{a,b},{b,c}} можно изобразить так:

                     

                                   

                                              Рисунок 3.1.1

      

       3. Задание графа матрицей инцидентности. Пусть все вершины и рёбра (дуги) графа G=(V,E) пронумерованы: V={v1,v2,v3,…vn}, E={e1,e2,e3,…em}. Матрицей инцидентности графа G называется матрица А=(аij) размера , n – число вершин, m – число рёбер (дуг):

          а) для н-графа: aij=

б) для орграфа: aij=

 

Пример 3.1.2 - V={v1,v2,v3, v4} – множество вершин, E={e1,e2,e3, e4, e5} – множество рёбер, A=  - матрица инцидентности графа на рисунке 3.1.2; V={а123} – множество вершин, E={1,2,3,4,5,6} – множество дуг,  

A= - матрица инцидентности графа на рисунке 3.1.3.

 

 

 

 

 

 


                             Рисунок 3.1.2                               Рисунок 3.1.3

 

4. Задание графа матрицей смежности. Матрицей смежности В=(bij) графа G=(V,E) называется квадратная матрица размера nn (n – число вершин), элементы которой определены следующим образом:

          а)   для н-графа b ij=

          б) для орграфа b ij=

         в) для мультиграфа

bij=               

          Пример 3.1.3 - Матрица B=  является матрицей смежности н-графа, изображённого на рисунке 3.1.4; матрица B= - матрица смежности для орграфа на рисунке 3.1.5; B= - матрица смежности для мультиграфа на рисунке 3.1.6.

 

 


                                                

 

     

                 Рисунок 3.1.4               Рисунок 3.1.5               Рисунок 3.1.6    

         

          Заметим, что для н-графа матрица смежности симметрическая, т.е. Вт, причём, если у графа нет петель, то в матрице смежности по главной диагонали стоят нули; для орграфа количество единиц в i-ой строке равно степени выхода ρ1(vі) i-ой вершины; количество единиц в j-ом столбце равно ρ2(vj) – степени входа j-ой вершины.

         По матрице смежности легко определить число вершин n – это размер матрицы; число рёбер - m=.

         5. Задание графа списком рёбер (дуг). Кроме матрицы инцидентности, отношение инцидентности можно определить списком рёбер (дуг), задавая его в виде двух столбцов, в первом перечислены все рёбра (дуги), во втором -  инцидентные им вершины. Для орграфа, если число дуг достаточно мало по сравнению с числом вершин, список дуг можно оформить по-другому: задать два набора  и , где - i-ая дуга графа.

          Пример 3.1.4-Для графа на рисунке 3.1.6 список рёбер задан таблицей 3.1.1.

      Т а б л и ц а 3.1.1   

Дуги

Вершины

a

b

c

d

e

f

g

1   2

1   2

1   3

2   3

2   4

3   4

4   4

          Список дуг орграфа на рисунке 3.1.5 может быть представлен наборами   и  .

Существуют и другие способы задания графов (см., например, [3],стр.244), мы ограничимся этими.

 

 

 

 

 

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

         Один и тот же граф, как указывалось выше, можно изображать по -  разному. Например, на рисунке 3.1.7 изображён один и тот же граф.

                           

 


                                                   

 

 

 

                                                          Рисунок 3.1.7

         

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

          Определение. Два графа G1=(V1,E1) и G2=(V2,E2) изоморфны (обозначается G1~G2), если существует биекция φ: , сохраняющая смежность: e1=(u,v) e2=(φ(u),φ(v)).     

          Теорема. Изоморфизм графов есть отношение эквивалентности.

          Действительно, изоморфизм обладает всеми свойствами отношения эквивалентности:

          а) рефлексивностью (G~G);

          б) симметричностью (G1~ G2 G2~G1);

          в) транзитивностью (G1~G2, G2~G3 G1~G3).

          Графы рассматриваются с точностью до изоморфизма. Для того чтобы

граф G1  был изоморфен графу G2 , необходимо и достаточно существование какого-либо взаимно однозначного соответствия между вершинами графов, а

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

 можно убедиться по их графическому представлению.

          Рассмотрим более общее правило установления изоморфизма графов:

          а) подсчитываем число вершин графов (если оно разное, то графы не изоморфны);

          б) выписываем все вершины обоих графов с их степенями (для н-графов) или с парой степеней выхода и входа (для орграфа);

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

                                                                                  г) проверяем сохранение смежности соответствующих вершин. Практически удобно вершины одного графа располагать над вершинами

другого, а соответствующие вершины соединять линией.

         

          Подграфы и части графов. Операции над графами

          Определение. Граф G1=(V1,E1) называется частью графа G=(V,E), если   и  E1E; подграфом графа G=(V,E) называется его часть G1=(V1,E1), которой принадлежат все рёбра (дуги) с концами в V1. На рисунке 3.1.8 изображены граф G, его подграф G1  и его часть G2 .

       

         

        

         

 

Рисунок 3.1.8

           

          1. Пусть дан граф G(V,E).

          а) граф (V, ) называется дополнением графа G, если для любых u,vV, ребро  {u,v} графа  существует тогда и только тогда, когда это ребро в  G отсутствует;

          б) операции добавления к графу G вершины v или ребра {u,v} состоит в образовании графов (V{v}, E) или (V{u,v}, E{{u,v}});

          в) операции удаления вершины v из G состоит в удалении вершины вместе с инцидентными ей рёбрами, т.е. образования графа (V\{v}, E\);

          г) в результате операции удаления ребра {u,v} получается граф (V, E\{{u,v}});

          д) операция отождествления вершин u и v состоит в удалении из графа этих вершин и добавлении новой вершины , при этом рёбра, имеющие концами удалённые вершины, заменяются рёбрами, в которых эти концы заменены новой вершиной. В случае, когда u и v соединены ребром, операцию отождествления вершин u и v называют стягиванием ребра {u,v}.

          2. Пусть даны два графа G1(V1,E1) и G2(V2,E2):

          а) объединением графов G1 и G2  (обозначается G1G2) называется граф G = G1 G2=( V1V2, E1E2);

          б) пересечением графов G1 и G2  (обозначается G1G2) называется граф G = G1 G2=( V1V2, E1E2);

          в) соединением графов G1 и G2 (обозначается G1+ G2) называется граф

G1+ G2 =( V1V2, E1E2 {{u,v}u V1, vV2,  u ≠v}).

          Кроме этих операций, для графов можно определить также и другие операции: кольцевая сумма, прямое произведение и т.д.

          Пример 3.1.5 - На рисунке 3.1.9 изображены графы, представляющие результаты операций над графами G1 , G2  и  G1G. Графы и получены из графа G1Gсоответсвенно стягиванием ребра  и отождествлением вершин и

                                                              

 

 

 

 

 


            G1+ G2                            G1G2                          G1G2                                             

                                         Рисунок 3.1.9

         

          Рассмотрим ещё несколько важных видов графов:

   а) полный граф с n вершинами  обозначается Кn (н-граф без петель и кратных рёбер называется полным, если любые его две вершины соединены ребром). На рисунке 3.1.10 изображены полные графы.

 

                         

             

         К2                         К3                                  К4                                    К5

                                               Рисунок 3.1.10

 

          Число рёбер полного графа вычисляется по формуле:

                                             m(Kn)==;

          б) n –мерные кубы ( n-кубы), обозначаются Qn. Вершинами Qn являются всевозможные  n-ки, состоящие из 0 и 1. Так как всего таких наборов , то вершин у Qn будет . Рёбра задаются по следующему правилу: вершины смежны тогда и только тогда, когда соответствующие n-ки отличаются ровно одной координатой. На рисунке 3.1.11 изображены кубы , Q2  и  Q3.

 

 

 

 

 

 

 

 

 

 

 


                                                   Рисунок 3.1.11

         

          в) граф G(V,E) называется двудольным, если существует такое разбиение множества V его вершин на два подмножества  и  (доли), что концы каждого ребра принадлежат разным подмножествам. Полный двудольный граф обозначают , где m – число вершин в , а n – число вершин в  и для каждого ,  имеем  . На рисунке 3.1.12 изображены полные двудольные графы и .

                

                                                       Рисунок 3.1.12

         

          Пример 3.1.6 - Рассмотрим различные графы, иллюстрирующие выше приведённые определения и понятия (см. рисунок 3.1.13):

 

 

 

 


                                         

                                                    

                                                                                                          

                                                                                 

                                                                                  

 

                                                     Рисунок 3.1.13

         

          а) G1- G7 - н-графы, G8- G12   - орграфы;

          б) G1 и G- полные графы, причём G1= G2;

          в) G7 – не является полным, т.к. имеет одну петлю;

         г) G3  нуль-граф,т.к. все его вершины изолированные;

         д) G4 и G5  являются дополнением друг к другу: G4=  и   G5=;

         е) G6 – мультиграф, т.к. содержит кратные рёбра a и b,  e и f ;

         ж) G8 – орграф, канонически соответствующий н-графу G5;

         и) G9  и G10  не являются равными, т.к. имеют отличающиеся дуги: в G-  (4,1),  в G10 - (1,4);

         к) G11 – ориентированный мультиграф, дуги а и  b кратные;

         л) G12 – не является мультиграфом, т.к. дуги а и b различно

ориентированы.

          Пример 3.1.7 - Найти степени вершин графов G1 и G2   , изображённых на рисунке 3.1.14.                                      

                                

 

 

 

 

                                                     

                                                       Рисунок 3.1.14

         

          Решение: оба графа имеют по четыре вершины, т.е. V={1,2,3,4} – множество вершин и G1 и G2 .      

          а) степени вершин н-графа G1 :ρ(1)=3,   ρ(2)=4,   ρ(3)=3,   ρ(4)=4.

Итак,  =14 =2m,   m=7– число рёбер;

          б) степени вершин орграфа G2 : степени выхода ρ1(1)=2,   ρ1(2)=3,   ρ1(3)=1,   ρ1(4)=1; степени входа ρ2(1)=1,   ρ2(2)=1,   ρ2 (3)=2,   ρ2(4)=3. Таким образом, .

 

          3.2 Маршруты, достижимость, связность

         

          Введём ещё несколько новых понятий для н-графа и орграфа

одновременно. Пусть G(V,E) граф. Последовательность v1,e1, v2,e2, ….., en,vn+1, где  v 1, v2, ..., vn+1 V,  e1,e2, …, en  E, называется маршрутом, соединящим вершины v1 и  vn+1. Маршрут можно задать также последовательностью его вершин v1 , v2, ...vn+1  или последовательностью его рёбер e1, e2, ...,en . Вершина v1- начало маршрута,  vn+1 – конец.

    Цепь (путь) – маршрут, в котором все рёбра (дуги) различны.

    Цикл (контур) – замкнутая цепь (путь), т.е. v1=vn+1.

    Простая цепь (путь), простой цикл (контур) -  цепь (путь), цикл (контур) не пересекающие себя, т.е. не содержащие повторяющихся вершин, кроме, может быть, первой и последней.

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

    Число рёбер (дуг) маршрута называется его длиной. Если существует цепь (путь) длины n, соединяющая вершины u и v, то будем писать uv.

    Вершина v достижима из вершины u, если существует цепь (путь) с началом в u и концом в v.

Определение. Н-граф называется связным, если любые его две несовпадающие вершины соединены маршрутом; орграф называется связным, если соответствующий ему н-граф является связным; орграф называется сильно связным, если любые его две вершины u и v взаимно достижимы, т.е. u достижима из v и  v достижима из u.

    Определение. Подграф G1 графа G называется компонентой связности (сильной компонентой связности) графа G (или связной (сильно связной) компонентой), если:

          1) G1 – непустой связный (сильно связный) граф;

          2) если G2 – связный (сильно связный) подграф графа G  и G1 G2 , то G1 = G2 , т.е. G1 – максимальный связный (сильно связный) подграф графа G.       

          Пример 3.2.1 - Для н-графа G на рисунке 3.2.1 можно определить следующие понятия:

          а) (v1,v3,v4) – простая цепь;

          б) (v1,v3,v2,v1,v3,v4) – маршрут;

          в) (v3,v1,v2, v4) не маршрут  (т.к. нет ребра {v2,v4 });

          г) (v1,v2,v3,v1) – простой цикл;

          д) вершины v1,v2,v3,v4  - попарно достижимы; v5,v6 – цепь длиной 1, v7 – изолированная вершина или цепь длиной 0;

          е) граф G не является связным, он имеет три компоненты связности с множеством вершин {v1,v2,v3,v4},  {v5,v6}, {v7}.

             

                         Рисунок 3.2.1                                   Рисунок 3.2.2

         

          Пример 3.2.2 - Для орграфа G2  на рисунке 3.2.2 имеет место:

          а) 1, 2, 4, 5 или 1, 2, 3 – простой путь;

          б) 1, 2, 3, 1 – простой контур;

          в)вершина 5 достижима из любой вершины, из вершины 5 не достижима ни одна вершина; вершина 4 достижима из 1, 2, 3 и не достижима из 5;

          г) этот граф связный, но не сильно связный. Он имеет три сильные компоненты связности, задаваемые множеством вершин {1,2,3}, {4}, {5}.

Теорема. Любой граф может быть представлен в виде объединения

непересекающихся связных (сильно связных) компонент. Разложение графа на

 связные (сильно связные) компоненты однозначно.

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

    Число связных (сильно связных) компонент графа G (обозначается K(G)  или C(G)) определяется однозначно. Если  K(G)=1, то граф G связный, если  K(G)>1, то G  - несвязный граф.

          Для орграфа G2 из примера 3.2.2 число сильно связных компонент K(G2)=3, а множество вершин {1,2,3,4,5} имеет разбиение {{1,2,3},{4},{5}}.

 

          Определение компонент связности и сильных компонент связности

          Рассмотрим ещё одну матричную характеристику графа.

          Определение. Квадратная матрица С=( сij ) порядка n (n - число вершин) называется матрицей достижимости (для н-графа матрицей связности), если

сij=

    Матрицу достижимости можно получить следующим образом: пусть А –  матрица смежности, составим матрицу B=(bij)=Е+А+А2+...+Аn  , тогда

сij =.

    Заметим, что существуют другие способы определения матрицы достижимости. В простых случаях матрицу С можно составить по рисунку графа, например, для графа G2 из примера 3.2.2 матрица достижимости будет иметь вид:  С=. Если все элементы матрицы достижимости н-графа сij=1, то граф связный. В общем случае матрица C н-графа является матрицей отношения эквивалентности, соответствующей разбиению множества вершин графа на компоненты. Например, для графа G из примера 3.2.1 матрица связности будет: С=. Блоки, состоящие из единиц, соответствуют трём компонентам связности с множеством вершин {v1,v2,v3,v4},  {v5,v6}, {v7}, т.е. разбиению множества вершин графа на эти компоненты.

    Для орграфа с помощью матрицы достижимости можно найти сильные компоненты связности.

Рассмотрим, кроме матрицы С=(cij), ещё две матрицы Q и  S. Q=CT=( qij),

qij =.

Иногда матрицу Q называют матрицей контрдостижимости. S = (sij) = C  Q, где операция  означает поэлементное произведение матриц C и Q, т.е. sij=cijqij.

    Так как вершины vi и vj находятся в одной сильно связной компоненте, если они взаимно достижимы,  то очевидно, что соответствующий элемент матрицы S равен 1: sij=1. Итак, сильно связная компонента, содержащая вершину vi, состоит из вершин vj, для которых sij=1.

    Пример 3.2.3 - Рассмотрим орграф G2  из примера 3.2.2. Его матрица  

достижимости С была найдена: С = . Q = CT =  -

матрица контрдостижимости. Матрица S = CQ =.

          В первой строке матрицы S три единицы, которые соответствуют вершинам 1, 2, 3, это значит, что сильная компонента, содержащая вершину 1, содержит также вершины 2 и 3, т.е. соответствует множеству вершин {1,2,3}. Мысленно вычёркиваем из матрицы  S строки и столбцы, соответствующие вершинам 1, 2, 3, в оставшейся матрице S1= в первой строке одна единица, отвечающая вершине 4, следовательно, вторая сильная компонента отвечает множеству {4}. Вычёркиваем из  S1 строку и столбец, соответствующие вершине 4, в оставшейся матрице S2= (1) всего одна единица, которая соответствует вершине 5, т.е. последняя компонента сильной связности будет отвечать множеству {5}. Таким образом, граф имеет три компоненты сильной связности  с множествами вершин {1,2,3}, {4}, {5}.

 

          Исследование маршрутов графа        

          Важным применением матрицы смежности является возможность по ней определять маршруты фиксированной длины и их количество.

    Теорема. Пусть дан граф G=(V,E), где V={v1,v2,…,vn} – множество вершин,  A – матрица смежности графа G. Рассмотрим матрицу Ak= AAA=(aij). Если aij=m, то из вершины vi в вершину vj существует m маршрутов длины k.


          Пример 3.2.4. Рассмотрим граф смешанного типа.

                                                      Рисунок 3.2.3

          Его матрица смежности будет матрица А=. По матрице А                                                                                               устанавливаем существование маршрутов длины 1, например, т.к. а13 =0, то маршрутов из 1 в 3 длины 1 нет (записывают: маршрута (13) нет).

А2 =  =. Т.к. а213 =0, то маршрута (13) нет,  т.к. а222 =2, то существует два маршрута (22), т.к. а234 =1, то существует один маршрут (34) и т.д.

А3 = =. Т.к. а313 =1, то существует один маршрут (13), т.к. а321 =3, то существует три маршрута (21) и т.д.

         Последовательность вершин маршрута можно получить, исследуя элементы матриц А, А2, А3 и т.д., или, в случае простых графов, по их рисунку. Наиболее наглядный способ состоит в использовании модифицированной матрицы смежности, в которой вместо единиц записаны названия соответствующих рёбер (дуг). В примере 3.2.4 модифицированная матрица смежности  будет иметь вид: .   

. По последней матрице делаем вывод, что т.к. её элемент , то существует один маршрут длины 2 из вершины 1 в вершину 2, это ; т.к. , то существует два маршрута длины 2 из вершины 2 в 2:  и . По  аналогично можно найти маршруты длины 3 и их количество.

 

          3.3 Эйлеровы и гамильтоновы  графы

        

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

1. Задача о кёнигсберских мостах была сформулирована и решена Эйлером в 1736 году. Она положила начало теории графов как самостоятельной науки. На рисунке  3.3.1 а) изображён план семи мостов через реку Перголи в центре г. Кёнигсберга.

 

                         

                                     а)                                           б)

Рисунок 3.3.1

 

Задача заключалась в том, чтобы пройти каждый мост по одному разу и вернуться в исходную точку. На языке теории графов эту задачу можно сформулировать так: дан граф G (см. рисунок 3.3.1 б)), в котором вершины – части города (берег и острова), рёбра – мосты. Вопрос: существует ли в графе G цикл, содержащий все рёбра? Такой цикл в дальнейшем назвали эйлеровым.

2. Название «гамильтонов цикл» произошло от задачи (игры), которую придумал математик У.Гамильтон в 1857 году. Суть этой задачи в следующем: дан граф, представляющий собой укладку на плоскости додекаэдра (см. рисунок 3.3.2).

 

Рисунок 3.3.2

 

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

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

         Следующая теорема даёт простой способ проверки наличия эйлерова цикла в графе.

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

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

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

а) выбираем произвольную вершину  и ребро , инцидентное .

Переходим в вершину  по ребру . Присваиваем ребру  номер 1, назовём его пройденным и вычёркиваем;

б) находясь в вершине  , не следует выбирать ребро, соединяющее  с

 , если есть возможность другого выбора;

в) находясь в вершине  , не следует выбирать ребро, которое является

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

г) после того как в графе будут занумерованы все рёбра, образуется

эйлеров цикл, причём мы придём в ту вершину, с которой начали. Порядок нумерации соответствует последовательности обхода рёбер.

Пример 3.3.1 -  Найдём эйлеров цикл в графах на рисунках 3.3.3 а) и б).

                                         

                                    а)                                                          б)

                                                        Рисунок 3.3.3 

        

Граф на рисунке 3.3.3 а) не содержит эйлеровых циклов, так как в нём есть вершины, имеющие нечётные степени: , .

         Граф на рисунке 3.3.3 б) эйлеров, поскольку . Построим эйлеров цикл в этом графе:

а) выберем вершину 1 и ребро , присвоив ему номер 1, перейдём

в вершину 2;

б) находясь в вершине 2, не выбираем пройденное ребро , из

оставшихся инцидентных этой вершине рёбер ни одно не является перешейком, поэтому выбираем любое, например, , присваиваем ему номер 2 и переходим в вершину 4;

в) рассуждая аналогично, обходим оставшиеся рёбра в порядке: ,

, , , , , . Итак, получен эйлеров цикл , , , , , , , , .

Граф называется гамильтоновым, если в нём имеется простой цикл,

содержащий все вершины графа по одному разу, этот цикл также называется гамильтоновым. Гамильтоновой называется и простая цепь, содержащая все вершины графа. Гамильтонов цикл не обязательно содержит все рёбра графа. Очевидно, что гамильтоновым может быть только связный граф. Задача нахождения гамильтоновых циклов значительно сложнее аналогичной задачи для эйлеровых циклов. Неизвестен такой же общий простой критерий существования гамильтонова цикла в графе. Известны лишь некоторые достаточные условия его существования. Необходимые условия существования неизвестны за исключением некоторых особых типов графов. Приведём два достаточных признака, простых в практическом применении. Пусть дан связный н-граф G без петель, имеющий  вершин.

         Теорема. Если для любых двух несмежных вершин  и  графа G выполняется условие , то в G существует гамильтонов цикл.

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

         Пример 3.3.2 - Полный граф (см. рисунок 3.1.10) является как эйлеровым, так и гамильтоновым, так как выполняются необходимые и достаточные условия эйлеровости и достаточные условия гамильтоновости: число вершин , произвольно обозначив вершины через a,b,c,d,e, имеем  и для любых двух вершин графа выполняется , где .

         Пример 3.3.3 - Для графа на рисунке 3.3.3 б), число вершин которого , не выполняется достаточное условие существования гамильтонова цикла: например, , однако, такой цикл в графе существует, это, например, цикл 1,2,4,5,3,6,1. Таким образом, этот граф как эйлеров, так и гамильтонов.

 

3.4 Расстояния в графах, взвешенные графы

 

Пусть G=(V,E) связный н-граф, vi, vj – две не совпадающие вершины G.

Определение. Расстоянием между вершинами vi и vj (обозначается d(vi, vj)) называется минимальная длина простой цепи с концами в vi и vj.

Таким образом, расстояние удовлетворяет всем аксиомам метрики:

а) d(vi, vj)≥0, причём d(vi, vj)=0  vi =vj;

б) d(vi, vj)= d(vj, vi);

в) d(vi, vj)≤ d(vi, vк)+ d(vк, vj) неравенство треугольника.

         Пусть V={v1,v2,…,vn} – множество вершин графа. Рассмотрим матрицу D=(dij), где dij =d(vi, vj). D называется матрицей расстояний. Очевидно, D=DT , т.е. D – симметрическая матрица.

         Введём ещё несколько понятий:

1. Эксцентриситетом вершины v  (обозначается e(v)) называется  max{d(u,v)/uV}, т.о., эксцентриситет равен расстоянию от данной вершины до наиболее удалённой от неё. В матрице расстояний e(vi) равен наибольшему из чисел, стоящих в і-ой строке.

2. Диаметром графа G (обозначается d(G)) называется максимальный из всех эксцентриситетов: d(G)=max{e(v)/vV}.

4. Радиусом графа G (обозначается r(G)) называется минимальный из всех эксцентриситетов: r(G)=min{e(v)/vV}.

5. Вершина v называется периферийной, если e(v)=d(G); Вершина v называется центральной, если e(v)=r(G). Множество всех центральных вершин графа называется его центром.

         Пример 3.4.1 - Рассмотрим граф на рисунке 3.4.1.

 

                                                         D= - матрица расстояний графа.

                              Рисунок 3.4.1

         

          Наибольшее число в строке -  это эксцентриситет соответствующей вершины, поэтому e(1) =3, e(2) =2, e(3) =3, e(4) =2, e(5) =2. Диаметр графа d(G)=3, как наибольший из эксцентриситетов, радиус -  r(G)= 2, как наименьший. Вершины 1, 3 – периферийные, вершины 2,4,5 – центральные, множество {2,4,5} – центр графа.

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

          Опредение. Пусть дан граф G(V,E). Пометкой (или распределением меток) графа называется пара функций: f: VSv и g: ESE, где Sv, SE – множества меток вершин и рёбер (дуг). Четвёрка (V,E,f,g) называется взвешенным или помеченным графом.

Если vV, то  f(v) – вес вершины v, если eE, то g(e) – вес дуги e. Часто бывают помеченными только вершины или только рёбра (дуги).

Пример 3.4.2 - На рисунке 3.4.2 изображён помеченный граф (V,E,f,g), представляющий схему автомобильных дорог с указанием их длины.

Рисунок 3.4.2

 

V1  - Астана, V2  - Экибастуз, V3  - Семипалатинск, V4  - Караганда.

V={V1, V2, V3, V4} ,  Е={{V1, V2 },{V2, V3}, { V1, V4},{ V2, V4}}, f: VSv , Sv – множество городов,  f(V1)= Астана,   f(V2)= Экибастуз,   f(V3)= Семипалапинск, f(V4)= Караганда. g: ESE , SE – множество расстояний,  g({V1, V2})=400, 

g({V2, V3})=600,  g({V1, V4})=250,   g({V2, V4})=300.

Информацию о весах дуг во взвешенном графе можно представлять в виде матрицы весов W=(wij), где wij – вес дуги (vi,vj), если эта дуга существует, если не существует, то соответствующий вес обозначают 0 или ∞ в зависимости от приложений (∞ - если вершины не смежные). Для графа из примера 3.4.2 матрица весов имеет вид: W=.

Для взвешенных графов также вводятся понятия расстояния, эксцентриситета и т.д. Пусть G(V,E) взвешенный граф, в котором вес каждой дуги (vi,vj) есть некоторое число (vi,vj), vi,vjV.

1. Весом маршрута  (v1vп+1) называется число =.

2. Взвешенным расстоянием dw(v1,vn+1) между вершинами v1 и vп+1 называется минимальный из весов  v1 v п+1 маршрутов.

3.  Кратчайшим маршрутом между vи vп+1 называется маршрут, вес которого равен dw(v1, vn+1).

4. Взвешенным эксцентриситетом вершины v (обозначается еw(v)) называется число ew(v)=max{dw(v,u)/ u V}.

5. Взвешенной центральной вершиной графа G называется вершина v , для которой ew(v)=min{еw(u)/uV}.

6. Взвешенным радиусом графа G (обозначается rw(G)) называется взвешенный эксцентриситет центральной вершины.

 

Нахождение кратчайших маршрутов (путей)

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

Рассмотрим алгоритм Дейкстры, который можно использовать только для взвешенных графов с неотрицательными весами всех рёбер. Этот алгоритм можно встретить в различных вариантах, например, с использованием и без матрицы весов, для применения в компъютере и т.д. Мы рассмотрим два варианта алгоритма Дейкстры (с использованием и нет матрицы весов).

Алгоритм Дейкстры 1.

Пусть G(V,E) – взвешенный граф, имеющий n вершин и  W=(wij), – его матрица весов . Пусть требуется найти взвешенное расстояние от фиксированной вершины vі (она называется источником) до некоторой другой вершины (вообще по алгоритму Дейкстры 1 находят сразу расстояния от источника до всех остальных вершин).

Обозначим Т1 множество вершин V \ { vi} , т.е. Т1 – это множество всех вершин V без источника. Обозначим D(1)=(d1(1) , d2(1), …, dn(1)), где di(1)=0, 

dj(1)= wij  (i≠j), т.е. D(1) – это і-ая строка в матрице весов. 

Пусть на шаге S уже определены множества вершин TS  и строка  D(S)=(d1(S) , d2(S), …, dn(S)). Наша задача перейти от TS  к  TS+1 и от D(S) к  D(S+1)

Выберем в TS вершину vj такую, что dj(S)=min{ dk(S)/ vk TS}. Положим TS+1=TS\{},  D(S+1)=( d1(S+1), …, dn(S+1)), где , если ,

  , если .

На шаге S = n-1 получим строку  D(n-1)=( d1(n-1), d2(n-1)…, dn(n-1)), в которой  dj(n-1)  равно взвешенному расстоянию от вершины vі до вершины vj:

d j(n-1)=dw(vі, vj).

Пример 3.4.3 -  Рассмотрим граф на рисунке 3.4.3.

 


                                                      W= - матрица весов.

                  Рисунок 3.4.3

 

Пусть требуется найти кратчайшие взвешенные расстояния от вершины A (источник) до остальных вершин.  V={A,B,C,D,E,F} – множество вершин.

Будем полагать, что min(a,∞)=a, min(∞,∞)=∞, a+∞=∞, ∞+∞=∞.

1 шаг. А- источник, , .

2 шаг. В  выбираем среди элементов, отмеченных ^ (т.е. кроме элемента отвечающего источнику) наименьший, и подчёркиваем его. Из  убираем вершину, соответствующую подчёркнутому элементу (это В). Строим . Для определения  делаем вспомогательную запись: из матрицы W выписываем строку, соответствующую В, и прибавляем ко всем её элементам (кроме первого и второго) подчёркнутое число 5. Сравним полученные числа с  и в ставим на соответствующие места наименьшие:                                     5  0  3   7    2   10

           5   5    5    5 

 8  12   7   15,        .

         3 шаг. ,  6   3   0   ∞   7    ∞

                                                                             6    6    6

                                                                             ∞  13   ∞   ,  .

          4 шаг.  ,  ∞   2   7   ∞   0    4          

                                                                         7   7    7

                                                                         ∞   7   11,         .

5 шаг. ,  ∞   10   ∞   2    4   0

                                                                        11       11         

                                                              13       11,         .

n=6, n-1=5, значит, это последний шаг. По виду  делаем вывод, что взвешенные расстояния от вершины А до остальных вершин равны ,, , , , .

Алгоритм Дейкстры 2

         Этот алгоритм позволяет найти не только вес кратчайшего пути, но и сам путь, его иногда называют алогоритмом расстановки меток. Пусть требуется найти кратчайшее взвешенное расстояние и путь от вершины   до вершины . Каждой вершине поставим в соответствие пару (метку) . Если вершина  имеет метку , то первая координата означает присвоенное расстояние от  до , вторая – предыдущую вершину пути от  до . Метки, как и вершины, могут находиться в двух состояниях – быть временными и постоянными.

Алгоритм  содержит следующие шаги:

1) Начинаем с источника . Приписываем этой вершине метку  и делаем постоянной. Каким - либо образом это отмечаем, например, звёздочкой или подчёркиваем:. Остальные вершины временные и имеют метки .

2) Пусть вершина   стала постоянной. Рассмотрим все вершины , смежные с . Прибавим величину  к расстоянию (весу) от  до . Если эта сумма меньше, чем временное расстояние, присвоенное вершине (т.е. её предыдущая первая координата), то заменим этой суммой первую координату , а вторую координату заменим на .

3) Находим минимальное из расстояний, приписанных временным

вершинам , смежным с  Вершину с наименьшим весом делаем постоянной.

4)     Если вершина  не постоянна, то возвращаемся к пункту 2, если  

постоянна, то расстояние, присвоенное вершине , является кратчайшим взвешенным расстоянием от  до . Алгоритм закончен.

         Для нахождения пути от  до  надо начать с , по второй координате найти предыдущую ей вершину, для этой вершины аналогично найти предыдущую и т.д., пока не будет достигнута первая вершина пути . Перестановка вершин в обратном порядке даст путь от  до .

         Рассмотрим этот метод на том же примере. Для графа на рисунке 3.4.3 найти кратчайшее расстояние и путь от вершины A до вершины F.

 Заметим, что этот алгоритм можно оформлять, изображая на каждом шаге граф с указанием вершин с их метками, найденными на этом шаге (см., например, [4], стр.611). Мы обойдёмся без рисунков.

1 шаг. Приписываем источнику А метку , делаем её постоянной и отмечаем , остальные вершины временные и имеют метки : , ,…, .

1-ая итерация.

2 шаг. С вершиной А смежны вершины В и С:

- от до расстояние 5, 5+0 < , поэтому В меняет метку: ;

- отдо расстояние 6, 6+0 < , поэтому С меняет метку: ;

         3 шаг. min(5,6)=5, поэтому В становится постоянной, отмечаем её: . , возвращаемся на второй шаг.

         2-ая итерация.

2 шаг. С вершиной В смежны вершины С,D,E,F:

- от до расстояние 3, 5+3=8 >6, поэтому C не меняет метку: ;

- от дорасстояние 7, 5+7=12 < , поэтому D меняет метку: ;

- от дорасстояние 2, 5+2=7 < , поэтому E меняет метку: ;

- от дорасстояние 10, 5+10=15<, поэтому F меняет метку: ;

3 шаг. min(6,12,7,15)=6, поэтому С становится постоянной: . , возвращаемся на второй шаг.

 3-ая итерация.

2 шаг. С вершиной С смежна вершина E (рассматриваем только временные вершины):

- от  до расстояние 7, 6+7=13>7, поэтому Е не меняет метку:;

         3 шаг. - постоянная, , возвращаемся на второй шаг.

4-ая итерация.

2 шаг. С вершиной Е смежна вершина F:

- от  до расстояние 4, 7+4=11<15, поэтому F меняет метку: ;

3 шаг. - постоянная. Итак, вершина F, до которой надо было найти кратчайшее расстояние, стала постоянной, поэтому процесс завершен. 11 есть кратчайшее расстояние от А до F. Если бы совокупность вершин, смежных с постоянной вершиной, была исчерпана до того, как мы достигли вершину F, то задача не имела бы решения, т.к. не было бы пути от А до F.

         Для нахождения кратчайшего пути идём последовательно от F к А по указанию второй координаты: F(11,E), Е(7,В), В(5,А), А. Переставив вершины в обратном порядке, получим искомый путь: (A,B,E,F).

 

         Потоки в сетях

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

         Сетью называется связный ориентированный граф G(V,E) без петель. В сети выделяют две вершины  - источник (исток) и  - сток. Каждой дуге ставится в соответствие число  – пропускная способность дуги .

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

   .

Потоком в сети называется такая функция , определённая на множестве дуг E (), что 1) ; 2)

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

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

         Теорема Форда-Фалкерсона. Максимальный поток в сети равен пропускной способности минимального разреза.

         Алгоритм Форда-Фалкерсона нахождения максимального потока основан на следующем:

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

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

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

         Пример 3.4.4 – Найти максимальный поток из  в  и указать минимальный разрез сети , , заданной матрицей пропускных способностей .

Рисунок 3.4.4

 

По матрице С построим граф (см. рисунок 3.4.4). Начнём перебирать все пути из  в , указывая над стрелками поток через данную дугу и её пропускную способность (в скобках), под стрелкой то же после увеличения потока на . Полагаем, что вначале поток через все дуги равен нулю:

1) = min(11,17)=11;

          2) ; = min(13,11,13,10)=10;

          3) ; = min(13-10,11-10,17-11)=1.

         Больше прямых путей из  в  без насыщенных дуг нет. Рассмотрим маршруты из  в , содержащие как прямые, так и обратные дуги:

         1) ; min(13-11,6,11,17-12)=2.

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

 

         3.5 Деревья, лес. Минимальные остовные деревья

        

Деревья являются самым распространённым классом графов, применяемых в программировании, это в некотором смысле простейший класс.

         Определение. Деревом называется связный н-граф, не содержащий циклов; лесом называется несвязный н-граф без циклов.

        

Таким образом, компонентами связности любого леса являются деревья.

Пример 3.5.1 -  На рисунке 3.5.1 а) изображено дерево; на рисунке 3.5.1 б) граф, не являющийся деревом, так как содержит цикл; на рисунке 3.5.1 в) лес, состоящий из трёх деревьев. 

                                                   

                                               

 

 

                     а)                                          б)                                     в)

                                              Рисунок 3.5.1

 

Теорема (*). Пусть G – н-граф без петель, содержащий n вершин, тогда следующие условия эквивалентны:

а) G – дерево;

б) G – связный граф, содержащий n-1 ребро;

в) G – ациклический граф, содержащий n-1 ребро;

г) любые две не совпадающие вершины графа G соединяет единственная

простая цепь;

д) G – ациклический граф такой, что если какую-либо пару его

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

Определение. Вершина v графа называется концевой (висячей, листом), если её степень =1. Ребро инцидентное концевой вершине называется концевым. 

Любое дерево можно «подвесить» за какую-либо его вершину v, т.е. v расположить на верхнем этаже, смежные с ней вершины этажом ниже и т.д. (как на рисунке 3.5.2). В этом случае вершина v называется корнем дерева.                                          

 

 

                       

 

 

 

 

                      Рисунок 3.5.2                                     Рисунок 3.5.3

 

Все концевые вершины расположены на нижних этажах, они называются вершинами типа 1. Если из дерева удалить все вершины типа 1, то в оставшемся дереве концевые вершины называются вершинами типа 2 в исходном дереве. Аналогично определяются вершины типов 3, 4 и т.д. Конечное дерево имеет вершины лишь конечного числа типов, причём число вершин максимального типа равно 1 или 2. На приведённом выше рисунке 3.5.2 вершины v3, v4, v 5, v 7, v 8 – концевые, типа 1; v 1, v 6 – типа 2; v 2 – типа 3; v – типа 4.

         Для каждого неориентированного дерева с корнем можно определить соответствующее ориентированное дерево с корнем: все рёбра такого дерева ориентируются от корня, причём данная ориентация единственная. При выборе другой вершины - корня получаеся другой орграф-дерево.

Пример 3.5.2 -  Рассмотрим граф-дерево на рисунке 3.5.3. Цифрами обозначены типы вершин. Таким образом, этот граф имеет две вершины максимального типа 4. Можно построить два различных ориентированных корневых дерева с корнем в вершине максимального типа: корень – левая вершина максимального типа 4 (см. рисунок 3.5.4); корень – правая вершина максимального типа 4 (см. рисунок 3.5.5).  

                                                                         

                    Рисунок 3.5.4                                               Рисунок 3.5.5

 

Если убрать ориентацию, то графы на трёх рисунках изображают одно и то же дерево.

Определение. Рассмотрим н-граф G=(V,E). Подграф  графа G называется остовом или каркасом графа G, если   и – лес, который на любой связной компоненте графа G образует дерево.

Если G связный граф, то его остов  есть подграф графа  G, являющийся деревом, которое называется остовным деревом.

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

Пример 3.5.3. Граф G на рисунке 3.5.6 состоит из двух связных компонент. Рёбра обозначены цифрами. В качестве остова  графа можно взять лес с рёбрами 2, 3, 4, 6, 7, удалив рёбра 1, 5, 8. Остов определяется неоднозначно, например, удалив рёбра 3, 5, 6, также получим лес, состоящий из двух остовных деревьев с рёбрами 2, 1, 4 и 7, 8.

 

      

   

      

   


Рисунок 3.5.6

   

    Теорема. Число рёбер произвольного н-графа G, которое необходимо удалить для получения остова, не зависит от последовательности их удаления и равно m-n+к, где m – число рёбер, n – число вершин,  к – число компонент связности графа.

Доказательство. Пусть Сi – і-ая компонента связности графа G (i=). Пусть Сi содержит  ni вершин. Тогда по теореме (*) её остовное дерево  Кi будет содержать (ni -1) рёбер.

Если mi – число рёбер Сi,  ni -1– число рёбер Кi, то для получения Кi из Сi нужно удалить (mi-(ni -1))= mi - ni +1 рёбер. Всего компонент связности к, поэтому суммируя все удалённые рёбра по всем компонентам связности графа G  получим: = - +=m-n+к.

Определение. Число ν(G)=m-n+к называется  цикломатическим числом (или цикломатическим рангом) графа G. Число  называется коциклическим рангом или корангом. Таким образом,  - это число рёбер, входящих в любой остов графа G.

Следствия: а) н-граф G является деревом (лесом) тогда и только тогда, когда ν(G)=0; б) н-граф G имеет единственный цикл тогда и только тогда, когда  ν(G)=1.

          Число остовов в графе можно найти с помощью матрицы Кирхгофа, которая определяется так:, где

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

Пример 3.5.4 - Для графа на рисунке 3.5.7 степени вершин будут равны

, .  - матрица Кирхгофа.

 

Рисунок 3.5.7

 

Рассмотрим, например, алгебраическое дополнение элемента :

. Таким образом, существует 8 остовных деревьев графа.

 

Определение остовного дерева минимального веса

Вес остовного дерева взвешенного графа G равен сумме весов, приписанных его рёбрам. Остов минимального веса (или минимальное остовное дерево) – это такой остов графа G, что его вес меньше или равен весу любого другого остова графа.

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

Алгоритм Краскала (Крускала).

Идея этого метода следующая: дан граф G=(V,E), будем формировать дерево T=(V,En-k), выбирая рёбра с наименьшим весом так, чтобы не возникало циклов:

1. Строим граф , состоящий из множества вершин V и ребра , которое имеет наименьший вес (т.е. , где ).

2. Если граф  уже построен и   , то строим граф  добавляя к множеству рёбер  ребро , имеющее наименьший вес среди рёбер, не входящих в  и не составляющее циклов с рёбрами (т.е. , где ).

3. При   алгоритм закончен и  - есть остов минимального веса, его вес равен сумме весов всех его рёбер.

Пример 3.5.5 - Дан взвешенный граф (рисунок 3.5.8). Построить остов

минимального веса и найти его вес:

                                                                       

                      Рисунок 3.5.8                                  Рисунок 3.5.9

а)  , где V ={A,B,C,D,E,F,G}, E1={{B,D}};

б) , E2={{B,D},{E,D}};

в), E3={{B,D},{E,D},{A,E}};

г)  , E4={{B,D},{E,D},{A,E},{G,F}};

д) , Е5={{B,D}, {E,D}, {A,E}, {G,F}, {E,F}};

е) ,  E6={{B,D}, {E,D}, {A,E}, {E,F}, {F,G}, {C,D}}.

Число вершин графа n=7, число компонент k=1, число рёбер m=10,  коранг , значит, остов должен содержать 6 рёбер, удалено ν=m-n+к=10-7+1=4 ребра. Алгоритм закончен, построено дерево минимального веса (рисунок 3.5.9). Его вес равен 1+2+2+4+3+4=16.

          Заметим, что если множество Т содержит более одного дерева, то существует ребро, при добавлении которого не возникает цикла – оно соединяет два дерева. Добавленное ребро - кратчайшее возможное (в примере 3.5.5 ребро {E,F} соединило два дерева).

          Алгоритм Прима (или алгоритм ближайшего соседа).

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

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

          1 шаг. Начинаем с любой вершины, например, . Полагаем  , , .

          2 шаг. Находим ребро  такое, что  и = =. Полагаем , , .

          3 шаг. Если , то - искомый остов, если нет, то переходим ко второму шагу.

          Рассмотрим тот же пример 3.5.5, но для решения применим алгоритм Прима: . Начнём с вершины А.

1 шаг. , , .

1-ая итерация.

2 шаг. , , ,.

3 шаг.  2 шаг.

2-ая итерация.

2 шаг. , , ,.

3 шаг.  2 шаг.

3-ая итерация.

2 шаг. , , ,.

3 шаг.  2 шаг.

4-ая итерация.

2 шаг. , , ,

3 шаг.  2 шаг.

5-ая итерация.

2 шаг. , , , .

3 шаг.  2 шаг.

6-ая итерация.

2 шаг. , , , .

3 шаг.  - остов минимального веса. Его вес

Алгоритм закончен. Построение остова лучше делать сразу, прибавляя на каждом шаге соответствующее ребро (рисунок 3.5.9).

         

 

 

3.6 Раскраска графов. Планарность

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

          Многие практические задачи сводятся к построению раскраски графов: задачи составления расписаний, распределения оборудования, проектирования некотоых технических изделий, раскрашивания географических карт и т.д.

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

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

          Алгоритм последовательной раскраски.

1.     Произвольной вершине  графа  присваиваем цвет 1.

2.     Если вершины  раскрашены  цветами 1,2,…,(), то

новой произвольно взятой вершине  припишем минимальный цвет, не использованный при раскраске вершин из её окружения, т.е. множества вершин таких, что . Обозначим через окружение вершины .

          Пример 3.6.1- Оценить и найти хроматическое число графа на рисунке 3.6.1. Раскрасить его вершины по алгоритму последовательной раскраски.

         

Рисунок 3.6.1

 

          Максимальная степень вершин графа =3, поэтому .

Алгоритм последовательной раскраски: а) выберем вершину  и присвоим ей цвет 1. На рисунке указываем цвет рядом с обозначением вершины. Окружение : . Окрасим  и  в цвет 2; б) выберем вершину , .  и  уже окрашены в цвет 2,  не окрашена. Минимальным цветом, не использованным при раскраске вершин из окружения , является цвет 1, поэтому присваиваем  цвет 1; в) .  окрашена в цвет 2,  не окрашена, поэтому для  выбираем цвет 1; г) ,  и  окрашены в цвет 1,  не окрашена, поэтому присваиваем  цвет 2; д) ,  и  окрашены в цвет 2, поэтому присваиваем  цвет 1.

          Таким образом, получена раскраска графа в два цвета. Эта раскраска минимальна, поэтому =2.

 

          Планарные и плоские графы

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

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

 

Рисунок 3.6.2

 

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

          Не всякий н-граф является планарным. Для формулировки критерия планарности введём понятие гомеоморфности графов.

          Пусть граф   содержит ребро , а граф  получен из графа  добавлением новой вершины  в множество  и заменой ребра  рёбрами  и . Эта операция называется операцией подразбиения ребра в графе , а граф  называется расширением графа . Два графа  и  называются гомеоморфными, если их можно получить из одного графа  с помощью последовательности подразбиений рёбер.

          Пример 3.6.3 – На рисунке 3.6.3 графы  и  являются расширением графа , поэтому эти графы гомеоморфны.

 

Рисунок 3.6.3

 

          Критерий планарности графов даёт следующая теорема.

          Теорема Понтрягина-Куратовского. Граф планарен тогда и только тогда, когда он не содержит подграфа, гомеоморфного  и .

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

          На практике требуется ответить на вопросы: а)будет ли граф планарным?; б) если будет, то как уложить его на плоскости? На первый вопрос отвечает теорема Понтрягина-Куратовского, хотя практически применить её не всегда просто. Ответ на второй можно найти в различных книгах, например, один из методов плоской укладки графа дан в книге С.Д.Шапорева [6], стр. 160.

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

          Пример 3.6.4 – Толщина любого планарного графа равна 1; число планарности графа  равна . Его толщина . Действительно из графа  надо удалить 1 ребро, чтобы получить планарный граф. На рисунке 3.6.4 графы  и  - плоские части графа .

                       

Рисунок 3.6.4

 

          Проблема раскраски плоских графов является одной из самых известных проблем теории графов. Она возникла в связи с раскраской географических карт: любые две соседние страны должны быть окрашены в различные цвета. Известно, что для раскрашивания карты пяти красок достаточно, трёх – нет. Отсюда возникла гипотеза четырёх красок: всякий планарный граф 4-раскрашиваем. На протяжении многих лет проблема четырёх красок оставалась нерешённой. Только в 1890 году Р.Д. Хивуд смог доказать, что произвольную плоскую карту можно раскрасить только пятью цветами, т.е. была доказана теорема: всякий планарный граф можно раскрасить пятью красками.

 

 

          4 Элементы комбинаторики

 

          4.1 Правила суммы и произведения

 

Комбинаторика – раздел математики, в котором решаются задачи

построения подмножеств некоторых, чаще всего конечных, множеств. Эти подмножества (или выборки, или комбинации, или комбинаторные

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

конфигураций, алгоритмов их построения, оптимизации таких алгоритмов.

          Вот некоторые современные задачи, решаемые комбинаторными методами:

          а) перечислительные задачи  отвечают на вопрос о количестве

комбинаторных конфигураций;

          б) задачи о маршрутах – отыскание оптимального плана, например, 

кратчайшего пути;

          в) комбинаторные задачи теории графов – задачи сетевого планирования, задача окраски графов, и т.д.

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

          1. Правило суммы.

          Если из некоторого конечного множества подмножество А ( которое может содержать один элемент) можно выбрать способами, а подмножество В (АВ) другими способами, то выбор А или В можно получить   способами.

          Это правило можно сформулировать и в терминах теории множеств: если мощности множеств (число элементов конечного множества) соответственно равны , , то ; в случае, когда  имеем .

2.     Правило произведения.

          Если из некоторого конечного множества подмножество А ( которое может содержать один элемент) можно выбрать способами и после каждого такого выбора подмножество В можно выбрать способами, то

 последовательный выбор А и В можно осуществить   способами.

          В терминах теории множеств: если , , то , где  - прямое произведение множеств А и В.

          Пример 4.1.1. В классе 14 девочек и 10 мальчиков. Сколькими способами можно выбрать двух учеников одного пола?

          Решение:

          по правилу произведения двух девочек можно выбрать

 способами, а двух мальчиков способами. Так как следует выбрать двух учеников одного пола, т.е. или двух девочек или двух мальчиков, то по правилу суммы таких способов выбора будет 182+90=272.

 

          4.2 Перестановки, размещения и сочетания

 

          Рассмотрим задачи, связанные с подсчётом числа способов построения различных комбинаторных конфигураций из элементов конечного множества.

          Определение. Пусть дано конечное множество А, состоящее из  

элементов (). Перестановкой элементов множества А называется любой кортеж (т.е. упорядоченное множество), состоящий из  элементов этого

множества.

          Таким образом, перестановки отличаются друг от друга только порядком входящих в них элементов.

          В некоторых учебниках (см.[3] стр.78) перестановку опредеяют как взаимно однозначную функцию . Если , то можно считать, что , и тогда перестановку удобно задавать таблицей, например, , (=5). Эта таблица называется подстановкой, по сути подстановки и перестановки одно и то же. Каждой такой подстановке можно поставить в соответствие граф. Так подстановке f, приведённой выше соответствует граф на рисунке 4.2.1.

 

 

 

 

 

 

Рисунок 4.2.1

 

          Число перестановок из    элементов обозначается . Легко показать, что (факториал, , по определению ).

          Действительно, на первое место в кортеже можно поставить дюбой из  элементов, на второе – любой из оставшихся  (-1)-го, на третье – любой из

(-2) оставшихся и т.д. Для последнего места останется только один элемент.

Поэтому    = .

          Пример 4.2.1 – Составить различные перестановки из элементов множества ; подсчитать их число.

          Решение:

          . По выше - приведённой формуле: . Действительно, имеем следующие перестановки: .

          Определение. Пусть множество А состоит из элементов () и .

Размещением из элементов по называется любой кортеж, состоящий из  попарно различных элементов множества А.

          Таким образом, размещения отличаются друг от друга либо самими элементами, либо порядком их расположения.

          Число размещений из элементов по  обозначается . Доказано, что . Действительно, для составления

каждого размещения нужно выбрать элементов из и упорядочить их. На первое место можно поставить любой из имеющихся элементов ( т.е.

заполнить первое место можно способами), на второе место – любой из оставшихся (-1) элементов, и т.д. После заполнения мест с первого по (-1) останется - (-1) = - +1 элементов, из которых выбирается элемент на последнее место. Таким образом, по правилу произведения существует

 способов выбора  элементов из  , т.е. 

.

            Пример 4.2.2 – Составить различные размещения из элементов множества  по два; подсчитать их число.

          Решение:

          , =2 . . Действительно, таких размещений шесть: .

          Определение. Пусть множество А состоит из элементов () и .

Сочетанием из элементов по называется любое подмножество множества А, состоящее из  элементов.

          Таким образом, сочетания отличаются друг от друга хотя бы одним элементом.

          Число сочетаний из элементов по  обозначается . Легко показать, что .

          Действительно, число размещений из элементов по () можно найти так: выбрать элементов из  элементов множества А, что возможно сделать  способами (по определению сочетаний); затем в каждом из полученных сочетаний,  содержащих элементов, произвести все возможные перестановки.  Это можно сделать  способами. Тогда по правилу произведения , откуда .

          Полезно знать некоторые свойства числа :

          1) ;

          2) ;

          3) , ;

          4) Числа  часто называют биномиальными коэффициентами. Действительно, формула бинома Ньютона имеет вид  

 . Из этой формулы легко получить ещё одно свойство чисел : при  формула бинома Ньютона превращается в равенство

.

            Пример 4.2.3 – Составить различные сочетания из элементов множества  по два; подсчитать их число.

          Решение:

          , =2 . .

          Действительно, таких сочетаний три: .

 

          4.3 Размещения, сочетания и перестановки с повторениями

 

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

          Определение. Пусть множество А состоит из элементов () и .

Размещением с повторениями из элементов множества А по называется  кортеж, состоящий из  элементов множества А.

          Таким образом, размещения с повторениями могут отличаются друг от друга либо элементами, либо порядком их расположения, либо количеством повторений элементов.

         Число размещений с повторениями из элементов по обозначается.

Легко доказать, что . Действительно, пусть множество А состоит из  элементов и  один из его кортежей (размещений с повторениями). Каждый элемент этого размещения может повторяться в других размещениях, т.е. на каждое место кортежа может претендовать любой из  элементов множества А. Поэтому число размещений из элементов по с повторениями .

          Пример 4.3.1 – Составить размещения с повторениями из элементов множества  по два; подсчитать их число.

          Решение:

          , =2 . .

          Действительно, это следующие размещения: .

          Определение. Сочетанием с повторениями из элементов множества А по  называется любое подмножество множества А, состоящее из  элементов, причём один и тот же элемент может повторяться.

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

          Число сочетаний с повторениями из элементов по  обозначается . Доказано, что .

            Пример 4.3.2 – Составить сочетания с повторениями из элементов множества  по два; подсчитать их число.

          Решение:

          , =2 . . Это следующие сочетания: .

          Определение. Пусть  во множестве с   элементами есть    различных элементов. Причём первый элемент повторяется  раз, второй -  раза и т.д., - ый повторяется  раз: .

          Перестановки из   элементов данного множества называются перестановками с повторениями из   элементов.

          Число перестановок с повторениями из    элементов обозначается . Доказано, что .

          Пример 4.3.3 – Сколько различных четырёхзначных чисел можно составить из цифр 1,1,2,4.

          Решение:

          данное множество состоит из четырёх цифр (=4), среди которых 1 повторяется два раза: =2; 2 – один раз: =1, 4 - один раз: =1. По выше приведённой формуле число четырёхзначных чисел из цифр 1,1,2,4 равно

.

 

          4.4 Разбиения

         

          Пусть множество А состоит из элементов, . Пусть  - разбиение множества А на k подмножеств (определение разбиений см. на стр.6),  , . Назовём кортеж  упорядоченным разбиением множества А на k подмножеств. Обозначим число упорядоченных разбиений  так: , где , . Доказано, что .

            Пример 4.4.1 – В общежитии остались не заселёнными 3 комнаты на 6, 4 и 2 человека. Сколькими способами можно расселить по этим комнатам 12 студентов?

          Решение:

          =6+4+2=12, , =6; =4, =2.

По выше - приведённой формуле число способов расселения равно: .

 

          4.5 Понятие производящей функции

 

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

          Идея этого метода в следующем: пусть дана некоторая числовая последовательность  и последовательность функций

 Составим формально ряд  Функция  называется производящей функцией для последовательности  относительно заданной последовательности . Часто используют  или .

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

            Пример 4.5.1 – По формуле бинома Ньютона имеем . Поэтому для последовательности биномиальных коэффициентов  производящей функцией будет .

            Пример 4.5.2 – Пусть =, =,  Тогда

 - это сумма членов бесконечной геометрической прогрессии со знаменателем . Если , то последний ряд сходится и его сумма равна . Таким образом, 

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

            Пример 4.5.3 – Пример из теории вероятностей: пусть производится  независимых испытаний, в каждом из которых вероятность появления события А разная: в первом - , во втором - , …, в -ом - ; соответственно  - вероятности непоявления события А;  - вероятность того, что в  испытаниях события А появится ровно раз. Заметим, что вероятность  находится по формуле Бернулли, если в каждом испытании вероятность появления события А одинаковая. В нашем случае эта вероятность определяется с помощью производящей функции. Производящей функцией вероятностей    называют функцию . Вероятностьравна коэффициенту при  в разложении производящей функции по степеням z. Например, при =2 имеем

 .

          Коэффициент при  равен вероятности того, что событие А появится два раза в двух испытаниях:; при  - вероятности того, что событие А появится один раз в двух испытаниях: ; при ( т.е. свободный член) - вероятности того, что событие А не появится ни разу в двух испытаниях: .

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

          В теории вероятностей производящую функцию можно определить по - другому, если она нужна для других целей. Например, для нахождения числовых характеристик дискретных случайных величин с целыми неотрицательными значениями, производящую функцию определяют так:

  , где ,,…,,… соответственно

 вероятности возможных значений 0,1,2,3,…случайной величины Х. Легко показать, что математическое ожидание равно ; дисперсия  - .

                  

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список литературы

 

1.     Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики. – М.: ИНФРА-М, Новосибирск: изд-во НГТУ, 2002.- 280 с.

2.     Москинова Г.И. Дискретная математика. Математика для менеджера в примерах и упражнениях: Учебное пособие. – М.: Логос, 2004. – 240 с.

3.     Новиков Ф.А. Дискретная математика для программистов.Учебник для вузов. 2-е изд.  – СПб.: Питер, 2004. – 364 с.: ил. – (Серия «Учебник для вузов»).

4.     Андерсон, Д. Дискретная математика и комбинаторика.: Пер. с англ. – М.: Издатель- ский дом «Вильямс», 2004. – 960 с.: ил. – Парал. тит. англ.

5.     Белоусов А.И., Ткачев С.Б. Дискретная математика. – М.: изд-во МГТУ им. Н.Э.Баумана, 2001

6.     Шапорев С.Д. Дискретная математика. Курс лекций и практических занятий. – СПб.: БХВ-Петербург, 2006.- 396 с.

7.     Яблонский С.В. Введение в дискретную математику. – М.: «Высшая школа», 2001

8.     Асеев Г.Г., Абрамов О.М., Ситников Д.Э. Дискретная математика: Учебное пособие.- Ростов н/Д: «Феникс»6 Харьков: «Торсинг», 2003.

     -144 с.

9.     Плотников А.Д. Дискретная математика. Учебное пособие.– 2-е изд., испр. и доп. – М.: Новое знание, 2006. – 304 с.

10.  Оре О. Графы и их применение: пер. с англ./ Под ред. и с предисл. И.М.Яглома. Изд. 3-е, стереотипное. –М.: КомКнига, 2006. – 168 с.

11. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для

    инженеров. – М.: Энергия,1980.

12. Данилов В.Г. и др., Дискретная математика. Учебное пособие для вузов.- М. 2008.- 136с.

13.  Палий И.А.Дискретная математика. Курс лекций.-М.:Эксмо, 2008.–352 с.

14.  Галушкина Ю.И., Марьямов А.Н. Конспект лекций по дискретной математике.- М.:  Айрис-пресс, 2007. – 176 с.

15. Астраханцева Л.Н. Дискретная математика. Конспект лекций.- Алматы: АИЭС, 2008. – 57 с.

16.  Гмурман В.Е. Руководство к решению задач по теории вероятностей и математической статистике. М. – Высш. шк., 1999. – 400 с.

 

 

 

 

 

 

 

Содержание

1 Элементы теории множеств                                                                           3

         1.1 Множества                                                                                          3

         1.2 Отношения                                                                                          7

         1.3 Понятие о мощности множеств                                                        16 

2 Элементы математической логики                                                                17

         2.1 Высказывания и логические операции                                            17

         2.2 Функции алгебры логики                                                                  21

         2.3 Дизъюнктивные и конъюнктивные нормальные формы               28

2.4 Булева алгебра и теория множеств. Коммутационные схемы      33

3 Элементы теории графов                                                                               36

         3.1 Основные понятия теории графов                                                   36

         3.2 Маршруты. Достижимость. Связность                                           44

         3.3 Эйлеровы и гамильтоновы графы                                                   48

         3.4 Расстояния в графах. Взвешенные графы                                      51

         3.5 Деревья. Лес. Минимальные остовные деревья                            59

         3.6 Раскраска графов. Планарность                                                      65

4 Элементы комбинаторики                                                                            68

         4.1 Правила суммы и произведения                                                     68

         4.2 Перестановки, размещения и сочетания                                        69

         4.3 Размещения, сочетания и перестановки с повторениями            71

         4.4 Разбиения                                                                                          73

         4.5 Понятие производящей функции                                                    73

 

Список литературы                                                                                          76