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

 

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

 

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

Конспект лекций

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

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

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

 

СОСТАВИТЕЛЬ: Л.Н. Астраханцева. Дискретная математика.

Конспект лекций для студентов всех форм обучения специальностей 050704 – Вычислительная техник и программное обеспечение,

050703 – Информационные системы.

          Лекции включают три раздела, традиционно изучаемые в курсе дискретной математики: элементы теории множеств и отношений, элементы математической логики и теории графов. Содержание разделов взаимно связано друг с другом. В доступной форме изложены основные теоретические сведения, приведены примеры и решённые задачи, помогающие усвоить и закрепить изучаемый материал. Конспект лекций предназначен для студентов всех форм обучения специальностей 050704 – вычислительная техника и программное обеспечение и 050703 – информационные системы.

 

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

          1.1 Лекция 1. Множества

          Содержание лекции: понятие множества, способы задания, операции над множествами; диаграммы Эйлера-Венна.        

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

 

Множество – совокупность некоторых объектов (элементов).

Обозначения: A, B, X,… - множества; a, b, x, x1, x2,… - элементы множеств;

- элемент а принадлежит А. - элемент b не принадлежит А. Конечные множества состоят из конечного числа элементов, бесконечные – из бесконечного числа элементов. Обозначения специальных множеств:

N – множество натуральных чисел (ω);

Z – множество целых чисел;

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

I - множество иррациональных чисел;

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

C – множество комплексных чисел;

Ø – пустое множество (не содержит ни одного элемента).

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

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

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

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

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=23  .

Обычно в конкретных рассуждениях элементы всех множеств берутся из одного достаточно широкого множества U, которое называется универсальным или универсумом.

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

Проиллюстрируем операции над множествами диаграммами

Эйлера - Венна, на которых множества обозначаются точками кругов внутри прямоугольника, точки которого – множество U- универсум.

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

рисунок 1.1.1.

 

 

 

 

 

                                                         Рисунок 1.1.1       

2 Пересечение (произведение, , ): АВ = {x| xА и xВ}; рисунок 1.1.2.

                                                       Рисунок 1.1.2         

3 Разность ( А \ В; А – В):  А \ В = {x| xА и xВ}; рисунок 1.1.3.

Рисунок 1.1.3        

4 Симметрическая разность (, , +): АВ=(А \ В)(В \ А) =

{x | (xА и xВ) или (xВ и xА)}; рисунок 1.1.4.

                                                        Рисунок 1.1.4        

5 Дополнение множества А ():={x | x и xА}= U \ A; рисунок 1.1.5.

 


                                                  

                                                                                

 

 

 

 Рисунок 1.1.5   

          Обобщение операций объединения и пересечения

A1 A2… An =

A1A2… An =

         

          Алгебра множеств

          Большинство свойств операций над множествами двойственны: если переставить местами Ø и U  или и , то из одного свойства можно получить двойственное.

          Пусть задан универсум U, тогда A, B, C U выполняются свойства:

Т а б л и ц а 1.1.1

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

           АА=А                                                         АА=А

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

          АВ= ВА                                                    АВ=ВА

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

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

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

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

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

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

     6 Свойство нуля

              АØ=А                                                             АØ= Ø

7 Свойство единицы

           АU=U                                                           АU= A

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

          =                                                     =

     9 Закон двойного отрицания (инволютивности)          =A

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

                  A=U                                                              A= Ø

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

1 а)

                АВ                                                          

                                                                                   

          в)                                                                                

                                           

                                                            

                                              

Рисунок 1.1.6

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

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

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

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

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

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

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

          а) АВ;

          б) АВ=А;

          в) АВ =В;

          г) А \ В = Ø;

          д) В =U.

          Установленные выше свойства позволяют упрощать сложные выражения, доказывать новые теоремы и т.д.

          Пример 1.1.2 - .

                  

 

          1.2 Лекция 2. Прямое произведение множеств. Отношения

          Содержание лекции: разбиения и покрытия множеств; прямое произведение множеств; унарные, бинарные, n-арные отношения; способы задания, основные свойства бинарных отношений.

          Цели лекции: ввести ещё одну операцию над множествами – прямое произведение; ввести понятие «отношения».

         

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

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

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

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

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

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

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

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

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

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

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

 

          Упорядоченные множества. Прямое произведение множеств

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

(x1,x2,…,xn) или <x1,x2,…,xn> и называть          кортеж длины n, упорядоченный набор из n элементов, вектор длины n,  n-ка (энка). xi – i-ая координата, компонента.

          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={(x1,x2,…,xn)| a1A1, a2A2 ,…, anAn}. Если A=B, то A×A=A2 ;   A×A×…×A=An ;  A1=A; A0={Ø}.

 

                                                                                   n 

          Пример 1.2.3 - 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;

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

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

         

          Отношения

          Определение. n-местным отношением P (n-местным предикатом) на множествах А1,А2,…,А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 | для некоторого y, (x,y)P}; областью значений (обозначается EP) называется EP ={y | для некоторого x, (x,y)P} (т.е. 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.5 -  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.6 -  A={2,3,4,5,6,7,8};

P={(x,y) | x,yA, y делится на x, x ≤3} = {(2,4),(2,6),(2,8),(2,2),(3,3),(3,6)}.

          Графическое задание Р:

Рисунок 1.2.1

         

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

     Определения. Пусть 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 – тождественное отношение на множестве А (иногда  обозначается

 idA). 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.2

          Пример 1.2.7 -  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.8  - P1={(x,x+2)|xZ+}, P2={(x,x2)|xZ+}, тогда

P1P2={(x,(x+2)2)| xZ+},  P2P1={(x,x2+2)| xZ+}.

          Теорема. Для любых бинарных отношений 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.9 -

, ,  тогда ;

; .

         

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

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

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

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

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

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

          д) транзитивным(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.10 -  А = {1,2,3}, P = {(1,2),(2,3),(3,2)}, [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.3 Лекция 3. Специальные виды бинарных отношений

          Содержание лекции: отношения эквивалентности, порядка, функциональные отношения.        

          Цели лекции: знакомство с бинарными отношениями, обладающими определённым набором свойств. 

         

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

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

          Примеры отношений эквивалентности: а) отношение равенства на любом множестве: 1)x=x; 2) x=y→y=x; 3) x=y; y=z → x=z; б) отношение подобия на множестве треугольников.

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

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

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

          Из определений ясно, что 1) любой элемент класса эквивалентности порождает класс эквивалентности, т.е. b[a]→[a]=[b]; 2) каждый класс эквивалентности содержит хотя бы один элемент, т.е. аА  [a]≠Ø; 3) никакой элемент множества А не может принадлежать двум различным классам: aEb[a]=[b].

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

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

          Пример 1.3.2 -  А={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.3.3 - 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,2,4},{3,5},{6}} является разбиением множества А, которое  соответствует данному отношению эквивалентности.

 

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

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

          Если к тому же оно 1) рефлексивно, то называется частичным или нестрогим порядком (≤); 2) антирефлексивно, то называется отношением строгого порядка (<). Если на множестве А задан порядок , то часто записывают (А, ) и называют множество А упорядоченным.

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

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

          Пример 1.3.4 - 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.3.5 -  (N; ≤) – в.у.м.; ([0;1]; ≤) – не является в.у.м., т.к., например, (0;1] [0;1], но (0;1]  не содержит  наименьшего элемента.

          Определение. Рассмотрим ч.у.м. (Х,≤). Говорят, что элемент у

покрывает элемент х, если х≤у и не существует такого элемента z (zx,zy), что хzy.

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

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

                                              

                              Рисунок 1.3.1                                   Рисунок 1.3.2

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

         

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

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

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

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

          Пример 1.3.8 -  F ={(1,2);(2,3),(3,2)} – функция, т.к. Df = Ef = {1,2,3}.

          Пример 1.3.9 -  P={(1,1),(1,2),(2,3)} – не функция, т.к. содержит пары (1,1) и (1,2) с одинаковыми первыми и разными вторыми элементами.

          Пример 1.3.10 - Отношение  - функция, т.к. из того, что  следует  .

          Пример 1.3.11 - P={(x2,x)|xR} – не функция, т.к. содержит пары с одинаковыми первыми и разными вторыми элементами:  (1,-1) P, (1;1) P.

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

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

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

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

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

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

         

 

 

 

 

 

          Отношение, но не функция                Инъекция, но не сюръекция

                 Рисунок 1.3.3                                     Рисунок 1.3.4

 

 

 

 

 

 


          Сюръекция, но не инъекция                       Биекция

                    Рисунок 1.3.5                                    Рисунок 1.3.6

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

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

          1  - инъекция, но не сюръекция, т.к.  Df = R, Ef R (рисунок 1.3.7).

                                   

Рисунок 1.3.7                                          Рисунок 1.3.8

 

          2  -  сюръективна, но не инъективна,  Ef  = R (рисунок 1.3.8).

          3  - биективна.

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

                          

         

         

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

          2.1 Лекция 4. Алгебра логики

          Содержание лекции: логика высказываний; логические операции;

 формулы и функции алгебры логики.

          Цели лекции: знакомство с основными понятиями и операциями

алгебры логики.

           

          Логика высказываний

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

               Пример 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

0

1

1

1

0

0

1

1

1

1

1

1

1

0

1

0

1

0

1

1

1

1

0

1

1

1

0

1

1

1

1

1

0

0

0

1

0

0

1

0

1

0

1

0

1

1

0

0

0

1

1

0

1

0

1

0

0

0

1

1

1

1

0

1

0

0

0

 

 

 

 

 

 

     

 

 

 

          Пример 2.1.3  - .

                                     Т а б л и ц а 2.1.3

у

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.4

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.4 -  а) в формуле  скобки следует расставить так: ; б) в формуле  скобки расставляются так: ; в) в формуле  скобки опустить нельзя, т.к. в силу наших соглашений выражению  соответствует формула .

 

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

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

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

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

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

 


    

 

 

                               Рисунок 2.1.2                                Рисунок 2.1.3

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

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

 

          2.2 Лекция 5. Логические функции

          Содержание лекции: способы задания логических функций; основные эквивалентные соотношения алгебры логики.

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

         

          Способы задания функций:

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

          б) задание функций перечислением всех наборов, на которых  принимает значение 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).

Итак, число всех наборов 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) в составленной таблице истинности два столбца, для   и для , были одинаковы. В этом случае возникает понятие эквивалентности формул.

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

          Пример 2.2.3 -  а) в примере 2.1.2 функции   и   эквивалентны, т.е. =;

б) построим таблицы истинности для формул :

      Т а б л и ц а 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

12а

13

13а

14

15

16

17

18

Заметим, что основные эквивалентные законы (таблица 2.2.4) не

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

          Определение. Формула  называется выполнимой (опровержимой), если существует такой набор значений переменных, при котором формула принимает значение 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.3 Лекция 6. Дизъюнктивные и конъюнктивные нормальные               формы

          Содержание лекции: полные системы логических функций; ДНФ и КНФ; СДНФ и СКНФ.

          Цели лекции: выяснение причин предпочтения базиса ; приведение к ДНФ и КНФ; приведение к СДНФ и СКНФ.

 

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

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

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

          Примерами функционально полных систем являются:

 и другие.

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

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

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

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

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

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

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

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

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

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

 

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

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

          Пример 2.3.2 - а)  и элементарные дизъюнкции; б)  и элементарные конъюнкции; в)одновременно является и элементарной дизъюнкцией и  элементарной конъюнкцией.

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

          Пример 2.3.3 -  а)ДНФ, б) КНФ.

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

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

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

            1) ;

            2) ;

            3) ;

            4) ;

            5) ;

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

;

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

          Пример 2.3.4 -   Привести к ДНФ формулу .

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

.

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

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

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

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

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

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

.

          Пример 2.3.5 -  Привести к КНФ формулу .

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

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

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

         

 

          СДНФ и СКНФ

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

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

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

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

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

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

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

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

Решение: 

- СДНФ.

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

          Пример 2.3.8 - Дана ДНФ функции . Найти СДНФ.

          Решение: построим таблицу истинности (таблица 2.3.1).

                            Т а б л и ц а 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

0

0

0

0

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

1

0

0

1

1

1

1

1

0

0

1

0

0

1

1

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

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

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

          а)

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

         

          2.4 Лекция 7. Минимизация булевых функций

          Содержание лекции: минимизация булевых функций в классе ДНФ; карты Карно; понятие двойственности.

          Цели лекции: выяснить смысл понятия минимизации; рассмотреть один из практических методов минимизации.

         

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

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

          Под вхождением переменной понимается место, которое переменная занимает в формуле.

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

         

          Карты Карно

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

          Карта Карно – это таблица, каждая клетка (ячейка) которой соответствует некоторой элементарной конъюнкции всех переменных. Для функции 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.4.1; б) для функции трёх переменных - на

рисунке 2.4.2; в) для функции четырёх переменных - на рисунке 2.4.3.

                                                                                    

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

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

          Пример 2.4.1 - Две функция   и   заданы в форме СДНФ. Для функции  карта Карно изображена на рисунке 2.4.4, для - на рисунке 2.4.5.                                                            

                                                                   

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

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

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

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

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

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

 

                      

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

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

          Пример 2.4.4 -

 - СДНФ. Карта Карно этой функции на рисунке 2.4.8.

 

 

 

 

 

 

 

 

 

 


Рисунок 2.4.8

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

 

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

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

называется самодвойственной, т.е. .

         Отношение двойственности симметрично, т.е., если ,то .     Пример 2.4.5 -

                    Т а б л и ц а 2.4.1  

1

0

0

1

 

 

 

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

а) для = имеем ;

б) для  , т.е. отрицание самодвойственное .

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

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

I способ: ;

II способ: построим таблицу истинности для (таблица 2.4.2), затем заменим в ней все значения на противоположные, получим таблицу для   (таблица 2.4.3). По таблицам видно, что эта функция самодвойственна .

    

 

 

 

 

 

Т а б л и ц а 2.4.2                                    Т а б л и ц а 2.4.3

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, то получим формулу , представляющую двойственную функцию. Таким образом, ДНФ соответствует КНФ, КНФ – ДНФ, СДНФ – СКНФ, СКНФ – СДНФ. Справедливо утверждение: если , то .

    

          2.5 Лекция 8. Изоморфизм булевых алгебр. Некоторые приложения математической логики

   Содержание лекции: булева алгебра и теория множеств; коммутационные схемы.

    Цели лекции: отметить важность изоморфизма булевых алгебр; указать примеры практического использования выше изложенного материала.

 

    Булева алгебра и теория множеств

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

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

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

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

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

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

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

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

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

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

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

 

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

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

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

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

                            

       

 

                                                            

                                              

 

 

 

                          Рисунок 2.5.1                            Рисунок 2.5.2                                          

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

                                                                                       

 


                                            

                                     

        

 

 

           Рисунок 2.5.3                     Рисунок 2.5.4             Рисунок 2.5.5

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

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

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

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

 

 

 


                                                                                                                                                                    

 

          Рисунок 2.5.6                   Рисунок 2.5.7                    Рисунок 2.5.8                            

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

        

 

 

 

 

         Пример 2.5.2 - Упростить схему  

Рисунок 2.5.9

          Решение: составим переключательную функцию

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

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

 

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

3.1 Лекция 9. Основные понятия теории графов

Содержание лекции: основные понятия и определения, способы задания графов; смежность, инцидентность, степени вершин.

Цели лекции: знакомство с основными понятиями теории графов.

 

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

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

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

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

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

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

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

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

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

   Для вершин орграфа определяются также две локальные степени. 

           Определение. Степенью выхода вершины  (обозначается  или  

ρ1(v)) называется число дуг с началом в вершине ; степенью входа вершины  (обозначается или ρ2(v)) - число дуг с концом в вершине ; ρ(v)=+. Если 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={а1,а2,а3} – множество вершин, 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. Задание графа списком рёбер (дуг). Кроме матрицы инцидентности, отношение инцидентности можно определить списком рёбер (дуг), задавая его в виде двух столбцов, в первом перечислены все рёбра (дуги), во втором -  инцидентные им вершины.

          Пример 3.1.4 - Для графа на рисунке 3.1.6 список дуг будет иметь вид:

                                                          Т а б л и ц а 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.2 Лекция 10. Изоморфизм графов. Операции над графами

         Содержание лекции: изоморфизм графов; подграфы и части графов; операции над графами; примеры различных видов графов.

         Цели лекции: выяснить, в чём заключается понятие изоморфизма для графов и как его установить; рассмотреть некоторые операции над графами и некоторые важные виды графов.

        

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

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

                                                                       

 

 

 

 


                                                      

 

                                                    Рисунок 3.2.1

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

          Определение. Два графа 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 , необходимо и достаточно существование какого-либо взаимно однозначного соответствия между вершинами графов, а также между их рёбрами.  Иногда в изоморфизме графов можно убедиться по их графическому представлению. Так, например, графы  и  на рисунке 3.2.2 изоморфны, т.к. достаточно поднять вершину 3 в графе  до уровня вершин 2 и 4  и перевернуть , и будет видно, что  и имеют одну форму.

                                  

                                                                                      

Рисунок 3.2.2

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

         

          Подграфы и части графов

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

       

         

        

         

 

Рисунок 3.2.3

 

         Операции над графами

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

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

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

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

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

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

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

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

                                                                    

 

 

 

 

 

 

 


               G1+ G2                                 G1G2                                     G1G2                                             

                                         Рисунок 3.2.5

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

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

 

 


                  

 

 

 

          К2                         К3                                  К4                                    К5

Рисунок 3.2.6

          Число рёбер полного графа вычисляется по формуле: m(Kn)=;

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

 

 

 

 

 

 

 

 


Рисунок 3.2.7

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

 

 


                                         

                                                   

                                                                                                           

 

 

 


                                                                                         

                                                                                         

Рисунок 3.2.8

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

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

 

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

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

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

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

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

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

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

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

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

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

                                

 

 

 

 

                                                     

                                                       Рисунок 3.2.9

          Решение: оба графа имеют по четыре вершины, т.е. 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.3 Лекция 11. Маршруты. Связность

          Содержание лекции: маршруты, цепи, пути, циклы, контуры; связность, компоненты связности; определение компонент связности; исследование маршрутов.

          Цели лекции: ввести новые понятия; определять компоненты связности; с помощью матрицы смежности определять длину и количество маршрутов.

         

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

          Введём ещё несколько новых понятий для н-графа и орграфа одновременно. Пусть G(V,E) граф. Последовательность v1,e1, v2,e2, ….., en,vn+1, где  v 1,v2, ...,vn+1V,  e1,e2, …,enE, называется маршрутом, соединяющим вершины 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.3.1 - Для н-графа G на рисунке 3.3.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,v1},  {v5,v6}, {v7}.

              

                         Рисунок 3.3.1                                   Рисунок 3.3.2

          Пример 3.3.2 - Для орграфа G2  на рисунке 3.3.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.3.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.3.2 матрица достижимости будет иметь вид:  С=. Если все элементы матрицы достижимости

н-графа сij=1, то граф связный. В общем случае матрица C н-графа является матрицей отношения эквивалентности, соответствующей разбиению множества вершин графа на компоненты. Например,  для графа G из примера 3.3.1 матрица связности будет: С=. Блоки, состоящие из единиц, соответствуют трём компонентам связности с множеством вершин {1,2,3,4},  {5,6}, {7}, т.е. разбиению множества вершин графа на эти компоненты.

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

    Рассмотрим, кроме матрицы С=(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.3.3 - Рассмотрим орграф G2  из примера 3.3.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= AA…A=(aij). Если aij=m, то из вершины vi в вершину vj существует m маршрутов длины k.

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

Рисунок 3.3.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.3.4 модифицированная матрица смежности  будет иметь вид: .   

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

 

          3.4 Лекция 12. Расстояния в графах. Задача о кратчайшем пути

          Содержание лекции: расстояния в графах; взвешенные графы; задача нахождения кратчайших путей.

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

 

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

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

Определение. Расстоянием между вершинами vi и vj (обозначается

d(vi, vj)) называется минимальная длина простой цепи с концами в vi и 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=.

Для взвешенных графов аналогично вводятся понятия расстояния, эксцентриситета и т.д.

 

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

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

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

Алгоритм Дейкстры 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}. Положим ТS+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

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

                                                                             

                  Рисунок 3.4.4                              Рисунок 3.4.5                                                  

Найти кратчайшее взвешенное расстояние и путь от вершины А до вершины F.

         1 шаг. Всем вершинам припишем метки , вершине А – источнику -  (0,0) и сделаем её постоянной и подчеркнём (рисунок 3.4.5).

2 шаг. Рассмотрим смежные с А вершины В и С, т.к. вес  больше их расстояний (весов) от А, то заменяем  на эти расстояния 5 и 6, а вторую координату заменяем на А, т.е. получаем В(5,А) и С(6,А).

3 шаг. Выбираем минимальный из весов, приписанных В и С, – это 5. Поэтому вершину В(5,А) делаем постоянной, подчёркиваем (рисунок 3.4.6).

       

                       Рисунок 3.4.6                                   Рисунок 3.4.7

          4 шаг. Как 2-ой шаг. Рассмотрим вершины, смежные с В(5,А), это C,D,E,F. Прибавим к их расстояниям от В вес вершины В: для С  - 5+3=8, т.к. 8>6, то оставляем С(6,А); для D - 5+7=12, т.к. 12< , то изменяем  D(12,B);

для E - 5+2=7, т.к. 7< , то изменяем E(7,B); для F - 5+10=15, т.к. 15< , то изменяем F(15,B).

         5 шаг. Как 3-ий шаг. Находим наименьшее из расстояний, присвоенных временным вершинам: min{6,12,7,15}=6, т.к. вершина С(6,А) имеет это расстояние, то делаем её постоянной, подчёркиваем (рисунок 3.4.7).

          6 и 7 шаги. Как 2-ой и 3-ий шаги. Смежной с вершиной С будет только одна временная вершина Е(7,В), прибавим к её весу вес С: 7+6=13>7, итак, оставляем для Е те же координаты, делаем её постоянной, подчёркиваем (рисунок 3.4.8).

                         

                     Рисунок 3.4.8                                         Рисунок 3.4.9

8 шаг. Смежной с Е временной вершиной будет F(15,B): 7+4=11<15, поэтому изменяем F(15,B) на  F(11,E), делаем постоянной, подчёркиваем (рисунок 3.4.9).

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

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

        

3.5 Лекция 13. Деревья. Лес. Минимальные остовые деревья

Содержание лекции: деревья, их свойства; остовые деревья; лес; минимальные остовые деревья.

Цели лекции: ввести новые понятия; отметить практическое значение нахождения остова минимального веса.

 

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

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

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

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

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

                                                  

                                               

 

 

                     а)                                          б)                                     в)

                                              Рисунок 3.5.1

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

          а) 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.29 вершины  v4, v3, v 5, v 6, 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},{E,F}};

д) , Е5={{B,D}, {E,D}, {A,E}, {E,F}, {F,G}};

е) ,  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} соединило два дерева).

 

Список литературы

 

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 с.

 

Содержание

 

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

Лекции 1-3

1.1 Множества

1.2 Алгебра множеств

1.3 Отношения

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

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

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

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

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

Лекции 4-7

2.1 Логика высказываний

2.2 Алгебра логики

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

алгебры логики

2.4 Булева алгебра логических функций. Полные системы

логических функций

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

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

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

2.8 Булева алгебра и теория множеств

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

 

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

Лекции 8-13

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

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

3.3 Операции над графами

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

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

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

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

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

Список литературы