Шпоры по дискретной математике - файл n1.doc

приобрести
Шпоры по дискретной математике
скачать (249.5 kb.)
Доступные файлы (1):
n1.doc250kb.08.07.2012 22:36скачать

n1.doc

Множества. Основные понятия. Способы задания.

Создатель теории множеств – Кантер(немец). Под множеством Кантер понимал скопления различных и определенных предметов, мыслимых как единое целое. Предметы, из которых состоят множества, зовут элементами множества. Слово определенный говорит о том, что если мы имеем множество и некоторый предмет, то всегда можно определить, принадлежит он множеству или нет. Слово различимый говорит о том, что если мы имеем два элемента множества, то всегда можно сказать, одинаковы они или нет. Но самое главное, что множество элементов, составляющих множество, мыслится как единое целое. Само множество может быть элементом другого множества. Что касается элементов множества, то они могут быть любой природы.
Множества могут быть конечными или бесконечными. И вообще мы можем не знать количество элементов в множестве.
Если элементами множества являются числа, то го зовут числовым. Множество изображается заглавными буквами, а его элементы – прописными. Некоторые определенные множества имеют определенные названия: N- множество натуральных чисел, Z- целых, Q- рациональных, I- иррациональных, R- действительных чисел, C- комплексных чисел. aA, aA aA. множество, не содержащее ни одного элемента, зовут пустым, и пишут 0. два множества А и В считаются равными, если они состоят из одних и тех же элементов. A={1,2,3}, B={1,1,1,2,2,3,3} – A=B.
Множества можно задавать: 1) перечислением элементов A={1,a,b}, 2) с помощью определяющего свойства M={x|x-четные}.
Если каждый элемент множества А является элементом множества В, то А зовут подмножеством В: АВ. Считается, что пустое множество является подмножеством любого множества. Два подмножества множества А – А и 0 – зовут несобственными подмножествами множества А. Все остальные – собственные. Если С – собственное подмножество множества А, то пишут СА.

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

1) объединение: множество тех элементов х, которые принадлежат хотя бы одному множеству. AB={x|xA или xB}
2) пересечение: общие элементы AB={x|xA и хВ}.
3) разность множеств.A\B={x|xA и xB}
4) симметрическая разность A_B={x|xA, то xB; xВ, то xA}.

Иногда бывает удобно все рассматриваемые множества в некоторой теории считать подмножествами некоторого одного множества, которое в этом случае зовут универсальным U.
5) A- дополнение множества А. Это есть U/A=A

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

Алгеброй зовут некоторое множество с введенными на нем операциями: A=, где М- носитель, - операции.

Школьная алгебра: A=. Возьмем U: A=- булева алгебра.

1) переместительный закон: AИB=BИA; AЗB=BЗA;

2) сочетательный закон: AИ(BИC)=(AИB)ИC; AЗ(BЗC)=(AЗB)ЗC
3) распределительный закон: AИ(BЗC)=(AИB)З(AИC); AЗ(BИC)=(AЗB)И(AЗC);
4) Not(not(A))=A – дополнение дополнения есть само дополнение
5) AИ0=A; AЗ0=0
6) AИU=U; AЗU=A;
7) AИA=A; AЗA=A
8) AИ`A=U; AЗ`A=0
9) закон поглощения AИ(AЗB)=A; AЗ(AИB)=A
10) закон де Моргана: not(AИB)= `AЗ`B; not(AЗB)= `AИ`B

Бесконечное множество

Эквивалентность множеств, равномощность

Свойства бесконечных множеств сильно отличаются от свойств конечных. Вещи, не возможные для конечных, становятся возможными для бесконечных множеств.

Как сравнить бесконечное множество по численности элементов? Способы сравнения конечных множеств:

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

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

Т.о. понятие мощность является обобщением понятия одинаковой численности для конечных множеств.

Пример: 1) N(натуральные)~Ч(четные); N={1,2,3,4…,n,…}, Ч={2,4,6,8…,2n,…}; nN, чОЧ => ч=2n

2) [a,b]~[c,d] – отрезки; a?b c?d;

xО [a,b] x?y

yО [c,d] y?x

y=((d-c)/(b-a))(x-a)+c

3) (0,1)~[0,1] xn?xn+2

4) (0,1)~(-?;+ ?) y=tg((?/2)*(2x-1)); => [a,b]~(a,b)~ (-?;+ ?) => в любом отрезке столько же точек, сколько во всей прямой.

5) (0,1)~ ед.квадрат

А – любая точка квадрата А(х,у)

х = 0,?1, ?2, ?3, ?4,…

y = 0,?1, ?2, ?3, ?4,…
A?BО (0,1) B(0, ?1, ?1, ?2, ?2, ?3, ?3,…)

C(0,?1, ?2, ?3, ?4,…) О (0,1) ? D(x,y) x= 0,?1, ?3,…,y= 0, ?2, ?4,… => множество точек прямой эквивалентно множеству точек плоскости, пространства.
Счетное множество

Бесконечное множество М= {a1, a2, a3, ….} называется счетным, если оно эквивалентно множеству натуральных чисел, т.е. элементы счетного множества можно занумеровать. Пример – множество четных чисел, множество нечетных чисел. Покажем, что счетным будет и множество целых чисел Z.

nN, zZ , z=[n/2](-1)n ([] – отбрасывание дробной части числа)

1?0; 2?1; 3?-1; 4?2; 5?-2

Доказывается, что: 1)объединение конечного множества и счетного есть множество счетное; 2)объединение конечного числа счетных множеств есть множество счетное 3)объединение счетного числа счетных множеств есть множество счетное.

Способ нумерации счетного множества:

1) a1 a2 a3 … 2) 1 1 1 1 1…

b1 b2 b3… 1 1 1 1 1…

……… 1 1 1 1 1…

f1 f2 f3… 1 1 1 1 1…


Несчетное множество

Теорема: множество действительных чисел (0,1) несчетно.

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

Ѕ = 0,50000000… и Ѕ= 0,49999999… => все mi ?0 и все mi ?9

Предположим, что все числа (0,1) можно занумеровать:

1?0, ?1, ?2, ?3, ?4,…

2?0,?1, ?2, ?3, ?4,…

3?0,?1, ?2, ?3, ?4,…, построим следующее число a(0,1) a=0,1, 2, 3,…, где 01<9, 02<9, 03<9 … и d1<> ?1 , d2<> ?2, d3<> ?3 и т.д.

a(0,1) но по построению это число не совпадает ни с одним из пронумерованных чисел, т.е. мы нашли число, которое не получило номера, что говорит о том, что множество точек (0,1) несчетно, а следовательно, несчетным будет множество действительных чисел плоскости, пространства.

Доказывается, что из всех бесконечных множеств самым малым по мощности является счетное множество, и если мы удалим из бесконечного множества счетное, то останется множество, эквивалентное данному, отсюда вытекает, что множество иррациональных чисел несчетно, т.к. это разность между всеми действительными и рациональными числами, т.е. I=R\Q.

Множество трансцидентных чисел – несчетное множество

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

Если M={a1,…,an}, то |M|=n

Теорема: мощность множества всех подмножеств конечного множества(степень) имеет мощность 2n ,т.е. |P(M)|=2|M|=2n

Доказательство: пусть имеем конечное множество М, составим степень этого множества. P(M)={0,{a1},…,{an},{ai,ai+1,…,{ak…am}}}. Поставим в соответствие каждому элементу множества МР(М) n-значное двоичное число по закону: если элемент ai из множества М является элементом М, то на i-том месте двоичного числа ставим 1, в противном случае – 0.

aiN

{a1}?10…0 тем самым мы перечислили все n- значные

{an}?0…010… двоичные числа, а их всего 2n

{a1,a2}?110…0

{a1…am}?1…1

Следствие: |N|<|P(M)| для конечных множеств. Покажем, что это неравенство имеет место и для бесконечных множеств.

Пусть М- бесконечное множество М={a1,a2,a3,…}, составим степень Р(М)={0,{a1},…,{a1,a2},…}, если каждому элементу ai множества М поставить в соответствие элемент ai в степени (ai?{ai}P(M) ), то => |M||P(M)|.

Чтобы доказать теорему, мы должны показать, что Р(М) не эквивалентно М, тем самым |M|<|P(M)|.

Предположим противное, а именно что можно установить взаимно однозначное соответствие между элементами множеств М и Р(М).

М Р(М) При этом может встретиться такой случай, что элемент,

a1?{ } (1) стоящий в левой части (1) , входит в правую часть,

a2?{ } тогда этот элемент назовем включенным, или элемент,

… стоящий в левой части, не входит в правую часть, тогда

ak?0 мы назовем его невключенным. Составим множество S

… из всех невключенных элементов, ОМ. Множество S не пусто (ak), но множество S ai?{a1…} и т.д. является элементом степени SОP(M)S будет соответствовать какой-то элемент pОM, т.е. рОМ, р?S,  он является включенным или нет.

Пусть р – включенное, тогда он содержится в S, чего быть не может, т.к. S состоит из невключенных элементов. Пусть теперь р – невключенное, тогда он не содержится в S, но S состоит из всех невключенных Ю элемент рОМ не является ни включенным, ни невключенным. Это противоречие доказывает теорему.

Из этой теоремы вытекает, что множества сколь угодно высокой мощности не существует: |M|<|P(M)|<|P|P(M)||<…

Пример: множество всех действительных функций – мощность выше континуума.


ОТНОШЕНИЕ НА МНОЖЕСТВАХ

1.Декартово произведение и его свойства.

Назовем упорядоченной парой (х,у) совокупность 2-х элементов х и у, расположенных в определенном порядке. ( ѕ = (3,4); a+bi = (a,b); y=f(x)(x,f(x))). Аналогично вводятся понятия упорядоченной тройки, четверки и т.д. пусть имеем два множества А и В.

Декартовым (прямым, бинарным) произведением множеств А и В называется множество упорядоченных пар АВ = {(x,y)|xОA,yОB}

Пример:1) A={1,2,3},B={3,4}; АВ={(1,3),(1,4),(2,3),(2,4),(3,3),(3,4)}

2) множество точек плоскости есть декартово произведение множества точек осей. Ели А=В, то АґА=А2 и говорят: декартова степень множества А.

аналогично можно ввести декартово произведение n множеств.

А1ґА2ґ…ґAn = {(x1…xn)|x1ОA1,x2ОA2,…,xnОAn}

Если А1=А2=…=An, то А1ґА2ґ…ґAn = An – n –я декартовая степень.

Свойства:

1. АґВ= ВґА 2. Аґ(ВґС)=( АґВ)ґС

3. Аґ(ВUC)=(AґB)U(AґC) 4. (BUC)ґA=(BґA)U(CґA)

5. (AґB)?(CґD)=(A?C)ґ(B?D) 6. Aґ0=0ґA=0

2. Бинарное отношение.

Любое подмножество ? декартового произведения называется бинарным отношением между элементами множеств А и В. Т.о. бинарное отношение – это множество упорядоченных пар, которые между собой находятся в определенном отношении ?. ?АґВ. Бинарное отношение называют двуместным. Аналогично можно ввести n–местное отношение.

Если (х,у)О?, то пишут х?у, если (х,у)?, то х?у

Способы задания бинарного отношения:

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

A={1,2},B={1,2,3}; ‘<’ ( вид ?) = {(1,2),(1,3),(2,3)}

2) c помощью матрицы

Cij={1, если ai ? aj ; 0, если ai ? aj }

3) графически.

Назовем областью определения отношения ? множество х, для которых существует у, что х?у (?о={x| y, х?у }). Областью значений:
?з={y| x, х`?у}.

Назовем отношение ?-1 обратным к отношению ?, если есть множество тех пар (х,у), что (у,х)О?, т.е. ?-1={(x,y)|(y,x)О?}. (?-1)-1=?

Композицией отношения ?1 и ?2 называется отношение, обозначаемое
?1• ?2, которое означает, что найдется такое z, что (x,z) будет О?1, а (z,y) находиться в отношении ?2.

?2• ?1={(x,y)| z (x,z)О?1, (z,y)О?2 }

Докажем (?2• ?1)-1= ?1-1•?2-1 : возьмем пару (х,у)О (?2• ?1)-1, по определению обратного отношения (у,х)О ?2• ?1, по опр-ю композиции существует z, что (y,z)О?1 и (z,x)О?2, по опр-ю обратного отношения (z,у)О?1-1 и (х,z)О?2-1 => мы имеем композицию ?1-1•?2-1.
Свойства бинарных отношений на множестве М.

Замечание: х и у берутся из одного и того же множества М.

Бинарное отношение ? на множестве М называется общезначимым, если ? совпадает с декартовым произведением. Если отношение ? не содержит ни одного элемента, то оно называется пустым.

1. отношение ? на множестве М называется рефлексивным, если каждый элемент из множества М стоит в отношении ? сам с собой.
х ОМ х?х. Пример: 1) ‘<=’,’>=’,’=’;2) отношение параллельности на множестве прямых. Не является рефл.: ’<’,’>’,’перпендикулярность’, ’симметричность относительно прямой’. Отношение, не являющееся рефлексивным, называется нерефлексивным. Если отношение задано матрицей, то на главной диагонали матрицы стоят единицы, если отношение нерефлексивное, то нули и единицы. Отношение ? называется антирефлексивным, если ни один элемент не находится в отношении ? сам с собой. Если отношение рефлексивное, то все элементы главной диагонали матрицы – нули.

2. отношение ? на множестве М называется коммутативным (симметричным), если это отношение с каждой парой (х,у) содержит пару (у,х). матрица такого отношения будет симметрична относительно главной диагонали. Пример: ‘=’,’?’. Не является коммутативным: ‘<=’,’>=’. Отношение коммутативно тогда и только тогда, когда оно совпадает со своим обратным отношением: ?= ?-1. Отношение ? на множестве М называется антикоммутативным (антисимметричным), если х,у ОМ пара (х,у) х?у и у?х, т.е. х=у. Замечание: из определения антикоммутативности следует, что пара (х,у) может находиться в отношении ?, а (у,х) – нет. Если отношение не является коммутативным и антикоммутативным, то оно называется некоммутативным. У обоих последних матрица не симметрична относительно главной диагонали.

3. отношение ? на множестве М называется транзитивным, если для х,у,z ОМ имеем: если х?у и у?х, то х?z. Пример: ‘<=’,’>=’,’=’,’<’,’>.
Замыкание отношений.

Рефлексивным замыканием ?R отношения ? на множестве М называется пересечение всех рефлексивных отношений, содержащих данное отношение.

? ?R

0 0 1 1 0 1 - ставим единицы на главной диагонали.
1 1 0 1 1 0
0 0 0 0 0 1

Коммутативным замыканием ?К отношения ? на множестве М называется пересечение всех коммутативных отношений, содержащих данное отношение.

? ?R

0 0 1 0 1 1 - делаем матрицу симметричной
1 1 0 1 1 0 (можно заменять только нули на
0 0 0 1 0 0 единицы)

Транзитивным замыканием ?Т отношения ? называется пересечение всех транзитивных отношений, содержащих данное.

Транзитивное замыкание можно отыскивать двумя способами: 1) аналитически, путем перемножения матриц и 2) графически.

1): пусть дана матрица А отношения, тогда а) находим произведение А*(А+Е)=А1, которая будет содержать нулей не больше, чем матрица А; б) находим А1*(А+Е)=А2 и т.д. в) вычисления проводят до тех пор, пока не установятся нули.

2): пусть отношение задано в виде ор-графа, тогда будем двигаться от вершины А по стрелкам к любой другой вершине В, если мы попадем в вершину В, а стрелки из А в В не стояла, то ее ставят. Если из какой-либо вершины по стрелкам можно вернуться к ней, то ставится петля (при условии, что до этого петли не было).

Типы бинарных отношений.

1. отношение эквивалентности – это отношение ?, если это ?: а) рефлексивное, б) симметричное и в) транзитивное. Пример: параллельность на множестве прямых, ‘=’. Не эквивалентное: перпендикулярность на множестве прямых. Отношение эквивалентности устанавливается между элементами одного множества и разбивает множество на непересекающиеся подмножества, которые в сумме дают всё множество. Причем каждое из этих подмножеств зовут классом эквивалентности. Все элементы, попавшие в один класс, считаются эквивалентными между собой, а элементы разных классов между собой не эквивалентны. Пример: M={2,3,4,5,6,7,8}; {2,4,6,8}- отношение «четные» и {3,5,7} – отношение нечетные. Если составить множество из всех классов эквивалентности множества М, то получим множество, которое зовут фактор-множество относительно отношения эквивалентности M\ ~. M\ ~{{2,4,6,8},{3,5,7}} – множество множеств. Отношение эквивалентности разбивает заданное множество на подмножества по некоторому признаку. Верно и обратное: если некоторое множество М разбить на непересекающиеся подмножества, которые в сумме дают множество М, то это разбиение определяет на множестве М отношение эквивалентности. При этом считается, что все элементы, попавшие в один класс, эквивалентны между собой, а различных классов – не эквивалентны.


2. отношение порядка. Бинарное отношение зовут отношением порядка, если оно несимметрично и транзитивное. (ху) – читаем «х предшествует, подчиняется у». Порядок может быть строгим, т.е. если пара (х,у)О?, то пара (у,х)?. Пример: отношение ‘<’. Множество, на котором введен порядок, зовут упорядоченным. Если отношение рефлексивно, антисимметрично и транзитивно, то оно зовется отношением частичного порядка (не строгого). Пример: ‘<=’; не является таковым ‘=’,’ ?’. Если все элементы частично упорядоченного множества сравнимы между собой (т.е для некоторых элементов (х,у)ОМ верно х=у или у=х), то множество М зовут линейно упорядоченным, иначе оно не является линейно упорядоченным. Пример: ‘<=’ – множество упорядоченно на хОR; ‘’ – не является линейно упорядоченным, т.к. не всегда верно АВ.

Отображение и функции.

Отображение: пусть имеем два множества Х и У. Отображением множества Х во множество У (пишем так: f: XY) называется f-правило, по которому каждому элементу х из Х ставится в соответствие единственный элемент у из У. y=f(x). Это отображение осуществляется с помощью функции y=f(x).
У зовут образом Х, а Х зовут прообразом У. Если не для всех х из Х есть соответствие у из У, то это не отображение.

Свойство отображений:

1. f: xy зовут сюрьективным, если каждый элемент уОУ обладает хоть одним прообразом. Если Х и У – конечные множества, то сюрьекцию можно осуществить, если мощность Х не меньше мощности У: |X|>=|Y|. Пример: является с. y=x3, не является – y=x2.

2. f: xy зовут инъективным, если каждый образ имеет ровно один прообраз. х1,х2 ОХ, f(x1)=f(x2) => x1=x2. если множество конечно, то инъекция осуществима тогда, когда |X|<=|Y|. Пример: явл. и. – y=ex, не и. - y=x2, т.к. у(х)=у(-х).

Если отображение одновременно сюрьективно и инъективно, то его зовут биективным, или взаимно однозначным соответствием (пример: у=2х-3).

3. обратным отображением f—1 множества У во множество Х зовут множество таких х, что f(x)=y; f-1(y)={x|f(x)=y}. При обратном отображении образы и прообразы меняются местами => обратное отображение может осуществиться только тогда, когда отображение f: x®y биективное. (f-1)-1=f. Обратное отображение можно определить для инъекции, не являющейся сюрьекцией, но это будет частичным отображением, т.е. отображением, заданном на некотором подмножестве общего множества, которое в этом случае зовут областью определения отображения. Пример: f:y=ax,
f-1:x=logay. Если у нас отображение сюрьективное, но не инъективное, то частичное обратное отображение построить нельзя.

Связь между отображением и бинарными отношениями.
?XY; (x,y) – множество упорядоченных пар. f: x®y (x,f(x))=(x,y) – тоже множество упорядоченных пар. Итак, отображение есть тоже бинарное отношение. Но не всякое бинарное отношение является функцией. По определению функции каждому хОХ соответствует единственное уОУ, что на языке отношений пишется так: (x,y)? и (x,z)?, то y=z. Пример: ?={(1,2),(1,3),(2,4)} – это бинарное отношение, но не функция. ?={(1,2),(3,2)} – f. Очевидно, используя бинарные отношения, можно сказать, что обратное отношение ?-1 будет функцией, если различным х соответствуют различные у. Пример: ?={(1,2),(3,2)}; ?-1={(2,1),(2,3)}- уже не функция.
Булевы функции.

Основные способы задания.

E={0,1}. f: En®E – отображение ЕЕЕ…Е®Е называется булева функция от переменных y=f(x1,…,xn), (x1,…,xn)En. БФ – двоичная функция двоичных переменных. f (x̃)=f(x1,…,xn). f(0…0)=f(0̃), f(1…1)=f(1̃). y=f(x), x=0,1; y=f(x1,x2). БФ можно задать кубически. При этом область определения – вершины n – мерного куба.

БФ может быть задана таблично, причем все наборы f(x,y,z) условимся заносить в порядке возрастания их десятичных эквивалентов.

x y z f f(10101110) – канонический набор. Если мы имеем
0 0 0 1 функцию n переменных, то количество наборов = 2n
… Т.к. переменные принимают конечное число значений,

1 1 1 0 то и БФ-й от n переменных будет конечное число. 2?=2к

Изучать БФ, используя табличное задание можно, если число переменных невелико. Иногда удается в функции сократить число переменных, причем свойства функции от этого не меняются. Переменная xi называется существенной, если удается найти такой набор ?i, что значения f(?1,…, ?i-1,0, ?i+1,… ?n)? f(?1,…, ?i-1,1, ?i+1,… ?n). Существенная зависимость означает невозможность определения значений функции без использования переменной xi. Переменная xi называется фиктивной, если для всех наборов f(?1,…, ?i-1,0, ?i+1,… ?n)= f(?1,…, ?i-1,1, ?i+1,… ?n).

Основные булевы функции.

Основные БФ ДМ играют ту же роль, что и элементарные функции обычной математики.

xy f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15 f16
00 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1- const 0, 2- x1x2
01 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 3- not(x®y), 4- x,
10 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 5- not(y®x), 6-y,
11 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 7- x  y, 8- xy,
9- xy, 10- xy, 11- y, 12- y®x, 13- x, 14- x®y, 15- x/y, 16- const 1.
m(x,y,z) – функция согласования (медиант), по количеству 0 и 1 функция m принимает значение исходя из большинства.

Основные булевы тождества.
БФ может быть задана формулой. Стройматериалом для функции является: const 0,1 , x,y, ,,,,,,/. Приоритет:  ,, все остальные в порядке следования. Если нужно изменить порядок, то ставят скобки. БФ можно преобразовать, используя основные тождества. Две функции называются тождественными, если они реализуют одну функцию. Пример: ху=ху. Тождеством называется пара тождественных функций, связанных знаком «=».

1. х х=х, х 0=0, х 1=х, х х=0, хх=х, х0=х, х1=1, хх=1, хх=0, х0=х, х1=х, хх=1.

2. х у=у х, хЪу=уЪх, хЕу=уЕх, х(yz)=(xy)z, xЪ(yЪz)= (xЪy) Ъz, xЕ(yЕz)=(xЕy) Еz.

3. x(yЪz)=xyЪxz, xЪyz=(xЪy)(xЪz), x(yЕz)=xyЕxz.
4. not(xЪy)= x`y, not(xy)= `xЪ`y.

5. x®y=`xЪy – импликация, xy=xyЪ`x`y – эквивалентность, xЕy=x`yЪ`x y, xy=not(xЪy), x/y=not(xy).

xyЕxЕy=xЪy.


Двойственность. Принцип двойственности.

Функция f*(xn) называется двойственной функции f(xn), если она построена по правилу: f*(xn)=not( f(x1, x2, …,xn) )= f(xn). Чтобы построить f* на нуле, мы должны посмотреть, чему равно значение функции на 1 и инвертировать: f*(0)= f(1). Столбец функции f* получается из столбца функции f переписыванием последнего в обратном порядке, одновременно инвертируя двоичные цифры. Очевидно, что (f*)*= f. Если функция f= f*, то она называется самодвойственной функцией. Рассмотрим функции, двойственные к элементарным: (xy)*=xy, 0*=1,1*=0, (xy)*=xy, (x/y)*=xy.

Теорема1: если функция f зависит от переменной xi фиктивно, то и двойственная к функции f зависит от xi фиктивно. Пусть R – система БФ, которые используются для реализации функции f и будем говорить, что f реализована над системой R.

Теорема2(1-й принцип двойственности): если функция f реализована над системой R, то заменой каждого символа операции в f на двойственный получится формула, которая реализует двойственную функцию f*. Заметим, что порядок выполнения действий при замене операций на двойственные сохраняется, поэтому в нужных местах проставление скобок обязательно.

Теорема3: если функция f, то и f **.

Переход от табличного задания функции к аналитическому.

Если мы знаем аналитическое задание функции, то мы всегда может построить ее таблицу значений. Но как наоборот? Поскольку одна и та же функция может быть выражена различной формулой, то прежде всего поставим вопрос: «какие операции мы будем использовать для получения f?» Будем для построения функции f использовать три операции ( ,,). Назовем элементарным произведением(элементарной суммой) конъюнкцию(дизъюнкцию) переменных и их отрицания. Совершенным произведением функции и переменных называется элементарное произведение, удовлетворяющее условиям: а) оно содержит и переменные, и отрицания, б) все переменные различны и в) в произведении не могут содержаться переменные со своим отрицанием.

Аналогично вводится понятие совершенной суммы. Очевидно, что если взять два различных СП(СС), то они отличаются хотя бы одним знаком отрицания, а потому их конъюнкция(дизъюнкция) = 0(1).

Запись БФ через СП.(СДНФ)

f =(x1,…,xn)= x1 x2x3…xn. Поставим каждой переменной с отрицанием в соответствие 0, а без -1. Тогда мы получим n-значное двоичное число, различных совершенных произведений будет столько, сколько различных n-значных двоичных чисел, т.е. 2n. Если между цифрами двоичного числа, соответствующего СП, поставить запятые, то на него можно смотреть как на координаты вершин n-мерного куба, т.е. каждому СП соответствует вершина n-мерного куба, которая называется собственной вершенной данного СП. СП=1 в своей собственной вершине и только в ней. Отсюда вытекает правило построения функции через СП: 1)в таблице отыскиваем 1, 2) в каждой строке, где стоят 1, записываем СП, 3) берем дизъюнкцию этих СП.
Построение БФ через СС.(СКНФ)

Возьмем СС функции и поставим в соответствие `х -1, х – 0. Тогда очевидно, что различных СС=2n, и эти двоичные числа можно рассматривать как вершины n-мерного куба, которые называются собственными вершинами соответствующих СС. СС=0 в своей собственной вершине и только в ней. Отсюда следует правило построения функции f через СС: 1) нужно в строках, где стоят 0 функции, записать соответствующие их СС, 2) взять их дизъюнкцию.

Запись БФ через СП(СС) называется СДНФ(СКНФ). Из изложенного следует, что всегда можно функцию выразить через операции ,, . Заметим, что если функция f=const 1, то она не имеет СКНФ, и наоборот. По виду функции в совершенной форме всегда можно сказать, будет она const, или нет. Если функция задана аналитически, то ее всегда можно привести к СФ. Для этого ее сначала упрощают так, чтобы она содержала три операции ,, , а затем, используя формулы хх=0 , хх=1, приводят к СФ.

Разложение функции по переменным.

Разложить функцию по переменным значит представление ее в виде конъюнкции переменных, умноженных на функции меньшего числа переменных. x=xЪ`x`s, где х- булев. переменная, а s ={0,1}. x0=x 0Ъ`x 1. xs={x, если s=1;`x, если s=0}. ss=1. Пусть f(xn) и 0<=m<=n, тогда имеет место f(xn)=[x1 s1 x2 s2 … xm sm f(s1,s2,s3,…,sm,xm+1,…,xn)], где …………( s1… sn) дизъюнкция берется по всем наборам переменных.

Минимизация БФ методом Вейча.

После того, как аналитически записали через СП функцию, ее надо упростить, т.е. минимизировать. Минимизацию можно проводить преобразованием выражения таким образом, чтобы было как можно меньше членов дизъюнкции (min число элементов). Или минимизацию проводят по числу букв, что соответствует минимальному числу входов. Минимизация проводится в классе операций ,, . Если мы получили min форму в этом классе, то это не значит, что дальнейшее упрощение невозможно. Назовем элементарное произведение рангом r, если оно содержит r сомножителей. Два элементарных произведения одного ранга называют соседними, если они отличаются одним отрицанием. Два соседних ЭП ранга r можно заменить ЭП ранга r-1, которое равно их общей части (склейка). Если мы имеем конъюнкцию двух ЭП, одно из которых является собственной частью другого, то конъюнкцию можно заменить одним ЭП, которое совпадает с собственной частью большего произведения.

Замкнутость и полнота.

Р2 – множество всех БФ. R – какие-нибудь функции из множества Р2. можно выразить любую функцию из Р2, используя только функции системы R. Система R называется полной в Р2, если любая функция из Р2 может быть реализована над системой R. Чтобы узнать, будет ли система полной, существует критерий полноты: пусть система функций R ={f1,f2,…} – полная и пусть задана система функций S={g1,g2,…}. Если каждую функцию системы R можно выразить через функции системы S, то система S- полная. С понятием полноты часто связано понятие замкнутости. Замыканием системы R называется множество булевых функций, которые можно реализовать над системой R. Очевидно, что если R полная система, то замыкание совпадает с Р2. [R]= Р2.

Реализация функций многочленом Жегалкина.

R={1,ху,ху}- полная, поэтому любую БФ можно реализовать над этой системой. Полученная при этом форма называется многочленом Жегалкина. Многочленом Жегалкина называется представлении функции в виде суммы по модулю 2, конъюнкции переменных и, быть может, 1. f(x,y)=?1xy?2x?3y?4. ?i находится методом неопределенных коэффициентов, т.е. зная табличное задание функции и подставляя различные наборы в многочлен Жегалкина, получим систему для определения ?i. f(0,0)=0, => x=0 и у=0 => ?4=0. Более простой алгоритм: 1)выписываем через интервал значения ф-и, 2)будем складывать соседние члены по модулю 2 и записывать ниже, 3) и т.д., 4) в таблице отмечаем те строки, кот-е соответ-ют единицам, стоящим на левой стороне треугольника, 5) в каждой отмеченной строке таблицы записываем конъюн-ю переменных, кот-е в этих строках равны 1 (если все переменные равны 0, то ставим на место конъюнкции ставим 1), 6) полученные конъюнкции объединяем знаком .

Важнейшие замкнутые классы.

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

1) класс Т0={ f(xn)| f(0)=0} – множество функций, которые на нулевом наборе равны 0. 2) класс Т1={ f(xn)| f(1)=1}. 3) класс S (класс самодвойственных функций). S={ f(xn)| f=f*}, где f*- двойственная функция. 4) класс монотонных функций M={ f(xn)| (?1…?n) (1…n)} (если набор ?i предшествует набору i ). Если функция не принадлежит к классам Т0 и Т1, то она не может быть монотонна. 5) класс линейных функций L={ f(xn)| ?1x1?2x2…?nxn?n+1xn+1…=f }, где ?i={0,1}.
Теорема о функциональной полноте: чтобы система R была полной в Р2, необходимо и достаточно, чтобы для каждого класса T01,S,M,L нашлась бы функция из система R, не принадлежащая этому классу.

Функции Пирса и Шеффера.

Реализация таблично-заданной функции через эти функции.

Рассмотрим свойства, которыми обладают эти функции: 1) они подчиняются коммутативному закону: xy=yx; x/y=y/x; 2) эти функции не подчиняются сочетательному закону: x(yz)?(xy) z; x/(y/z)?(x/y)/z, 3) законы де Моргана: not(xy)=x/y; not(x/y)=xy;
4) действие с нулем: x0=x; x/0=1; 5) действие с единицей: xЇ1=0; x/1=`x; 6) связь с отрицанием: `x=xЇx; xЇ`x=0; `x=x/x; x/`x=1; 7) связь с конъюнкцией (дизъюнкцией): xy=not(xy)=(xЇy)Ї(xЇy); xy=not(not(xy)) =not(`x`y)= `xЇ`y=(xЇx)Ї(yЇy); xy=not(xЇy)= `x/`y=(x/x)/(y/y); xy=not(not(xy))=not(x/y)=(x/y)/(x/y). По аналогии с двуместными функциями можно вводить n-местные функции, т.е. x1Їx2Їx3Ї…Їxn= not(x1x2x3…xn); x1/x2/x3/…/xn=not(x1x2x3…xn). n- местные функции обладают всеми свойствами двуместных, но поскольку сочетательный закон не справедлив, то x/y/z?x/(y/z).


Запись аналитического выражения функции, заданной таблично, через функцию Шеффера и Пирса.

а) через функцию Шеффера: 1) отмечаем в таблице строки, где f=1; 2) каждому набору переменных поставим в соответствие терм Шеффера, причем нулю ставится в соответствие соответствующая переменная с отрицанием, а единице – без отрицания (111- x/y/z); 3) полученные термы берут в скобки и объединяют через /. (можно показать, то полученную форму можно привести к СДНФ).

б) через функцию Пирса: 1) находим троки, где f=0; 2) каждому набору переменных поставим в этих строках в соответствие терм пирса, причем переменной отрицанием соответствует 1, а без отрицания-0(000 - xЇyЇz)
3) полученные термы заключаем в скобки и объединяем стрелками Пирса (полученную форму можно привести к СКНФ).

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

Основные понятия теории графов.

Возьмем два множества: V- множество точек(не пустое), E- множество линий (может быть пустое). Возьмем элемент e из множества E. Если существует пара элементов u,vV, что эти элементы являются концами линии е, то говорят, что элемент е инцидентен элементам u и v, и наоборот, элементы u и v инцидентные.
Графом (G,G(u,v),V E) называется совокупность множеств V и E между элементами которых определено отношение инцидентности, причем для каждого элемента еОЕ найдется пара элементов из множества V, что e инцидентно этим элементам. Обратное вообще говоря неверно: элементы V не инцидентны никаким элементам из множества Е.???
Элементы множества V называются вершинами графа, элементы множества Е- ребрами графа. Вершина, не инцидентная ни одному ребру, называется изолированной. Граф, состоящий только из изолированных вершин, называется нуль-графом. Вершины, инцидентные одному ребру, называются смежными. Два ребра, инцидентные одной вершине, называются смежными. Если вершина инцидентна только одному ребру, то она называется висячей. Если вершина инцидентна только двум ребрам, то она называется транзитивной. Если граф содержит петли, то он называется псевдографом. Если граф содержит кратные ребра, то его называют мультиграф. Если не никаких оговорок, то, говоря о графе, будем полагать, что он не содержит ни петель, ни кратных ребер. В некоторых случаях рассматриваются графы, вершины которого неравноправны, т.е. рассматриваются в определенном порядке, тогда ребру приписывается направление от начальной вершины к конечной. Направленное ребро называется дугой графа. Граф, содержащий только дуги, называется ориентированным графом, или ор-графом. Если граф содержит дуги и ребра, то он называется смешанным. Для неориентированных. графов (u,v)=(v,u), для ор-графов (u,v)?(v,u).
Способы задания графов.

1) геометрический.

2) табличный а) назовем вершину vi непосредственно предшествующей вершине vj, если существует дуга (vi,vj). Множество вершин, непосредственно предшествующих вершине vj, обозначим B(j), тогда граф можно задать в виде таблицы, где в первой троке записываются вершины, а во второй строке под ними вершины, непосредственно предшествующие соответствующей вершине.
Вершина vj называется непосредственно следующей за вершиной vi, если существует дуга (vi,vj). Множество вершин, непосредственно следующих за вершенной vi, обозначим как A(i). Таблица задается аналогично. Очевидно, ели граф не ориентирован, то множества А и В совпадают. б) таблица : в первой строке записываются ребра, а во второй строке – инцидентные им вершины. Причем если граф ориентирован, то на первом месте во второй строке ставится начальная, а на вором – конечная вершина. Если граф не ориентированный, то в любом порядке.

3) аналитический {V1,V2,V3,V4,(V2V3),(V4V2),(V4V3),(V3V2)}

4) матричный а) пусть имеем граф, содержащий n вершин и m ребер или дуг. Матрицей инцидентности называется матрица размера n x m(строки х столбцы), элемент которой Aij в случае не ориентированного графа равен 1, если вершина Vi инцидентна j-му ребру, и 0, в противном случае. Aij={1, Vi инц. j ребру; 0, если нет}. Если граф ориентированный, то Aij=-1, если вершина Vi начальная для j-й дуги, =1, если конечная, и 0, если вершина не инцидентна. Замечание: если мы имеем псевдограф(петлю), то в соответствующем месте Aij ставится любое число, отличное от 0 и +-1. б)матрица смежности. Матрицей смежности графа называется матрица n-го порядка(число вершин), элемент которой Aij=1, если есть дуга (vi,vj), и =0 в противном случае. Число единиц в матрице будет равно количеству дуг или удвоенному числу ребер.

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

Граф Н называется подграфом графа G, если множество вершин графа Н есть подмножество вершин графа G, и множество ребер графа Н есть подмножество ребер графа G: VH VG EH EG . Подграф Н называется оставным, если множество вершин VH=VG. Говорят, что подграф Н порожден вершинами VH VG, где VH не пустое, если он содержит те и только те дуги(ребра), оба конца которых принадлежат множеству VH. Очевидно, что если мы имеем матрицу смежности, то чтобы получить матрицу смежности подграфа, порожденного какими-то вершинами, нужно вычеркнуть соответствующие строки и столбцы матрицы исходного графа, тогда на пересечении этих строк и столбцов будет находиться матрица смежности графа, порожденного соответствующими вершинами. Это справедливо и для псевдо- и для мультиграфов.

1. добавление ребра x=(Vi,Vj) в графе G. H=G+x, VH=VG, EH=EG{x}= EG{(Vi,Vj)}. Замечание: ребра добавляются только между несмежными вершинами, иначе получим мультиграф.

2. удаление ребра H=G-(Vi,Vj). VH=VG, EH=EG/{(Vi,Vj)}.

3. удаление вершины H=G-Vi, VH=VG/{Vi}, EH=EG/{x| x – ребра, инцидентные Vi)}.

4. объединение графов GH, VHVG, EHИEG. Обычно полагают, что множества вершин и ребер не пересекаются. В противном случае операция объединения сводится к наложению графов друг на друга.

5. пересечение графов GH. Эта операция полагает, что пересечение вершин – не пустое множество. Тогда получаем граф, у которого пересекаются вершины и пересекаются ребра. VHVG, EHEG.

6. сложение графов G+H, VHVG, EHИEGИ{x=(u,v)|uVG, vVH}, т.е. из каждой вершины первого графа строим ребра к каждой вершине второго графа.
Степени вершин графа.

Назовем граф максимальным (минимальным) по отношению к некоторому свойству, если граф обладает этим свойством, и никакой другой граф, полученный из данного прибавлением (удалением) вершины или ребра, этим свойством не обладает. Назовем степенью i-ой вершины графа G((i)) число ребер, инцидентных i-ой вершине.

2 (1)=1- висячая вершина, (4)=2 -
3 транзитивная.

Очевидно, что сумма всех степеней
1 вершин неориентированного графа дает
4 2n, где n- число ребер. Число ребер такого графа N=1/2d(i) (1). Если граф ориентированный, то вводят степень d-(i) – число выходящих дуг из i-ой вершины, и d+(i)- число входящих дуг в i-ю вершину. Для ориентированного графа число ребер N=d-(i)= d+(i). Назовем в неор-графе вершину нечетной, если d(i)- нечетное число, и четной в противном случае. Змечание: для ор-графа рассматриваем d-(i) и d+(i). Теорема: число нечетных вершин графа всегда четно. Доказательство из формулы (1). Если в формуле (1) удалить все четные вершины, то сумма оставшихся вершин все равно делится на 2. Граф называется однородным, если степени вершин одинаковы. Для ор-графа d-= d+. Если степень каждой вершины k, то число ребер равно N={nk/2 – для неор-графа, nk- для ор-графа}. Граф называется полным, если каждая его вершина связана ребром (дугой) со всеми остальными. Очевидно, что это однородный граф, где d(i)=n-1, поэтому полный неор-граф имеет ребер N=n(n-1)/2, а ор-граф – N=n(n-1).

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

Один и тот же граф можно изобразить по-разному. Есть произвол в расположении вершин и линий, их соединяющих. Рассмотрим два графа:

2 1 1 2 3 4 3 1 2 3 4 Два графа G и

1 0 1 0 0 1 4 1 0 0 0 1 H называются

G 2 1 0 1 1 2 0 0 1 1 изоморфными,

3 0 1 0 1 3 0 1 0 1 если

4 0 1 1 0 Н 2 4 1 1 1 0 существует

3 4 биективное отображение  его вершин :VGVH, сохраняющее отношение смежности, т.е. дуга (ребро) принадлежит множеству ЕG тогда и только тогда, когда
(Vi,Vj)ЕG((Vi),(Vj)) ЕH. Из определения вытекает, что в изоморфных графах одинаковое число вершин, одинаковое число ребер(дуг). Если образ вершины Vi в изоморфном графе Н есть (Vi), то степени их равны. Если две вершины в графе G не смежные, то их образы в графе Н также не смежные. Если графы заданы матицами смежности и они изоморфны, то, производя одинаковые (т.е если переставить местами 1 и 2-ю строки, то нужно переставить 1 и 2 столбцы) перестановки строк и столбцов первого графа, можно получить матрицу изоморфного графа. Чтобы доказать, что графы не изоморфны, нужно выполнить n! перестановок строк и столбцов. Иногда удобней проверит на изоморфность графы через дополнения графов. G- дополнение графа G до полного. Граф G называется дополнением к графу G, если число вершин у них одинаковое (VH=VG), а каждое ребро, если оно Е`G , то оно ЕG. Граф называется самодополнительным, если он изоморфен своему дополнению. Если графы изоморфны, то и их дополнения тоже изоморфны.

Маршруты и пути на графах. Теорема о выделении простого маршрута (пути).

Пусть граф G не ориентированный. Маршрутом называется такая конечная или бесконечная последовательность ребер, что начало каждого следующего совпадает с концом предыдущего. Часть рассматриваемого маршрута называется подмаршрутом. Вершина, от которой начинается маршрут, называется начальной; кончается – конечной. Длиной маршрута называется число ребер в нем. Причем каждое ребро считается столько раз, сколько раз оно явно входит в маршрут. Маршрут, все ребра которого различны, называется цепью(вершины могут повторяться). Цепь, вершины которой различны, называется элементарной. Замкнутая цепь называется циклом. Замкнутая элементарная цепь называется элементарным циклом. Пусть теперь G- ор-граф. Для ор-графа вводятся понятия ориентированного маршрута или нет. Ориентированный маршрут называется путем. Путь, у которого все дуги различны, называется цепью. Элементарная цепь – все вершины различны. Замкнутая цепь называется контуром. Замкнутая элементарная цепь – элементарный контур. Замечание: когда говорят о контуре графа, то считают, что он всегда ориентирован.

Теорема1: из всякого незамкнутого маршрута (пути) можно всегда выделить элементарную цепь с той же начальной и конечной точкой. Доказательство: пусть мы имеем не элементарную цепь, тогда найдется вершина V, кот. инцидентна. Пронумеруем все ребра, инцидентные вершине V. Отсюда следует, что если какие-нибудь вершины V и U соединены цепью, то они соединены и элементарной цепью. Аналогичная теорема имеет место для замкнутых маршрутов и путей. Из псевдографов, мультиграфов(ор. или нет), из всякого цикла (контура) можно выделить элементарный цикл (контур).

Теорема о выделении из всякого замкнутого маршрута (пути) нечетной длины простого цикла (контура) нечетной длины.

Теорема: из всякого замкнутого маршрута (пути) нечетной длины можно выделить простой цикл (контур) нечетной длины. Доказательство: пуст дан граф: 1

1 2-3-4-5-2-5-1-2. Расположим вершины

5 2 замкнутого контура по кругу:

1-2-3-4-5-1. Если все вершины различны,

4 3 то простой цикл (контур) построен.

Пусть теперь некоторые вершины повторяются:

1-2-3-4-5-2-5-1. возьмем вершину, которая повторяется хоты бы два
раза – 2. Очевидно, путь от первого вхождения вершины до второго вхождения замкнутый, и от второго в первое тоже замкнутый. Т.к. весь путь нечетной длины, то из двух полученных циклов (второй – 5-2-5) один обязательно нечетной длины. Выбросим цикл четной длины и проведем аналогичное рассуждение к оставленному циклу нечетной длины. Этот процесс обязательно закончится, т.к. на каждом шаге длина пути уменьшается по крайней мере на 2.


Нахождение числа маршрутов (путей) через матрицу смежности.

Пусть А- матрица смежности n- вершинного графа. А=(aij)n, Al- l-я степень матрицы А. Al=(alij). Теорема: элементы матрицы Al дают число путей (маршрутов) длины l из i-й вершины в j-ю. Доказательство: обозначим число различных путей из i-й вершины в k-ю через aik. Длина этих
i путей- 1. Тогда общее
число путей из i-ой вершины
в j-ю длины 2, проходящих
j m через k-ю вершину, есть
. k произведение. Если мы
просуммируем по всем вершинам k, то получим число всех путей длины 2 из i-й вершины в j-ю. А по определению матриц это есть АА. (i=1 to n)aikakj=AA=A2=(a2ij). Если мы возьмем некоторую вершину m, тогда чтобы найти число путей из i-й вершины в m-ю длины 3, которые проходят через j-ю вершину, нужно найти произведение a2ijajm. Если просуммируем по всем j, то получим общее число путей из i-й вершины в m-ю. (j=1 to n) a2ijajm=A2A=A3=a3ij. и т.д. Очевидно, если при каком-нибудь значении l получим Аl=0, то это будет означать, что и более высокие степени матрицы=0, т.е. в графе не будет циклов(контуров). Если в графе нет циклов, то Аl дает число простых путей(маршрутов) графа между i-й и j-й вершинами.

Необходимое и достаточное условие существования контура ор-графа.

Теорема: для того, чтобы n-вершинный ор-граф имел хотя бы один контур, необходимо и достаточно, чтобы матрица K=A2+ A3+ A4+…+ An (1) имела хотя бы один элемент на диагонали >0 (kij>0). Доказательство: пусть хотя бы при одном i элемент матрицы k>0 (kij>0). Это означает, что в силу условия (1) найдется такое 2<=l<=n, что aii>0, т.е. имеется путь из i-ой вершины в i-ую, значит, имеется и элементарный контур из i-ой вершины в i-ую. Обратно: если найдется элемент a(l)ij>0 в матрице Al, то это будет означать, что существует контур длины l, значит, из него можно выделить простой контур, длина которого не превосходит числа вершин, а тогда 2<=l<=n, следовательно, элемент a(l)ij>0К, т.е. на диагонали матрицы К элемент kii>0.

Связность графа. Отыскание компонент связности при графическом задании графа.

Граф (ор-граф) называется связным (сильно связным), если любая пара его вершин соединяется хотя бы одной цепью.
- сильно связан - слабо связан

Возьмем ор-граф и уберем стрелки, тогда получим неор. граф, о котором говорят, что он ассоциирован с данным. Ор-граф называется слабосвязным, если ассоциированный с ним граф является связным.
Максимально связанный (сильно связанный) подграф данного графа называется компонентой связности (сильной связности).
Очевидно, если граф G имеет Р компонент связности G1,G2,G3,…,Gp, то число вершин графа G равно числу компонент связности. Если граф неор., то число его ребер равно сумме ребер его компонент связности.

Рассмотрим алгорит выделения компонент связности для неор. графа и этот же алгоритм даст возможность определить, будет ли граф связным. Этот алгоритм может работать и для выделения компонент слабой связности графа.

1) возьмем какую-нибудь вершину, 2) запишем все вершины, ей смежные, получим список, 3) к каждой вершине списка пункта 2 присоединяем смежные вершины, причем если вершина уже есть в списке, то ее уже не пишем, список при этом дополняется, 4) к полученным вершинам снова добавляем смежные к ним, не вошедшие в список, и так до тех пор, пока список не будет расширяться. При этом если в список вошли все вершины графа, то граф связный, в противном случае м ы выделим одну компоненту связности. Тогда берем любую вершину, не вошедшую в первую компоненту связности и повторяем алгоритм.

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

Будем говорить, что вершина v достижима из вершины u, если u=v или существует простая цепь из u в v. Пусть G- не ор-граф. Матрицу S называют матрицей достижимости, связности, если элементы ее sij=1 при условии, что j достижимо из i, или i=j, и 0 в противном случае. Иначе говоря, sij?0, если i-я и j-я вершины принадлежат одной компоненте связности. Доказывается, что S=EA*2 A*3… A*n, где А- матрица смежности.
Пусть теперь G- ор-граф. Матрицей достижимости Т ор-графа называется квадратная матрица, Тij=1, если j-я вершина достижима из i-й, и 0 в противном случае. Доказывается T=EA* A*2… A*n-1. матрицей сильной связности зовут матрицу, элементы которой Sij=1, если ViVj и VjVi существует, иначе Sij=0. Т.е. Sij=1, когда вершины Vi и Vj принадлежат одной компоненте сильной связности. Доказывается, что S=TTT, где TT- транспонированная Т. Очевидно, если граф имеет немного дуг, то матрицу связности можно построить по графу.

Рассмотрим алгоритм выделения компонент сильной связности: пусть имеем матрицу смежности А:

0 1 0 1 0 0 построим матрицу сильной связности S: 1 0 0 1 0 0
0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0 1 0 1 1
1 0 0 0 0 0 1 0 0 1 0 0
0 1 0 0 0 1 0 0 1 0 1 1
1 0 1 0 0 0 0 0 1 0 1 1
Алгоритм: 1) вычеркиваем в матрице S солбцы и строки, соответствующие единицам первой строки. Вершины, находящиеся на пересечении вычеркнутых строк и столбцов, дают первую компоненту сильной связности. (1,4). Матрица смежности, соответствующая первой компоненте связности, получается вычеркиванием соответствующих строк и столбцов матрицы А: V1={1,4} 1 (0 1)
4 (1 0),
2) берем вторую строку и вычеркиваем все столбцы и соответствующие им строки, на пересечении которых находятся 1. Вторая компонента связности: V2={2} 2 (0)
3) берем третью строку и повторяем рассуждения. V3={3,5,6} …

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

Пусть G не ор-граф. G(V,E). Расстоянием d(u,v) между вершинами u и v называется кратчайшая цепь, соединяющая эти вершины. Очевидно, что эта цепь является простой. (u,v)- геодезическая. Если граф связный, то d(u,v)<, если не связный, то полагают d(u,v)=. Пусть G связный граф, тогда диаметром графа G называется максимальное расстояние d(G)=max d(u,v) | (u,v)V. Зафиксируем вершину u. эксцентриситетом или максимальным удалением l(u) называется максимум d(u,v):
l(u)=max d(u,v) | vV. Диаметр- это максимальный эксцентриситет. Назовем радиусом графа r(G) минимальный эксцентриситет:
r(G)=min l(u) | uV. Вершины графа, эксцентриситет которых равен радиусу, называются центральными.

Алгоритм отыскания d,r,l:
7 расст-ие 1 2 3 4 5 6 7

1 2

=1 2 1 2 5 3 5 1
4 7 4 3 4 2
4 3 7 3 5 1 6…..
6 =2 3 4 1 6 2 3 4
5 5 5 7 2 1 4 3
6 7
=3 6 6 7 2 5 d(G)=4; r(G)=2
. 1… 3,4- центральные
=4 7 6 вершины.
l(i) 3 3 2 2 3 4 4

Отыскание кратчайших расстояний на графе.

Расстояние между двумя вершинами – это минимальное число ребер в маршруте. Каждому ребру припишем число Cij. Если Cij=1, то алгоритм даст способ отыскания кратчайшей цепи между парой любых вершин. Рассматривая конкретные практические задачи, Cij может быть любым числом, например, если Cij рассматривать как стоимость пути между i-м и j-м пунктом, то здача о наикратчайшем расстоянии интерпретируется как нахождение пути минимальной стоимости между i-м и j-м пунктами. Графы, каждому ребру которых приписано число Cij, называются нагруженными.

Алгоритм: 1) берется вершина графа и находится наикратчайший путь от этой вершины до всех остальных. 2) затем фиксируют другую вершину и находят расстояние от этой вершины до всех остальных. 1!) выбираем вершину k и считаем, что d0(k,j)={0, if k=j; w, if k?j}, w> Cij. d1(k,j)=min{d0(k,i)+ Cij}, где i- множество вершин, непосредственно предшествующих вершине j. d(m)(k,j)=min{dm-1(k,i)+Cij}, iB(j). Алгоритм заканчивает работу, как только d(m)(k,j)= d(m-1)(k,j)= d(k,j). Этот алгоритм дает не только кратчайшее расстояние, но и показывает маршрут, по которому нужно двигаться из k-й вершины в j-ю. Этот алгоритм работает как для ор-графов, так и для не ор-графов, но в случае ор-графа может случиться так, что алгоритм закончил работу, а в некоторых вершинах осталось число w, это говорит о том, что данная вершина недостижима из k-й вершины.


Ациклические ориетированные графы. Теорема о существовании его начальной и конечной вершины.

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

Теорема (о существовании …): у каждого конечного ациклического графа имеется по крайней мере одна начальная и одна конечная вершина. Доказательство: возьмем вершину Vj и найдем все пути, заканчивающиеся в этой вершине. Т.к. граф конечный и ациклический, то существует самый длинный путь. Обозначим этот путь (V0,V1,V2,…,Vn), тогда вершина V0 является начальной. Действительно, если бы V0 не была бы начальной, то существовала бы дуга (VaV0), и тогда бы путь (V0…Vn) не был бы максимальным. Если заменить направление дуг на противоположное, то свойство ацикличности не нарушится, откуда вытекает доказательство теоремы и о существовании конечной вершины.
Ациклический граф, у которого одна начальная и одна конечная вершина, называется направленным. В направленных графах из начальной достижимы все вершины.

Ранги вершин. Правильная нумерация вершин.

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

Алгоритм, позволяющий найти ранги вершин: 1) каждой вершине в порядке введеннной нумерации присваиваем ранг=0: R(0)(j)=0, 2) R(k)(j)=max{R(k-1)(i)+1}, где i непосредственно предшествует k. Алгоритм заканчивает работу, когда R(k)(j)= R(k-1)(j)=R(j).
если у графа мало дуг, то ранги можно находить геометрически.

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

V1 из опреления вытекает, что вершины,

принадлежащие одной доле, не могут

быть смежными.
V2

2 1 3 5 эти графы изоморфны

1 3 название К3,3


6 4

5 2 4 6

Теорема о достаточном и необходимом условии двудольности: Теорема: граф двудолен тогда и только тогда, когда любой простой цикл этого графа имеет четную длину. Доказательство: дан двудольный граф, доказать, что простые циклы его имеют четную длину. Если граф не имеет циклов, то доказательство очевидно. Пусть граф имеет цикл. Возьмем какую-нибудь его вершину, лежащую на цикле. Очевидно, вершина а принадлежит либоV1, либо V2.

V1 если мы от вершины а по ребру придем во множество V1, то пройдем нечетное число ребер, а чтобы из вершины а

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

Покажем, что вершины множеств v1 и V2 между собой не могут быть смежными. Предположим a,b,cV1. Тогда растояние от вершины а до b имеет четную длину. Добавим ребро bc и путь от с к а будет четным, получаем цикл нечетной длины, что противоречит условию. Аналогично доказывается и для множества V2.

Разделяющие вершины и мосты. Теорема о разделяющей вершине. Алгоритм отыскания.

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

G V




V1 V2

Доказательство: удалим из графа G вершину V: G-V и рассмотрим граф G-V. В этом графе вершины V1 и V2 не связаны между собой, т.к. любая цепь, их связывающая, проходит через вершину V. А это говорит о том, что граф G-V не связный, т.е. удалив вершину V, мы увеличим по крайней мере на 2 число компонент связности графа.
Следствие: если существует простая цепь, проходящая через все смежные вершиные с U вершины и не проходящая через U, то вершина U не является разделяющей. Заметим, что разделяющей вершиной не может являться висячая и транзитивная (степень 2) вершина, лежащая на простом цикле.
Аналочичную теорему можно сформулировать и для моста: Ребро Е связного графа G является мостом, если существуют также две вершины графа V1 и V2, что любая простая цепь, их соединяющая, проходит через ребро Е. Очевидно, мост не может лежать на простом цикле.

Рассмотрим алгоритм нахождения разделяющих вершин:

8 7 6 1) отсекаем вершины, которые не могут быть

разделяющими: 4,3,8. 2-3-9-7-6 – вычерк. 2,

9-8-7-6-2-3 – вычеркиваем 9,

9 7-8-9-3-2-6 – вычерк. 7, 1,6,5-? Если не

5 удастся отсечь все вершины, то включаем их в

сомнительные.

2) исследуем сомнительные вершины:

1 2 3 4 удаляем каждую сомнительную вершину и проверяем оставшийся подграф на связность. Если он связный, то вершина не является разделяющей. В противном случае вершина будет разделяющей и мы найдем компоненты связности. 1,5 – очевидно разделяющие. Удаляем 6: G-6 – не связный. {2,3,7,8,9} и {1,5,4}.


Блоки. Достаточный признак. Алгоритм отыскания.

Связный не ор-граф называется неразделимым, если он не содержит разделяющих вершин. Связный неразделимый граф называется блоком, а все его вершины называются внутренними вершинами графа. Теорема: пусть N- число вершин графа >=3. Граф является блоком, если: 1) любые две его вершины принадлежат общему простому циклу, 2) любые два ребра принадлежат общему циклу, 3) любая вершина и любое ребро принадлежат общему простому циклу, 4) для любых двух вершин и любого ребра графа существует простая цепь, их соединяющая. Возьмем произвольный граф, который не является блоком, тогда он разделим на отдельные блоки, каждый из которых является подграфом графа. Блоком графа G, порожденный вершинами U1,…,Ui, называется его максимальный неразделимый подграф, порожденный этими вершинами. Блоки могут соединяться либо по вершинам, которые являются разделяющими, либо с помощью мостов. Алгоритм выделения блока:1) определяем все разделяющие вершины Ui, 2) для каждой разделяющей вершины определяем компоненты связности графа G-Ui. Эти вершины порождают для каждой свои компоненты связности, 3) находим внутренние вершины графа,блока. Для этого рассматриваем все непустые пересечения множеств, полученных в пункте 2, 4) к полученным вершинам добавляем смежные с ними разделяющие вершины, и строим эти блоки, 5) добавляем (если они есть) к каждому блоку недостающие вершины между смежными разделяющими вершинами, 6) полученные блоки соединяем по разделяющим вершинам с добвлением K2 (если они есть).

Определение дерева. Теорема о связи любых его двух вершин.

Не ориентированный связанный граф, не содержащий циклов, называется деревом. Если граф не связан, а каждая его компонента дерево, то граф называется лесом.
Свойства деревьев: 1)в дереве любая пара вершин соединяется единственной простой цепью. (если бы существовала не единственная цепь, то существовал бы цикл, а дерево циклов не имеет). Концевая вершина называется листом. Звездный граф – содержи только концевые ребра.
2) каждое дерево имеет по крайней мере одно концевое ребро и две концевых (висячих) вершин. 3)Теорема (о связи между вершинами и ребрами дерева): пусть имеем дерево, в котором n вершин и m ребер, тогда m=n-1. Доказательство: по индукции: для графа K2 (одно ребро и две вершины) это очевидно. Пусть теорема справедлива для любого числа вершин
Задача о минимальном соединеии, алгоритм получения.

Задача: имеется n пунктов. Имеется стоимость строительства между каждыми пунктами. Требуется эти пункты соединить наиболее дешевой сетью. Это будет дерево. Алгоритм построения min дерева схож с алгоритмом построения оставного дерева. Только здесь нужно выбирать наиболее дешевое ребро. 1) берем любую вершину и смежное к ней самое дешевое ребро (или берем самое дешевое ребро), 2) выбираем самое дешевое ребро, смежное к полученной вершине шага 1, 3) рассматриваем все смежные ребра к вершинам пункта 2, выбирается самое дешевое и с инцидентной ему вершиной, не вошедшей в вершины пункта 2.

Планарность: оновные определения, теорема Эйлера, следствие.

Граф G называется укладываемым на поверхность S, если его можно так нарисовать на этой поверхности, что ребра будут пересекаться только в вершинах. Граф называется планарным, если его можно уложить на плоскости. Всякая укладка на плоскости называется плоским графом. Пример: полный граф К5 никогда не будет плоским.
Часть пространства называетс гранью графа, если любые две внутренние точки можно соединить непрерывной линией, которая не пересекает ребер и вершин. Неограниченная часть пространства называется внешней гранью. Если взять дерево, то оно имеет только внешнюю грань.
Теорема: Пусть имеем связный плоский граф, у которого n вершин, m ребер и r граней (включая внешние), то n-m+r=2 (1). Эквивалентная теорема: если не выполнимо (1), то граф не является планарным. Доказательство: пусть имеем связный плоский граф. Построим его оставное дерево. У дерева r=1, m=n-1, тогда n-m+r=n-n+1+1=2. Будем восстанавливать дерево. Очевидно, что если мы ребром соединим две концевые точки, то внешняя грань уберется, появляется внутренняя и чесло ребер увеличивается на 1. если соединим две внутренние точки, то число внутренних граней +1 и число ребер +1.
Следствие: если каждая грань плоского графа ограничена простым циклом длины p, то p*(n-2)/(p-2). Доказательство: решив систему уравнений {pr=2m; n-m+r=2}, полчим данное уравнение. (стоит проверить). В качестве примера приводится граф с p=3, n=4.
Максимальный плоский граф. Основные соотношения. Геоморфизм. Теорема Понтрягина-Куратовского.

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

вершин и m ребер, то каждая его

грань является треугольником,

причем m=3n-6. Если G плоский граф,

у которого каждая грань цикл длины U, то

m=2n-4.

Доказательство: если G содержит грань, не являющуюся треугольником, то найдутся хотя бы 2 не смежные вершины, которые можно соединить ребром, хотя это противоречит тому, что граф максимально плоский. Если G произвольный плоский граф, то m<=3n-6. Если G блок, не содержащий треугольников, то m<=2n-4. Отсюда вытекает, что граф К5 не является планарным. n=5, m=10 3n-6=9, т.е. граф не является планарным.

Геоморфизм: Разбиением ребра UV называается помещение на ребре транзитивной W, которая делит ребро на два. Если граф G получен из графа Н разбиением, то граф G называется разбиением графа Н.
Графы G и H называются геоморфными, если можно осуществить такое разбиение этих графов, что получим изоморфные графы.











Т. Понтрягина-Куратовского: Граф G планарен тогда и только тогда, когда в нем нет подграфов, геоморфных К5 и К3,3.

Т: граф планарен тогда и только тогда, когда планарен его блок.

Множества. Основные понятия. Способы задания
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации