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

приобрести
Шпоры по дискретной математике для МИЭ
скачать (168 kb.)
Доступные файлы (1):
n1.doc168kb.06.07.2012 22:11скачать

n1.doc

1)Критерий графовости вектора

(Рис.)

(5,4,3,3,3,2,2)

(a1,a2,a3,…,an) причем a1>=a2>=a3>=…>=an

a1<=n-1

Th: Для того, чтобы вектор (a1,a2,a3,…,an) (*)

являлся графом необходимо и достаточно, чтобы вектор (a2 -1,a3 -1,…,aa1+1-1, aa1+2-1, aa1+3-1,….,an-1)(**) также являлся графом

(5,5,4,4,4,3,3,2)


(4,3,3,3,2,3,2)

Док-во:

1)(Рис.)

2)(*)-графовый

(Рис.)

Повторив эту процедуру несколько раз мы получим граф с графовым вектором(*), в кот. вершина со степенью a1 смежна с вершинами со степенями (a2,a3,…,aa1+1)


2)Критерий существования обратного отображения

Теорема. Для того, чтобы отображение f: А?В имело обратное, необх. и дост., чтобы f было взаимнооднозначным соотв-м f-1

  1. Пусть f-1 сущ-ет

а) bЄB f-1(b)

f(f-1 (b))=b f(a)=b a1=a2

значит отображение f является взаим. однозн. Соответв.

  1. Пусть отображение f взаимоднозн.



f(a)=b f-1(b)
3) Критерий эйлеровости графа.

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

Теорема: для связного неориентированного графа равносильны 3 свойства:

1)граф эйлеров;

2)степени всех вершин четные;

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

Док-во:

1=>2: Пусть Z – эйлеров цикл. Двигаясь по Z, будем подсчитывать степени вершин, полагая их до начала прохождения нулевыми. Прохождение каждой вершины добавит 2 в степень этой вершины. Т.к. Z содержит все ребра, то когда обход будет закончен, будут учтены все ребра, а степени всех вершин – четные.

2=>3: Пусть у связного неориентированного графа степени всех вершин четные. Этот граф не является деревом => он содержит хотя бы один простой цикл. Удалим из графа этот цикл. Степени всех вершин уменьшились на 2 => у всех вершин опять степени четные. Продолжая этот процесс, разобьем дуги на конечное число циклов (т.е. пока граф не будет пуст).

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


4)Несуществование мнжества максимальной мощности.

Теорема.(Кантора) Не существует множества

максимальной мощности, т.е.|N|<|[0,1]|.

Примечание. 0, a1, а 2,…,аn - это есть десятичные знаки

(9/10)+(9/100)+(9/1000)+…=(9/10)/(1-(1/10))=1

Док-во:

Докажем , что: 1) |N| < |[0,1]|;

2)|N| ? |[0,1]|;
1)1? 1

2? Ѕ {1/n}

3? 1/3

Т.е. во множестве вещественных чисел есть

равномощная часть в натуральных числах.

2) Применяется диоганальный метод Кантора.

Пусть на самом деле они равномощны, т.е. f : N? [0,1]

Существует функция f , являющаяся взаимно однозначным

соответствием:

f(1)= 0, a11, а 12, а 13,…,а1n,…

f(2)= 0, a21, а 22, а 23,…,а2n,…

f(3)= 0, a31, а 32, а 33,…,а3n,…

…………………………….

f(n)= 0, an1, а n2, а n3,…,аnn,…

…………………………………………….

Если нам удастся найти число из отрезка [0,1], которое

не учавствует в этом множестве, теорема будет доказана.

1, если аnn ? 1

b n {

2, если аnn = 1

0, b1, b 2,…,bn……………

b ? f(1)

Теорема. Для всякого множества М, |M|<|B(M)|.

Док-во:

Докажем что:

  1. |M|?|B(M)|;

2)|M|?|B(M)|.

  1. a Є M, {a} ( M

{{a}:aЄM}=M1,

M1 ( B(M)

a?{a}

Значит в булеане мы нашли такое подмножество,

которое равномощно М.

2) Пусть |M|=|B(M)|, тогда существует f : M ?B(M)

М М

Итак, пусть T = {a: a Є f(a)}

Существует b Є M: f(b)=T

Пусть b Є T

b Є f(b)=T

?

b Є T

b Є f(b)=T

?

Исходное допущение неверно, т. е. |M|?|B(M)|.


5) Несчетность множества вещественных чисел. Счетность множества рациональных чисел.

Множество M называется счетным, если оно равномощно множеству натуральных чисел.

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

Док-во: Предположим, что оно счетно и существует его нумерация. Расположим все числа, изображенные бесконечными десятичными дробями, в порядке этой нумерации:

0,a11a12a13 ...

0,a21a22a23 ...

0,a31a32a33 ...

.......................

Рассмотрим любую бесконечную десятичную дробь 0,b1b2b3..., такую, что b1 ? a11, b2 ? a22, b3 ? a33 и т.д. Эта дробь не может войти в указанную последовательность, т.к. от первого числа она отличается первой цифрой, от второго числа – второй цифрой и т.д. =>все числа из интервала (0,1) не могут быть пронумерованы, и множество всех действительных чисел интервала (0,1) несчетно.

Счетность множества рациональных чисел: Q – множество рацион. чисел – p/q, где p и q – натуральные числа, т.е. p, q Ђ N. => множество рациональных чисел Q счетное.

Q 1 = {p/1}, Q2 = {p/2}, ... , Qq = {p/q}, ...

Каждое из этих множеств является счетным => Q = Q 1 U Q2 U ... U Qq U ... А объединение счетного семейства счетных множеств является счетным множеством. => множество Q является счетным

7) Равномощность как отношение эквивалентности.

Опр.: множество A равномощно множеству B, если существует взаимнооднозначное соответствие f: A?B

Теорема: «A равномощно B» есть отношение эквивалентное на совокупности множеств.

Док-во: 1) рефлексивность – отношение, iA:A?A (например, отношение ? и «иметь общий делитель» рефлексивны; отношение < и «быть сыном» - антирефлексивны; отношение «быть симметричным относительно оси x» не является ни тем, ни другим)

2) симметричность – отношение, когда f: A?B, f-1:B?A (например, отношение «быть симметричным относительно оси x» симметрично, т.е., если 1-ая точка симметрична второй, то и 2-ая симметрична 1-ой; отношение ? - антисимметрично)

3)транзитивность – отношение, f: A?B – взаимноодн.; g: B?C – взаимноодн.; f°g:A?C – взаимноодн. ( например, отношения «равенство», ?, «жить в одном городе» транзитивны, отношение «быть сыном» - нетранзитивно).

Следовательно, |A|=|B| - эквивалентность, равномощность.

8) Свойства деревьев.

Лес- это неориентир-й граф без циклов.

Дерево- это связанный лес.

(Рис1)



  1. неориентированность

  2. связность

  3. отсутствие циклов(ацикличность)

Висячими наз-ся вершины, степень которых =1(лист)

У всякого дерева, у кот-го не менее 2-х вершин, есть хотя бы 2 висячие вершины.

(обратной связи у этого свойства нет)(Рис)

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

Пусть U и V те вершины, расстояние м/у которыми самое большое в этом графе и эти вершины висячие.

Д-во: пусть это не так.

От V до W есть дуга, тогда V не висячая.

(Рис2)

Если вершина не является висячей, то она инцидентна ещё одной дуге. Тогда сущест-ет ещё одна дуга, соединяющая W и U. А это цикл.

(рис.3)



p=1, q=0 /

p=2, q=1 /=> q = p-1

p=4, q=3 /

Число дуг на 1 меньше, чем вершин.

Th: для того, чтобы связный, неориентированный граф является деревом, необходимо и достаточно q = p-1

Пусть граф является деревом

p=1 q=0

пусть это так для всякого дерева, кот содержит p вершин

***

рассмотрим дерево Г, у которого р+1 вершин,

у графа есть висячие вершины

отсекаем дугу вместе с вершиной

(рис)
Рассмотрим то, что осталось, докажем, что это дерево. У этого дерева р вершин q= p-1

q=p=(p+1)-1

Число дуг меньше числа вершин что и требовалось док-ть Обратная теорема: пусть Г связный, неориентированный граф, у которого q= p-1.

Пусть это не дерево(в нем есть цикл)

(рис.)

1.



k вершин

k дуг

k =р

***

2.k < р

k +1 вершина

k +1 дуга


9)Cравнение мощностей как отношение порядка

Теорема. Отношение мощности А не превосходящее мощность В есть отношение нестрого порядка на классах равномощных множеств.

1.Рефлективность – мощность А не превосходит мощность А

А1-А iA: А?А

2.Транзитивность – мощность А не превосходит мощность В, мощность В не превосходит мощность С



f: A?B1 g: B?C1 C2=g(B1) f0g: A?C2

Мощность А не превосходит мощность С

1


)
Антисимметричность – мощность А не превосходит мощность В

Мощность В не превосходит мощность А



│А│< = │В│ мощность А не превосходит мощность В

│А│ < │В│

10)Структура центра дерева.

Теорема:Центр любого дерева может состоять либо из одной вершины, либо из 2-х смежных вершин.

Док-во: удалим из дерева все весящие вершины, вместе с висящими дугами. Эксцентриситет уменьшился на 1.Центр нового дерева совпадает с центром старого.
11)Степенью вершины графа deg V неор. Графа наз-ся число дуг инцидентных вершине

? deg V = 2Q

1,2,2,3,4,5 – такого графа нет.

deg V=0, значит граф изолированный

deg +V-полустепень входа, у скольких вершин она является конечной

deg –V- полустепень выхода, у скольких вершин она является начальной

?deg+V = q

?deg-V

deg+V=0, то вершина-исток

deg-V=0,то вершина-сток
12)Счетные множества

{комментарий: Ђ-это вместо знака принадлежности элемента к мн-ву }

Опр: Множество М наз-ся счетным, если оно равномощно множеству натуральных чисел.

Множество счетное- бесконечно!!!

0, 1, -1, 2, -2, 3, -3….. n/2, при n-четн.

f(n)= -(n-1)/2, при n-нечетн

1, 2, 3, 4, 5, 6, 7…..
Th: Всякое бесконечное множество содержит счетное подмножество.

Док-во: пусть М- бесконечн.

а1 Ђ М

а2 Ђ М\ {a1}

а3 Ђ М\ {a1,a2}

………

{a1,a2, a3,….,an,….}

Th: Всякое бесконечное подмножество счетного множества, является счетным.

А-счетное мн-во

ВСА – бесконечное

С СВ– счетное

/С/=
/С/=/A/ значит В –равномощное

Th: Объединение счетного семейства счетных множеств, является счетным множеством

A1={a11,a12.a13,a14,….}

A2={a21,a22.a23,a24,….}

A3={a31,a32.a33,a34,….}

A4={a41,a42.a43,a44,….}



f(n)={ai(n),j(n) }
получаем:


Q= p/q, p,q-натуральные числа

Следствие: множество рациональных чисел счетное

Q1={p/1}, Q2={p/2},……. Qq={p/q},

Q=Q1UQ2U…UQq

Мн-во рациональных чисел яв-ся счетным

Q-плотно в мн-ве вещественных чисел

(a,b)

В любом интервале (a,b) обязательно расположены рациональные числа

М- конечное множество М1 С М , М М, /М1/
Th: Для того, чтобы мн-во М было бесконечны необходимо и достаточно, чтобы:

М1С М ,

М М,

1/=/M/
1)у конечных множеств таких частей нет

пусть множество М бесконечное => по Th 1 у него есть счетное подмножество

A={a1,a2.a3,…an,….}

(Рис.) ai+1, если m=ai

f(m)=

m, если mA

Th: /B(N)/=/[0,1]/

0,10100101…

{1,3,6,8,…}Ђ B(N)

A Ђ B(N)

F(A)

Не существует множества максимальной мощности.

Для всякого множества М

1)/М/=/В(M)/

2)/М//В(M)/

Док-во

1)а C М {a} C M

M1={{a}: а Ђ М }

M1C B(M)

a->{a}

2) )/М/=/В(M)/

f:M->B(M)

(Рис.)

T={a: af(a)}C M

Сущ-ет b = M:f(b)=T

1)B Ђ T

B f(b)=T;

2) B T

B Ђ f(b)=T;
Значит, не равномощны, что и требовалось доказать


13)Терема Дирака. (1952)

Пусть в связ. неор. графа степени всех вершин p\2, где р- число вершин, тогда граф гамильтонов. Deg Viр\2.

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





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

С треугольными вершинами р\2; без квадр. –р-р\2=р\2. с  верш.р\2. есть  смежные с р. р с 5, 1 с 6 получаем гам. цикл. Противоречие.
14) Торема Кэли.

(по лекции гр. ПИЭН)

Теорема Кэли о числе различных помеченных деревьев.

Различных помеченных деревьев с p вершинами всего

существует pp-2 (шт.)

Док-во: используем код дерева: дерево с p вершинами

однозначно кодир-ся с помощью кода из (p-2) чисел,

след-но кол-во различных кодов будет =0.

(по лекции)

Код – (p-2) числа от 1 до p

Сколько сущ-ет различных помеченных деревьев

с p вершинами?

1-p 1-p 1-p … 1-p




1 2 3 p-2

сущ-ет pp-2 помеченных деревьев с p вершиной.

На основании основного принципа комбинаторики.

p1 , p2 , p3 , …, pp-2 .

15)Теорема об отношении эквивалентности.

Отношение называется отношением эквивалентности,

если оно рефлексивно, симметрично и транзитивно.

(по лекции) Т. [a~b] Пусть G – отношение эквивал-ти на множ-ве М,

тогда M=M1 U M2 U U M4 …, где множ-во Mi попарно не пересекается

и a~b тогда и только тогда, когда a, b Є Mi .

Док-во:

Ga ={b Є M b~a} (есть такое множ-во b Є M, где b~a )

1)Если возьмем a , то a~a (рефл.,транзит.,симм.)

значит a Є Ga

2)Ga и Gb .

Ga ? Gb ? 0 => Ga = Gb

Если они пересекаются по одному элементу, то этого

достаточно чтобы они были равны.

c Є Ga ? Gb d Є Ga

c ~ a, c~b, d~a

d~a, a~c, c~b

d~c c~b

d~b => d Є Gb

Ga ЄGb, Ga и Gb равноправны

3)a~b => a Є Gb

b Є Gb

4) c, d Є Ga мы должны док-ть что два этих

элемента эквивалентны

c~d, a~d
16)теорема Холла.

Пусть G(V1,V2,E)- двудольный граф.совершенное паросоч. Из V1 в V2 существует тогда, когда А V1 АГ(А).

Доказательство. Необходимость.пусть сущ.соверш-ое парос-ие из V1 в V2. Тогда в Г(А) входит А вершин из V2.парных вершинам из А и, возможно, еще что-то. Таким образом, АГ(А).

Достаточность. Добавим в G две новые вершины u и v, так что u смежна со всеми вершинами из V2. Совершенное паросочетание из V1 в V2 существует тогда и только тогда когда,когда существуют V1 вершинно- непересекающихся простых u,v цепей.(рис). Ясно, что Р(u,v)V1 (т.к. V1 разделяет u и v).



по теореме Менгера maxР(u,v)=minS(u,v)=S, где S наименьшее множество, разделяющее вершины u и v. Имеем SV1.покажем, что SV1. Пусть S=AՍB,AV1,BV2. Тогда Г(V1\A)B. Действительно, если бы Г(V1\A)B, то существовал бы «обходной» путь u,v1,v2.v, и Sне было бы разделяющим множеством для u и v. Имеем:  V1\A Г(V1\A)В. Седовательно, S=А+ВА+V1\A=V1.

17) Число элементов множества подмножеств конечного множества.

Опр.: Булеаном множества А называется множество всех подмножеств множества А.

Пусть A={a}; ?B(A)={ǿ,{a}}.

B(A)={ǿ,{a}, {b}, {a,b}}, если A={a,b}.

Пусть A={a,b,c}, тогда B(A)={ǿ,{a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}}.

Теорема: Если множество А – конечное, то число элементов булеана множества А есть 2|A|, т.е |B(A)|=2|A|.

Док-во: A={a1,a2,…,an}. Рассмотрим множество И(А) двоичных векторов из 0 и 1 длины n. Каждому подмножеству А*?A поставим в соответствие вектор v=(v1,…,vn) Ђ B(A);

vi= {0, если ai не Ђ A*;

{1, если ai Ђ A*

Установленное соответствие между мн-вом всех подмн-в А и двоичными векторами длины n является взаимнооднозначным и число подмн-ва А=|B(A)|. А т.к B(A) является прямым произведением n 2-хэлементных мн-в {0,1} то следовательно |B(A)|=2n?|B(A)|=2|A|


c~d.

1) Критерий графовости вектора
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации