shpory_diskra (Шпоры к экзамену по дискретке, вопросник внутри (лектор Иванов А.О., ИУ8))

Вопрос №1

Вопрос №2

Вопрос №3

Вопрос №4

Пусть J_n={1,2,…,n} – множество n первых натуральных чисел. Назовем конечным множество, эквивалентное одному из J_n (пустое множество также считается конечным). Множество называется счетным, если оно эквивалентно множеству натуральных чисел. Бесконечное множество, не являющееся счетным, называется несчетным. Не более чем счетным называется множество, которое либо конечно, либо счетно. Два множества A и B считаются равными, если любой элемент x из множества A (xA) является множеством элемента B (xB) и наоборот. A=B(x)(xAxB). Объединением двух множеств X и Y называется множество XY, состоящее из элементов, принадлежащих хотя бы одному из множеств X или Y. Пересечением двух множеств X и Y называется множество XY, состоящее из элементов, принадлежащих каждому из множеств X и Y. Разностью множеств X и Y называется подмножество X\Y множества X, состоящее из всех его элементов, не содержащихся в Y. Симметрической разностью множеств X и Y называется множество X∆Y=(X\Y)(Y\X). Пусть выбрано некоторое «универсальное » множество U, такое, что все рассматриваемые множества являются его подмножествами. Дополнением к множеству X называется множество X=U\X. Свойства операций над множествами:

1. (XY)Z=X(YZ) 2. (XY)Z=X(YZ) (свойство ассоциативности) 3. XY=YX 4. XY=YX (свойство коммутативности) 5. (XY)Z=(XZ)(YZ) 6. (XY)Z=(XZ)(YZ) (свойство взаимной дистрибутивности) 7. XX=X 8. XX=X (свойство идемпотентности) 9. XY=XY 10. XY=XY (законы де Моргана) 11. X(XY)=X 12. X(XY)=X (законы поглощения).

Пусть X и Y – множества. Отображением f:XY из множества X в множество Y называется правило f, сопоставляющее каждому элементу xX однозначно определенный элемент f(x)Y. Множество X называется областью определения. Элемент f(x) называется образом элемента x при отображении f. Отображение f:XY называется сюръективным, если f(X)=Y, т.е., если у каждого элемента из Y есть прообраз. Это отображение называется инъективным, если из f(x)=f(x^|) следует x=x^|, т.е., если каждый элемент из области его значений имеет единственный прообраз. Отображение называется биективным (или взаимно однозначным соответствием), если оно одновременно и сюръективно, и инъективно. Характеристической функцией множества XU называется функция, определенная следующим образом: _A(x)={^{1,если xA,} _{0, если xA.} Функции _A(x) и _B(x) совпадают только тогда, когда A=B. Свойства характеристической функции: 1. _A(x)=1-_A(x) 2. _AB(x)= _A(x) _B(x)

3. _AB(x)= _A(x)+ _B(x)- _A(x) _B(x) 4. _A\B(x)= _A(x) - _A(x) _B(x) 5. _{A ∆ B}(x) = _A(x)+ _B(x)-

-2_A(x) _B(x)

Пусть X и Y – множества. Отображением f:XY из множества X в множество Y называется правило f, сопоставляющее каждому элементу xX однозначно определенный элемент f(x)Y. Множество X называется областью определения. Элемент f(x) называется образом элемента x при отображении f. Отображение f:XY называется сюръективным, если f(X)=Y, т.е., если у каждого элемента из Y есть прообраз. Это отображение называется инъективным, если из f(x)=f(x^|) следует x=x^|, т.е., если каждый элемент из области его значений имеет единственный прообраз. Отображение называется биективным (или взаимно однозначным соответствием), если оно одновременно и сюръективно, и инъективно. Пусть f:XY и g:YX – отображения. Отображение g называется обратным к f (а f – обратным к g), если fg=id_X и gf= id_Y. Если обратное отображение существует, то оно единственно. Теорема. Отображение обладает обратным тогда и только тогда, когда оно биективно. Достаточность. Пусть f:XY – биективное отображение. Определим отображение g:YX, полагая g(y)=x, если f(x)=y. Вследствие биективности f отображение g корректно определено, и ясно, что g=f^-1. Необходимость. Пусть f:XY и g:XY – взаимно обратные отображения. Пусть yY и g(y)=x. Тогда f(x)=f(g(y))=y, т.е. f сюръективно. Инъективность f также легко проверить: если x,x^|X, причем f(x)=f(x^|), то g(f(x))=g(f(x^|)), откуда e_X(x)=e_X(x^|), т.е. x=x^|. Теорема доказана.

Пусть f:XY и g:YZ – отображения. Суперпозицией называется отображение gf:XZ, определенное следующим образом: (gf)(x)=g(f(x)) (xX). Суперпозиция определена не для любых пар отображений. Но суперпозиция двух преобразований одного и того же множества всегда определена. Отображение, обратное к суперпозиции: (fg)^-1=f^-1g^-1

Ассоциативность суперпозиции отображений.

Если f : X → Z , g : Z → Y , h : Y → V , то h o (g o f ) = (h o g ) o f .

Доказательство.

для любого x ∈ X:

(h o (g o f ))(x ) = h((g o f )(x )) = h(g ( f (x ))) = (h o g ) ( f (x )) = ((h o g ) o f )(x ) .

Бинарным отношением на мн-ве X называется произвольное подмн-во RX². Бин. отн. R наз. рефлексивным, если xRx для всех x. Бин. отн. R называется симметричным, если xRy тогда и только тогда, когда yRx. Бин. отношение называется транзитивным, если из xRy и yRz следует xRz. Бин. отн. R называется антисимметричным, если из xRy и yRx следует x=y. Бин. отн. называется отношение эквивалентности, если оно рефл., симм. и транз. Пусть в множестве X введено отношение эквивалентности. Подмножество [x]={yX|y~x}, состоящее из всех элементов, эквивалентных данному, называется классом эквивалентности, содержащим x. Теорема. Множество классов эквивалентности по отношению эквивалентности на множестве X есть разбиение этого множества. Обратно, если задано разбиение множества X на попарно непересекающиеся подмножества, то эти подмножества будут классами эквивалентности по некоторому отношению эквивалентности на X. Так как x[x], то X есть объединение классов [x] (xX). Покажем, что любые два класса либо не пересекаются, либо совпадают. Пусть [x][y]0, z[x][y]. Это значит, что z~x и z~y. Ввиду транз. отношения эквивалентности имеем x~y. Пусть теперь t – произвольный элемент из [x]. Это значит, что t~x. Поэтому t~y и t[y], откуда [x][y]. Аналогично доказ. и включение [y][x]. Следов., [x]=[y]. Обратно, пусть подмножества C_(A) образуют разбиение на множества X. Положим x~y тогда и только тогда, когда x и y лежат в одном и том же подмножестве C_. Полученное отношение рефл., симм. и транз., т.е. является отношением эквивалентности. Ясно, что подмножества C_(A) совпадают с классами эквивалентности по этому отношению. Отношением предпорядка назыв. бинарное отнош., кот. рефл. и транз. Если это отношение антисимм., то оно назыв. отношением порядка.

Вопрос №5

Вопрос №6

Вопрос №7

Вопрос №8

Бинарным отношением на мн-ве X называется произвольное подмн-во RX². Бин. отн. R наз. рефлексивным, если xRx для всех x. Бин. отн. R называется симметричным, если xRy тогда и только тогда, когда yRx. Бин. отношение называется транзитивным, если из xRy и yRz следует xRz. Бин. отн. R называется антисимметричным, если из xRy и yRx следует x=y. Бин. отн. называется отношение эквивалентности, если оно рефл., симм. и транз. Если это отношение антисимметрично, то оно называется отношением порядка. Пусть X упорядоченное множество. Элемент x называется наибольшим, если yx для всех yX. Если наибольший элемент существует, то он единствен. Не в каждом упорядоченном множестве существует наибольший элемент. Элемент aX называется максимальным, если из ax следует x=a. Аналогично определяется наименьший и минимальные элементы. Пусть <A,> - упорядоченное множество, и BA. Элемент aA называется верхней (соответственно, нижней) гранью множества B, если (xB) (xa) (соответственно, (xB) (xa) ). Наименьший элемент множества всех верхних граней (соответственно, наибольший элемент множества всех нижних граней) множества B называют точной верхней гранью B (соответственно, точной нижней гранью B) и обозначают supB (infB).

Множества A и B называют равномощными, если между ними может быть установлено взаимно однозначное соответствие, т.е. существует биекция одного из них на другое. Если мы обозначим через |A| класс эквивалентности множества A по отношению ~, то утверждение о равномощности множеств A и B можно записать так: |A|=|B|. Тогда договоримся сам класс эквивалентности |A| называть мощностью множества A. Множество называется счетным, если оно эквивалентно множеству натуральных чисел.

Свойства счетных множеств:

1. Любое бесконечное множество содержит счетное подмножество.

2. Любое бесконечное множество содержит два не пересекающихся между собой счетных подмножества.

3. Любое подмножество счетного множества конечно или счетно. Если множество конечно или счетно, его называют не более чем счетным.

4. Объединение любого не более чем счетного семейства счетных множеств счетно.

5. Если M – счетное множество, а K – его конечное подмножество, то M\K – счетно.

6. Если M – бесконечное множество, а N – его не более, чем счетное подмножество, причем множество M\N – бесконечно, то M\N~M.

7. Если M – бесконечное множество, а N – не более, чем счетное множество, то M~MN.

8. Множество 2^N всех подмножеств множества натуральных чисел не есть счетное множество.

9. Декартово произведение конечного числа счетных множеств счетно
Беск несчет мн-во – множество всех чисел из отрезка [0;1)

Множества A и B называют равномощными, если между ними может быть установлено взаимно однозначное соответствие, т.е. существует биекция одного из них на другое. Если мы обозначим через |A| класс эквивалентности множества A по отношению ~, то утверждение о равномощности множеств A и B можно записать так: |A|=|B|. Тогда договоримся сам класс эквивалентности |A| называть мощностью множества A. Теорема. Множество всех отображений множества X на множество Y более мощно, чем множество X. Доказательство от противного. F(X,Y)X. f_x(t)={^{y0, xt}_{y1, x=t.} {f_x}~X. Пусть есть биекция F(x,y)X:Ф. g:XY g(x)=yФ_x(x) (Ф_x(x)=y). Мы получили противоречие.

Группоидом называют любую алгебру, сигнатура кото­рой состоит из одной бинарной операции. Группоид, операция которого ассоциативна, называют полугруп­пой. Полугруппу G=<G,> называют моноидом, если в ней существует единица (нейтральный элемент) по опе­рации. Моноид G=<G,>, называют группой, если в нем для каждого элемента существует обратный по опера­ции , т.е. для каждого xG существует такой элемент x^|G, называемый обратным к x, что xx^|=x^|x=, где  - единица моноида G. Если операция коммутативна, по­лугруппа называется коммутативной. Группой назы­вается полугруппа с единицей, в которой каждый эле­мент обратим. Группу H=<H,,^-1,1> называют подгруп­пой группы G=<G,,^-1,1>, если H есть подмножество G, замкнутое относительно операции , содержащее еди­ницу 1 группы G и вместе с каждым элементом xH со­держащее элемент x^-1, обратный к x. Множество всех биекций некоторого множества A на себя с операцией композиции есть группа. Это следует из того, что отно­шение, обратное биекции, есть биекция, а также из того, что для всякой биекции f:AA имеет место равенство ff^-1=f^-1f=id_A. id_A (диагональ) – нейтральный элемент по операции композиции. Эту группу называют симметри­ческой группой множества A, а в том случае, когда мно­жество A конечно – группой подстановок множества A. Теорема Кели. G~HS_|G|. Любая конечная группа изо­морфна некоторой группе H, принадлежащей группе пе­рестановок на G. G~HS_|G|.

Вопрос №9

Вопрос №10

Вопрос №11

Вопрос №12

Группоидом называют любую алгебру, сигнатура которой состоит из одной бинарной операции. Группоид, операция ко­торого ассоциативна, называют полугруппой. Полугруппу G=<G,> называют моноидом, если в ней существует еди­ница (нейтральный элемент) по операции. Моноид G=<G,>, называют группой, если в нем для каждого элемента сущест­вует обратный по операции , т.е. для каждого xG сущест­вует такой элемент x^|G, называемый обратным к x, что xx^|=x^|x=, где  - единица моноида G. Если операция коммутативна, полугруппа называется коммутативной. Группой называется полугруппа с единицей, в которой каждый элемент обратим. Группу H=<H,,^-1,1> называют подгруппой группы G=<G,,^-1,1>, если H есть подмножество G, замкнутое относительно операции , содержащее единицу 1 группы G и вместе с каждым элементом xH содержащее элемент x^-1, обратный к x. Теорема Лагранжа. Пусть G=<G,,1> - группа, а H=<H,,1>. Левым смежным классом подгруппы H по элементу aG называют множество aH={y|y=ah, hH}. Порядок конечной группы делится на порядок любой ее подгруппы. Для доказательства этого докажем сначала теорему: все левые классы смежности подгруппы H равномощны и их мощность равна мощности H. Для произвольного фиксированного aG зададим отображение _a:HaH следующим образом: _a(h)=ah. Отображение _a есть, во-первых, сюръекция, ибо xaH x=ah для некоторого hH; во-вторых, _a – инъекция, ибо из ah₁=ah₂ следует h₁=h₂ – в силу законов сокращения в каждой группе. Следовательно _a – биекция, и |aH|=|H|. В силу доказанного все левые классы смежности образуют разбиение множества на k равномощных подмножеств. Следовательно, |G|=k|H|, где k – число всех левых классов смежности подгруппы H, называемое левым индексом подгруппы H в группе G.

Кольцом (ассоциативным) называется алгебра с двумя операциями – сложением (+) и умножением (), удовлетворяющими следующим условиям: 1. <X,+> - коммутативная группа 2. <X,> - полугруппа 3. (дистрибутивность) Для любых x, y,zX имеют место неравенства (x+y)z=xz+yz, z(x+y)=zx+zy. Если существует нейтральный элемент для умножения, I, то кольцо называют кольцом с единицей. Если умножение коммутативно, то кольцо называется коммутативным. Коммутативное кольцо с I0, в котором каждый ненулевой элемент обладает обратным относительно умножения, называется полем. Кольцо <X,+,> называется булевым, если оно имеет единицу и для всех элементов xX справедливо равенство x²=x. Делители нуля – ненулевые элементы, произведение которых равно 0. Областью целостности называют коммутативное кольцо без делителей нуля. Например, кольцо целых чисел есть область целостности. Конечная область целостности является полем. Примеры конечных полей: Z_P – класс вычетов по модулю простого числа.

Полукольцо — это алгебра с двумя бинарными и двумя нульарными операциями S=(S,+,⋅,0,1), такая, что для произвольных элементов a,b,c множества S выполняются следующие равенства, называемые аксиомами полукольца:

)a+(b+c)=(a+b)+c;

)a+b=b+a;

)a+0=a;

)a⋅(b⋅c)=(a⋅b)⋅c;

)a⋅1=1⋅a=a;

)a⋅(b+c)=a⋅b+a⋅c;

)(b+c)⋅a=b⋅a+c⋅a;

)a⋅0=0⋅a=0.

Первую операцию + называют сложением полукольца, а вторую операцию ⋅

- умножением полукольца S; элементы 0 и 1 называют соответственно нулем и единицей полукольца S.

Идемпотентное полукольцо - полукольцо с идемотентной операцией сложения.

Отношение ⩽ на носителе произвольного идемпотентного полукольца есть отношение порядка. Будем называть его естественным порядком идемпотентного полукольца и говорить, что он задан в этом полукольце.

Если A — конечное подмножество (носителя) идемпотентного полукольца, то supA относительно естественного порядка этого полукольца равен сумме всех элементов множества A.

Пусть A={a1,…,an} и a=a1+…+an. Для произвольного элемента ai, i=1..n, в силу коммутативности и идемпотентности сложения имеем

ai+a=ai+(a1+…+ai+…+an)==a1+…+ai+ai+…+an==a1+…+ai+…+an,

то есть ai⩽a, и поэтому a есть верхняя грань множества A. Покажем, что это точная верхняя грань множества. Возьмем произвольную верхнюю грань b множества A и рассмотрим сумму b+a. Так как для каждого i=1..n имеет место ai⩽b, то есть ai+b=b, то b+a=b+(a1+a2+…+an)=(b+a1)+(a2+…+an)==b+a2+…+an=b.

Следовательно, a⩽b поэтому a — точная верхняя грань множества A.

Упорядоченное множество (M,⩽) называют индуктивным, если:

1) оно содержит наименьший элемент;

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

Пусть (M1,⩽) и (M2,≼) — индуктивные упорядоченные множества. Отображение f:M1→M2 одного индуктивного упорядоченного множества в другое называют непрерывным, если для любой неубывающей последовательности a1,…,an,… элементов множества M1 образ ее точной верхней грани равен точной верхней грани последовательности образов f(a1),…,f(an),…, т.е. справедливо равенство f(supa_n)=sup f(a_n).

Отображение f:M1→M2 упорядоченных множеств (M1,⩽) и (M2,≼) называют монотонным, если для любых a,b∈M1 из a⩽b следует f(a)≼f(b).

Всякое непрерывное отображение одного индуктивного упорядоченного множества в другое монотонно.

Пусть f — непрерывное отображение индуктивного упорядоченного множества (M1,⩽) в индуктивное упорядоченное множество (M2,≼). Пусть a,b∈M1 и a⩽b. Образуем последовательность {xi}n∈ℕ, где x1=a, а xn=b, n⩾2. Эта последовательность неубывающая. Для нее supxn=sup{a,b}=b. В силу непрерывности отображения f

f(b)=f(supxn)=f(sup{a,b})=sup{f(a),f(b)}.

Откуда следует, что f(a)≼f(b).

Вопрос №13

Вопрос №14

Вопрос №15

Вопрос №16

Упорядоченное множество (M,⩽) называют индуктивным, если:

1) оно содержит наименьший элемент;

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

Т. Любое непрерывное отображение f индуктивного упорядоченного множества (M,⩽) в себя имеет наименьшую неподвижную точку.

Обозначим через наим эл-т мн-ва M. Полагаем f0(x)=x и fn(x)=f(fn−1(x)) для любого n>0, т.е. fn(x) означает результат n-кратного применения f к x. Рассмотрим последовательность эл-тов M

{fn()}n⩾0={,f(),…,fn(),…}. (1.7)

Докажем, что посл-ть (1.7) неубыв. Используем метод мат индукции. Для эл-та , как наим эл-та мн-ва M, имеем −f0()⩽f(). Пусть для нек натурального n верно соотн-е fn−1()⩽fn(). Согласно теореме о связи монотонности и непрерывности, отображение f монотонно, и поэтому

fn()=f(fn−1())⩽f(fn())=fn+1(),

т.е. соотн-ие верно и для номера n+1. Согласно методу мат индукции, fn()⩽fn+1() для любого n∈ℕ0, т.е. посл-сть (1.7) неубывающая. Следовательно, по опрединдуктивного упорядоченного мн-ва, она имеет точн верхнюю грань. Обозначим ее через a:

a=supn⩾0fn(). (1.8)

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

Действительно, если а есть точная верхняя грань неубывающей последовательности {xn}n⩾0, то a⩾xn для всякого n⩾0. В частности, фиксируя произвольно k>0, для любого n⩾k имеем a⩾xn, т.е. а будет верхней гранью подпоследовательности {xn}n⩾k>0.

Докажем, что а является точной верхней гранью этой подпоследовательности. Пусть b — какая-то ее верхняя грань, т.е. b⩾xn для любого n⩾k. Так как последовательность {xn}n⩾0 неубывающая, то xp⩽xk для каждого p=0..k−1. Поскольку xk⩽b, то в силу транзитивности отношения порядка xp⩽b и тем самым b⩾xn для любого n⩾0, т.е. b есть верхняя грань всей последовательности {xn}n⩾0. Поскольку a=supn⩾0xn., то a⩽b и a=supn⩾k>0xn.. Следовательно, a — точная верхняя грань последовательности {xn}n⩾k.

В силу непрерывности f получаем

f(a)=f(supn⩾0fn())=supn⩾0f(fn())=supn⩾0fn+1().

Но

supn⩾0fn+1()=sup{f1(),f2(),…}=supn⩾1fn()=a.

Таким образом, доказано, что a является неподвижной точкой отображения f.

Покажем теперь, что найденная неподвижная точка является наименьшей. Пусть для некоторого y∈M имеем f(y)=y. Так как ⩽y, а отображение f, будучи непрерывным, монотонно, то

f()⩽f(y)=y,f(f())⩽f(f(y))=y и т.д.

Следовательно, для любого n⩾0 имеем fn()⩽y, т.е. элемент y есть верхняя грань последовательности {fn()}n⩾0. Поскольку элемент a (как точная верхняя грань) есть наименьший элемент на множестве всех верхних граней этой последовательности, то y⩾a. Таким образом, мы доказали, что произвольная неподвижная точка отображения f не меньше элемента a, то есть a— наименьшая неподвижная точка отображения f.

Полукольцо S=(S,+,⋅,0,1) называют замкнутым, если:

1) оно идемпотейтно;

2) любая последовательность элементов множества S имеет точную верхнюю грань относительно естественного порядка ⩽ этого идемпотентного полукольца;

3) операция умножения полукольца S сохраняет точные верхние грани последовательностей, т.е. для любого a∈S и любой последовательности X={xn}n∈ℕ элементов множества S имеем

asupX=supaX, (supX)a=sup(Xa).

Наименьшими решениями уравнений x = ax+b и x = xa+b в замкнутых полукольцах являются соответственно

x=a∗⋅b (1)

и

x=b⋅a∗,(2)

где a∗ — итерация элемента a,

Док-во

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

x=∑_n=0^∞fⁿ(0),

где 0 — нуль полукольца, а f(x)=ax+b. Учитывая, что

f⁰(0)=0, f¹(0)=b, f²(0)=ab+b=(a+1)b, …, fⁿ(0)=(aⁿ−1+…+a²+a+1)b,

получаем

∑_n=1^∞fⁿ(0)=∑_n=1^∞(1+a+…+aⁿ⁻¹)b.

Используя непрерывность умножения, вынесем b (вправо) за знак бесконечной суммы и получим

∑_n=1^∞(1+a+…+aⁿ⁻¹)b=(∑_n=1^∞(1+a+…+aⁿ⁻¹))b.

Сумма 1+a+…+aⁿ⁻¹ есть частичная сумма последовательности {aⁿ}_n⩾0.

Следовательно:
∑_n=1^∞(1+a+…+aⁿ⁻¹)=∑_n=0^∞aⁿ=a∗.

Окончательно получаем ∑_n=1^∞fⁿ(0)=a∗b.

Аналогично доказывается равенство (2).

Булева функция (от n переменных) — это произвольное отображение вида

f:{0;1}ⁿ→{0;1},

т.е. булева функция определена на множестве всех n-элементных (при n⩾0) последовательностей (или n-компонентных кортежей) нулей и единиц и принимает два возможных значения: 0 и 1.

Из определения булевой функции f(x₁,x₂,…,x_n) следует, что для ее задания достаточно узнать, какое значение функции соответствует каждому из наборов значений аргументов (булеву вектору – табл.).

Функция f(x₁,…,x_i-1,x_i,x_i+1,…,x_n) из P₂ зависит существенным образом от аргумента x_i, если существуют такие значения ₁,… _i-1, _i, _i+1,… _n, переменных x₁,…,x_i-1,x_i,x_i+1,…,x_n, что

f(₁,… _i-1,0, _i+1,… _n)f(₁,…_i-1,1, _i+1,… _n). В этом случае переменная x_i называется существенной. Переменная, не являющаяся существенной, называется несущественной, или фиктивной. Функции f и g называются равными, если функцию f можно получить из g добавлением или изъятием фиктивных аргументов.

ДНФ от переменных x₁,…,x_n – это формула вида K₁…K_m, где K_i –элементарная конъюнкция, содержащая некоторые из литералов из x₁,…,x_n. Когда в каждую конъюнкцию K_i входит в точности один из литералов x_j (x_j ), ДНФ называется СДНФ.

Булева функция (от n переменных) — это произвольное отображение вида

f:{0;1}ⁿ→{0;1},

т.е. булева функция определена на множестве всех n-элементных (при n⩾0) последовательностей (или n-компонентных кортежей) нулей и единиц и принимает два возможных значения: 0 и 1.

Теорема о разложении б.ф. Для б.ф. справедливо равенство: f(x₁,x₂,…,x_n)=x^1₁ x^2₂…x^m_m f(₁,…,_m,x_m+1,…x_n), где дизъюнкция производится по всем возможным наборам (₁,…,_m) Доказательство.

Для  набора (₁,…, _n) правая часть дает f(₁,…, _n), а левая-^1₁ …^m_m f(₁,…,_m, _m+1,… _n)= ^1₁ …^m_m f(₁,…  _n)=f(₁,…  _n)

Введем понятие функции, представляемой формулой над множеством F. Мы полагаем, что:

1) любая константа из F представляет саму себя;

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

3) если формулы Φ1,…,Φn над множеством F

представляют соответственно функции g1,…,gn, a f — функция из F от n переменных (n⩾1), то формула f(Φ1,…,Φn) представляет суперпозицию функций f(g1,…,gn);

4) других булевых функций, представляемых формулами над множеством F, кроме тех, которые могут быть получены согласно пунктам 1-3 данного определения, не существует.

Дизъюнктивная нормальная форма (ДНФ) от переменных x1,…,xn — это формула вида K1∨…∨Km, где Ki, i=1..m, — элементарная конъюнкция, содержащая некоторые из литералов x1,…,xn. В том случае, когда в каждую конъюнкцию Ki для каждого номера j=1..n входит в точности один из литералов x˜j, ДНФ называется совершенной дизъюнктивной нормальной формой (СДНФ).

Вопрос №17

Вопрос №18

Вопрос №19

Вопрос №20

Пусть f(x₁,x₂,…,x_n) – булева функция. Функция f * (x₁,x₂,…,x_n ) называется двойственной f(x₁,x₂,…,x_n), если f * (x₁,x₂,…,x_n ) = f(x₁,x₂,…,x_n).

Принцип двойственности: Функция, двойственная суперпозиции функций, равна суперпозиции двойственных функций.

Пусть Ф= f₁(x₁,…,x_i-1, f₂(x₁,…,x_m),x_i+1,…,x_n), тогда Ф*= f*₁(x₁,…,x_i-1, f*₂(x₁,…,x_m),x_i+1,…,x_n)

Доказательство: расписать Ф*, учитывая, что Ф(x₁, …,x_n )= f₁(x₁,…, x_i-1,  f₂(x₁,…, x_m), x_i+1,…, x_n)

Функция называется самодвойственной, если f (x₁,x₂,…,x_n )= f * (x₁,x₂,…,x_n ).

Скнф как в 16 вопросе сднф

Полиномом Жегалкина называется выражение вида:  _i1…is x_i1,…x_is (_i1…is B), где суммирование производится по различным наборам 1<1<…<i_s, и среди слагаемых имеется константа ₀ B, отвечающая пустому множеству.

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

Теорема: всякую функцию можно реализовать единственным полиномом Жегалкина, т.е. ПЖ однозначно определяет БФ.

Доказательство: Поскольку число наборов переменных х1, х2, …, хn совпадает с числом подмножеств множества { х1, х2, …, хn} и равно 2ⁿ и каждый коэффициент полинома Жегалкина равен 0 или 1, то число полиномов от переменных совпадает с числом характеристических функций на множестве указанных наборов. Т. образом число полиномов в точности равно числу булевых функций от n переменных. Поскольку каждая функция реализуется полиномом (т.к. через полином могут быть получены функции стандартного базиса, через который реализуется любая б.ф. что легко показать), теорема доказана.

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

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

• Правило обобщенного склеивания: х К₁х К₂= хК₁ х К₂  К₁ К₂

• Правило поглощения: К₁  К₁ К₂ = К₁

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

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

С геометрической точки зрения карта Карно есть способ изображения булева куба (размерностей 3 и 4). Любая пара соседних клеток (с учетом "закрученности" карты) определяет некоторое ребро булева куба, а любой прямоугольник, состоящий из 2k клеток (или, как говорят, прямоугольник с площадью 2k) для некоторого k, определяет грань размерности k.

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

Любую ДНФ, эквивалентную исходной СДНФ, содержащую все ядровые импликанты и не содержащую ни одной избыточной импликанты, называют тупиковой.

ДНФ называют минимальной, если она содержит наименьшее число литералов среди всех ДНФ, эквивалентных ей.

Алгоритм Квайна-Мак-Клоски. 1. Операция склейки: Пусть К1 и К2 – две элементарные конъюнкции, входящие в исходную СДНФ, причем К₁=хК , К₂=хК, где К – некоторая элементарная конъюнкция. Тогда К₁К₂=хК(хК)=(хх)К=К. Процесс склейки можно выполнить, используя карты Карно, которая является одной из форм таблицы истинности. Процесс склейки выглядит так: на карте Карно 2, 4 или 8 соседних единиц обводятся прямоугольником, который обозначает склейку. Поучаем сокр. ДНФ. 2. Определение ядра. Простую импликанту называют ядровой, если она покрывает некоторую импликату исходной СДНФ, не покрываемую никакими другими импликатами. 3. Перечисление тупиковых ДНФ. ДНФ называется тупиковой, если удаление любой простой импликанты нарушает эквивалентность этой ДНФ исходной (т.е. ДНФ содержит все ядровые импликанты и не содержит ни одной избыточной). Получить ТДНФ можно, используя КНФ функцию Патрика К1… Kn. Раскрывая скобки в КНФ и применяя правило поглощения, получим ДНФ, элементарные конъюнкци которой определяют ТДНФ. 4. Отыскания среди ТДНФ минимальных ДНФ. Операцию получения сокр. ДНФ можно провести по алгоритму Блейка. Он состоит в том, что к любой ДНФ, представляющей функцию применяются следующие тождества: правило обобщенного склеивания: х К₁х К₂= хК₁ х К₂  К₁ К₂ правило поглощения: К₁  К₁ К₂ = К₁ Сам алгоритм следующий: сначала к ДНФ применяют правило обобщенного склеивания до тех пор, пока не перестанут появляться новые элементарные конъюнкции, а затем, применяют правило поглощения. В результате получаем сокращенную ДНФ.

Вопрос №21

Вопрос №22

Вопрос №23

Вопрос №24

Пусть F – некоторое множество булевых функций. Замыканием [F] множества F называется совокупность всех функций из P, реализуемых формулами над F.

Множество F булевых функций называется функционально замкнутым классом, если [F]=F.

T0 – класс всех функций, сохраняющих константу 0, т.е. f(0,0,…,0)=0;

T1 – класс всех функций, сохраняющих константу 1, т.е. f(1,1,…,1)=1;

S – класс всех самодвойственных функций, т.е. f (x₁,x₂,…,x_n ) = f (x₁,x₂,…,x_n). Например, x иx.

Лемма о несамодвойственной функции: если f(х₁,…,х_n), то, подставляя на места ее переменных х иx, можно получить константу.

Доказательство: т.к. fS, то найдется набор (₁, ₂,…, _n) такой, что f(₁, ₂,…, _n)= f(₁, ₂,…, _n).

Положим _i (х)=х^i , i = 1,…,n, и (х)=f(₁ (х),… _n (х)). Т.е имеем: (0)= f(0^i,…, 0^i) = f(₁, ₂,…, _n) = f(₁, ₂,…, _n)= f(1^i,…, 1^i)= (1). Следовательно (х) – константа. Лемма доказана.

Нужно для каждого класса Поста C∈{T0,T1,S,M,L} доказать, что замыкание [C] множества булевых функций C совпадает с C. Пусть f(g1,…,gn) — какая-то суперпозиция над C. Обозначим ее через φ. Без ограничения общности можно считать, что все функции f,g1,…,gn∈P2,n (для некоторого n).

Рассуждаем, используя индукцию по определению суперпозиции. Если для каждого i=1..n функция gi=xi, где xi — переменное, то φ=f(x1,…,xn)∈C. Предположим, что в суперпозиции φ все функции gi есть элементы класса Поста C (в частности, это может быть и соответствующая проектирующая функция, которая ввиду замечания 6.9 принадлежит всем классам Поста). Докажем, что и φ=f(g1,…,gn)∈C.

1. Если C=T0, то φ(0˜)=f(g1(0˜),…,g2(0˜))=f(0,…,0)=0, так как f,g1,…,gn∈T0. Следовательно, φ∈T0.

2. При C=T1 рассуждаем точно так же.

3. Пусть C=S. Фиксируем произвольно набор α˜∈{0;1}n. Вычислим (используя самодвойственность всех функций):

Следовательно, φ∈S.

Пусть F – некоторое множество булевых функций. Замыканием [F] множества F называется совокупность всех функций из P, реализуемых формулами над F. Множество F булевых функций называется функционально замкнутым классом, если [F]=F. Функция называется монотонной, если для любых двух наборов  и  f(А₁,А₂,…,А_n)  f(В₁,В₂,…,В_n), при А В (А  В если А₁  В₁, …, А_n  В_n ). Пример: f = 0; f = 1; f = х; f = х₁х_2ъ. Класс монотонных функций обозначается через M. К классу лин. ф-ций L относят ф-ции, реализ. полиномом Жегалкина вида: ₀  ₁х₁  … _nх_n (_iB). Лемма о немонотонной функции: из любой немонотонной функции путем подстановки в нее констант и х можно получить отрицание. Доказательство: возьмем два набора А  В для которых f(А)  f(В) и которые различаются K компонентами. Меняя последовательно в наборе А 0 на 1 мы будем приближаться к В и на j замене получим, что f(А₁,…,А_j-1,0, А_j+1,…,А_n)> f(А₁,…,А_j-1,1, А_j+1,…,А_n). Положим (х)= f(А₁,…,А_j-1,х, А_j+1,…,А_n), которая и будет функцией отрицания. Лемма о нелинейной функции: из любой нелинейной функции путем подстановки в нее констант и использования отрицания можно получить конъюнкцию. Доказательство: Пусть f нелинейна, тогда она содержит хотя бы одну конъюнкцию. Пусть К=х_i1 … x_is , s>1 – самая короткая из них. Положим х_i3 … x_is = 1, а для всех х_j, не входящим в К положим х_j =0. Поэтому f примет вид: (х_i1, х_i2) = х_i1 х_i2   х_i1   х_i2  , где  ,  и  - константы, равные 0 или 1. Положим теперь (х_i1 ,х_i2 ) = (х_i1   ,х_i2  )     . При раскрытии (х_i1 ,х_i2 ) получим (х_i1 ,х_i2 )= х_i1  х_i2. Лемма доказана.

Нужно для каждого класса Поста C∈{T0,T1,S,M,L} доказать, что замыкание [C] множества булевых функций C совпадает с C. Пусть f(g1,…,gn) — какая-то суперпозиция над C. Обозначим ее через φ. Без ограничения общности можно считать, что все функции f,g1,…,gn∈P2,n (для некоторого n).

Рассуждаем, используя индукцию по определению суперпозиции. Если для каждого i=1..n функция gi=xi, где xi — переменное, то φ=f(x1,…,xn)∈C. Предположим, что в суперпозиции φ все функции gi есть элементы класса Поста C (в частности, это может быть и соответствующая проектирующая функция, которая ввиду замечания 6.9 принадлежит всем классам Поста). Докажем, что и φ=f(g1,…,gn)∈C.

4. C=M. Берем произвольно наборы α˜ и β˜ так, что α˜⩽β˜. Докажем, что φ∈M. Имеем

так как все функции gi, i=1..n, монотонны и тем самым вектор (g1(α˜),…gn(α˜)) не больше вектора (g1(β˜),…gn(β˜)), а функция f также монотонна. Тогда ясно, что φ∈M.

5. Если же C=L, то очевидно, что при подстановке в линейную функцию (полином Жегалкина первой степени) вместо ее переменных произвольных линейных функций получится снова линейная функция.

Теорема Поста о функциональной полноте.

Система F={f₁, f₂, …,f_n} полна тогда и только тогда, когда она целиком не содержится ни в одном из пяти замкнутых классов: T₀, T₁, S, M, L .

Доказательство: 1) Пусть F полна, т.е. [F]= F. Предположим, что F содержится в одном из пяти классов – обозначим его через Q, т.е. F Q. Тогда в силу свойства замыкания и замкнутости Q, получим P₂=[F] Q = Q. С другой стороны замкнутые классы T₀, T₁, S, M и L попарно различны и отличны от P₂ (P₂ – стандартный набор из И, ИЛИ и НЕ). Таким образом P₂  Q. Полученное противоречие доказывает необходимость. (Также можно показать, что существуют функции, не лежащие ни в одном классе Поста (например, штрих Шеффера), а из [F] Q следует, что всякая суперпозиция над F также лежит в Q).

2) Пусть F не содержится целиком ни в одном из 5 классов. Это значит, что в системе есть 5 функции _I, _j, _k, _l и _m, не принадлежащие этим классам. Такая подсистема будет полна:

- Пусть _I T₀T_1.Тогда мы получим либо константу 1, либо отрицание. В последнем случае возьмем несамодвойств. функцию _k S и в силу леммы о несамодв. ф-ции получим константу, а используя отрицание, получим и другую.

- Теперь, на основе леммы о немонотонной функции, мы можем получить отрицание, подставляя в _l M константы и х.

- На основе леммы о нелинейной функции мы можем получить конъюнкцию, подставляя в константы, х и отрицание в _m  L.

Таким образом, мы получили полную систему из И и НЕ. Следовательно, теорема доказана.

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

Необходимость условия теоремы доказывается просто: если бы для некоторого класса Поста C выполнялось F⊆C, то всякая суперпозиция над F, согласно теореме 6.5, снова лежала бы в C. Между тем существуют функции, не содержащиеся ни в одном из классов Поста, например штрих Шеффера (см. пример 6.9). Таким образом, нашлась бы функция, которую нельзя представить в виде суперпозиции над F, что противоречит предположению о полноте F.

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

Для немонотонной функции fM∈F∖M, согласно теореме 6.6, найдутся два таких набора α˜ и β˜, что

α˜β˜=(α1,…,αi−1,0,αi+1,…,αn),=(α1,…,αi−1,1,αi+1,…,αn),fM(α˜)=1, а fM(β˜)=0.

Тогда ¬х=fM(α1,…,αi−1,x,αi+1,…,αn), т.е. отрицание может быть получено из немонотонной функции подстановкой вместо некоторого ее переменного xi переменного x, а вместо остальных переменных констант α1,…,αi−1,αi+1,…,αn, определяемых выбранными выше наборами α˜ и β˜. Но, вообще говоря, система F может и не содержать констант. Поэтому константы 0 и 1 необходимо представить некоторыми формулами над F.

Рассмотрим два случая.

Первый случай. В F существует функция f0, не сохраняющая константу 0, которая сохраняет константу 1; или существует функция f1, не сохраняющая константу 1, но сохраняющая константу 0.

Если существует функция f0∉T0 и f0∈T1, то константа 1 представляется формулой 1=f0(x,…,x), так как f0(0,…,0)=1 и f0(1,…,1)=0. Чтобы выразить константу 0, используем любую функцию g∈F, не сохраняющую константу 1:

0=g(1,…,1)=g(f0(x,…,x),…,f0(x,…,x)).

Если же указанная функция f0 не существует, но найдется функция f1∈T0∖T1, to константы представляем формулами над F аналогично (двойственным образом).

Второй случай. Любая функция из F, не сохраняющая константу 0, не сохраняет и константу 1, и, наоборот, любая функция из F, не сохраняющая константу 1, не сохраняет и константу 0.

Пусть f0(0,…,0)=1 и f0(1,…,1)=0. Тогда мы получаем возможность представить отрицание следующей формулой:

¬x=f0(x,…,x).

Переходим к построению формул для констант, так как они потребуются нам далее при построении формулы для конъюнкции. Чтобы представить константы формулами над F, воспользуемся несамодвойственной функцией fS из F. Для этой функции найдется такой набор α˜, что fS(¬α˜)=fS(α˜). Введем функцию от одного переменного h(x)=fS(xα1,…,xαn) (в предположении, что α˜=(α1,…,αn). Легко видеть, что h(0)=fS(¬α˜)=fS(α˜)=h(1), так как для любого σ∈{0;1} имеем

0^σ={1, if σ=0; 0, if σ=1;

1^σ={1, if σ=1; 0, if σ=0.

Итак, значение h(x) есть константа. Если она равна 0, то константу 1 представляем через функцию, не сохраняющую константу 0; если же h(x)≡1, то константу 0 представляем через функцию, не сохраняющую константу 1.

Опишем построение формулы для конъюнкции. Берем нелинейную функцию fL из F. В полиноме Жегалкина для этой функции выберем произвольное нелинейное слагаемое, содержащее наименьшее число переменных; пусть это будет слагаемое xi1,…,xik при 2⩽k⩽n. Вместо каждого переменного xm функции fL, где m∈{i1,…,ik}, подставим константу 0, т.е. заменим нулем все переменные, которые не вошли в выбранную ранее конъюнкцию. Получим "редуцированную" функцию

fL′=xi1,…,xik⊕ai1xi1⊕…⊕aikxik⊕a0=fL(0,…,0,xi1,0,…,0,xik,0,…,0).

Заметим, что коль скоро мы уже представили константы формулами над F, то функция fL′ тоже представлена формулой над F. Разобьем теперь множество переменных {xi1,…,xik} произвольно на две части: {xi1,…,xim} и {xim+1,…,xik}, где 1⩽m⩽k−1, и заменим все переменные первой части переменным x, а переменные второй части — переменным y. В результате получим функцию от двух переменных

χ(x,y)=xy⊕ax⊕by⊕c,

где a=ai1⊕…⊕aim, b=aim+1⊕…⊕aik, c=a0.

Ясно также, что функция х может быть представлена такой формулой над F:

χ(x,y)=fL(0,…,0,x⏟i1,0,…,0,x⏟im,0,…,0,y⏟im+1,0,…,0,y⏟ik,0,…,0),

т.е. функция χ получена из нелинейной функции fL∈F путем подстановки на место ее переменных с номерами i1,…,im переменного x, на место переменных с номерами im+1,…,ik — переменного y, а на место всех остальных переменных — константы 0, уже представленной формулой над F (см. выше).

Определим функцию ψ(x,y)=χ(x⊕b,y⊕a)⊕ab⊕c. Выразив эту функцию из полинома Жегалкина для χ получим

ψ(x,y)=χ(x⊕b,y⊕a)⊕ab⊕c==(x⊕b)(y⊕a)⊕a(x⊕b)⊕b(y⊕a)⊕c⊕ab⊕c==xy⊕ax⊕by⊕ab⊕ax⊕ab⊕by⊕ab⊕c⊕ab⊕c=xy,

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

Неформально граф можно рассматривать как множество точек и соединяющих эти точки линий со стрелками или без них.

Ориентированный граф G задается двумя множествами G=(V,E), где V — конечное множество, элементы которого называют вершинами или узлами; E — множество упорядоченных пар на V, т.е. подмножество множества V×V, элементы которого называют дугами.

Неориентированный граф называют связным, если любые две его вершины u и v соединены цепью (u∣=∣∗v).

Компонента связности (или просто компонента) неориентированного графа — это его максимальный связный подграф.

Ориентированный граф называют связным, если для любых двух его вершин u,v вершина v достижима из вершины u или вершина u достижима из вершины v (u⇒∗v или v⇒∗u).

Компонента связности (или просто компонента) ориентированного графа — это максимальный связный подграф.

Ориентированный граф называют сильно связным, если для любых двух его вершин u и v вершина v достижима из вершины u и вершина u достижима из вершины v (u⇒∗v и v⇒∗u).

Неориентированный граф G1=(V1,E1) называют ассоциированным с ориентированном графом G=(V,E), если его множество вершин совпадает с множеством вершин ориентированного графа G, а пара {u,v}образует ребро тогда и только тогда, когда u≠v и из u в v или из v в u ведет дуга, т.е. V1=V и

E1={{u,v}:(u,v)∈E∨(v,u)∈E, u≠v}.

Ориентированный граф называют слабо связным, если ассоциированный с ним неориентированный граф связный.

Вопрос №25

Вопрос №26

Вопрос №27

Вопрос №28

Неориентированный (ориентированный) граф G – это пара множеств G=<V,E>, где V – конечное множество, элементы которого называют вершинами или узлами. E – множество неупорядоченных (упорядоченных) пар на V, т.е. подмножество множества двухэлементных подмножеств V (VV), элементы которого называют ребрами (дугами). Граф (неориентированный или ориентированный) G₁=<V₁,E₁> называют подграфом графа G=<V,E> (соответственно, неориентированного или ориентированного), если V₁V и E₁E. Если V₁=V₂, то G₁ называется остовным подграфом графа G. Отображение h:V₁V₂ множества вершин графа G₁=<V₁,p₁> в множество вершин графа G₂=<V₂,p₂> называют изоморфизмом графа G₁ в G₂, если любые две вершины смежны в первом графе тогда и только тогда, когда их образы смежны во втором графе, т.е. если (u,vV₁)(up₁vh(u)p₂h(v)). Цепь в неориентированном (путь в ориентированном) графе G – это последовательность вершин v₁,v₂,…,v_n,…, такая, что для любого i v_i-()v_i+1. Простая цепь (все входящие в нее ребра попарно различны и все входящие в нее вершины, кроме, быть может, первой и последней, попарно различны) неориентированного(ориентированного) графа ненулевой длины с совпадающими концами называется циклом(контуром). Неориентированный (ориентированный) граф называют связным, если любые две его вершины соединены цепью (для любых его двух вершин u,v вершина u достижима из v или v достижима из u: u*v или v*u). Компонента неориентированного (ориентированного) графа G – это его максимальный связный подграф. Диаметр графа D(G) – это расстояние между двумя наиболее удаленными друг от друга вершинами. _{Автоморфизм графа G=(V,ρ) — это любая подстановка множества его вершин, являющаяся изоморфизмом G на себя.}

Матрица смежности вершин, или булева матрица графа. Это квадратная матрица В порядка n, элементы которой определяют следующим образом:

для неориентированного графа
bij={1, i,j vershiny smejnye;
0, inache;

для ориентированного графа
bij={1, iz i−vershiny v j vedet duga;
0, inache.

Циклический ранг неориентированного графа — это число обратных ребер при поиске в глубину из любой вершины, а коциклический ранг — число древесных ребер при поиске в глубину из той же вершины.

ν=m−n+k, где циклический ранг ν, число ребер m, число вершин n и число компонент связности к произвольного неориентированного графа G.

Неориентированным деревом называют связный и ациклический неориентированный граф.

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

Любое дерево с n вершинами содержит n-1 ребро.

Взвешенный граф – это граф, для которого задано отображение w:ER₀, где R₀ – множество действительных неотрицательных чисел.

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

1. Множество ребер H искомого остовного дерева полагаем пустым (H=∅).

2. Формируем множество VS={{v1},…,{vn}}, элементами которого являются множества вершин, соответствующих компонентам исходного остовного леса. Каждая такая компонента состоит из единственной вершины.

3. Сортируем множество ребер E исходного графа по возрастанию весов и формируем очередь Q, элементами которой являются ребра графа G.

4. Если множество VS содержит более одного элемента (т.е. остовный лес состоит из нескольких компонент) и очередь Q не пуста, переходим на шаг 5, если иначе — на шаг 7.

5. Извлекаем из очереди Q ребро e. Если концы ребра е принадлежат различным множествам вершин Vi и Vj из VS, то переходим на шаг 6, если иначе, то отбрасываем извлеченное ребро и возвращаемся на шаг 4.

6. Объединяем множества вершин Vi и Vj (полагая W=Vi∪Vj), удаляем множества Vi и Vj из множества VS и добавляем в VS множество W. Добавляем ребро e в множество H. Возвращаемся на шаг 4.

7. Прекращаем работу. Множество H есть множество ребер полученного остовного дерева.