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

приобрести
Шпоры по дискретной математике
скачать (130.5 kb.)
Доступные файлы (1):
n1.doc131kb.06.07.2012 23:21скачать

n1.doc

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

Объект рассм-ния – неор.граф. Гр-ый вектор неор.графа - в-р, компоненты кот. равны степеням вершин графа, распол-ым в пор. невозрастания.

Т. Есть вектор П=(d1,d2,…,dp), где p-1>=d1 >=…>=dp. Вектор П явл. графом т. и т.т., когда сущ. вектор П’=(d-1, dd1+1-1, dd1+2-1,…,dp) или получ-ый из него перестан-кой комп-тов. Т.е. есть вектор(5,4,4,3,2,2,2)1)(3,3,2,1,1,2){перестан.}. 2)(3,3,2,2,1,1). Если 1)соотв. граф, то и 2 соотв. граф. Док-во: Пусть П’-графовый вектору соотв. граф: Надо док-ть, что (d1,d2,..,dp)тоже графовый. Добав. вершину и соед. её с верш.Пусть П’ или его перестан.-граф.вектор (4,4,3,2,3,2).Исх.вектор был такой (5,5,5,4,3,4,2).Обратное рассужден. Пусть п-графовыйнадо док-ть, что П’-граф.,но может .Пусть d1 смежна с верш.со степ.di и не смеж.с верш.степ.dj,где dj>di.dj>diсущ. верш.с ном.k,кот.смеж.с с j верш.и не смеж.с i.Продолжая проц.,получ.П’.
2.Критерий сущ-ия обратного отоб.

Т. Чтобы отобр.f имело обратное: f:AB имело f -1: ВА необх.и дост.,чтобы оно является.взаимоод. соотв-ем. Док-во. Пусть f имеет обратное отобр.f -1 . 1)f(f -1(B))=b.Пусть f -1(b)=a.f(a)=b,т.е.f(A)=B.2) f(a1)=f(a2). f -1(f(a1))= f -1(f(a2)). Пусть отобр-ие f взаимоодн. f:RR. f(x)=x2. f:=RR (график параболы).
3.Критерий Эйлеровости графа.

Цикл в гр.наз.эйл.,если кажд.дуга вход.в него 1 раз.Цепь наз.эйл.,если кажд.дуга в гр.вход.в него 1 раз.Граф наз.эйл.,если в нем сущ.эйл.цикл.Граф наз.полуэйл.,если в нем сущ.эйл.цепь. Т. Для связ.неорграфа равнос.:1-граф Г-эйл.,2-Степ.всех верш.-чет.,3-существует.кон.число простых цик-лов таких,что кажд.дуга вход.только в 1 цикл. Док-во.Докажем 1231. 12. Граф Г-эйл.Нарису-ем эйл.цикл,выберем люб.вер-ну.Всякий раз вхо-дим и выходим из нее по разн.дугам.Т.к.цикл эйл., по кажд.из дуг,инцид.данной верш.,мы д.пройти. Сколько входов,столько выходов,все дуги исчерп. степ.чётная. 23. Степ.четные,граф связ.и неор. степени>1.Возьмем произв.верш-у и инцид.ей дугу. Так до тех пор,пока какая-то верш. не повтор.Удалим из графа цикл.Полу-чим,что у получ.графа степ.вер.-чет. 31. 1-2-3-4-1,1-5-3-1,1-2-3-4-1-5-3-1.
4.Несущ-ие мн-ва макс.мощности.

Т. Мощн.мн-ва M меньше его булеана.|M|<|B(M)|. Самого макс.множ.не существует. Док-ть: 1).|M|<=|B(M)|.Возьмем люб.эл-т a{a}из мн.M. Bє(ш,{a},{ab})Значит, мн-во М не превосх.Мощн. В(М).2).|M|<>|B(M)|.Пусть это не так и сущ. f:MB(M)..Выберем эл-ты все а,кот.не вход.в f(a). T={a:a не вход.f(a)},TєB(M). T=f(b),bєM.1-пусть bєT,значит b не вход.f(b) єT.2-b не прин.T,значит bє f(b) єT. Пришли к противореч.Значит,(|M|<>|B(M)|.
5.Несчет. множеств вещест.чисел…

Счет. наз. мн., равномощ. мн-ву нат. чисел. Объед.счетного сем-ва счет.мн-в явл.счет.мн-вом.

{а11,а12,а21,а31,а22,а13…}

Рац.число=отнош.двух целых чисел p/q.(a,a+E).Возьмем та-кое q,что 1/q6.Прав.нумерация вер.ацикл.графа

Ацик.граф-ор.граф без цикла.Нумер.вер.наз.прав., если из сущ-я дуги (Vi,Vj)i Будет вер.,из кот.не исход. дуга(сток).Выкинем ее со всеми инцид. дугами.Останется граф с р-1 вер.,по индукции в нем сущ.прав.нумер.вершин.Добавим р верш.
7.Равномощ-ть как отнош.эквив-ти

Отн-ие равномощ-ти мн-в есть отн.эквив-ти. Док-ть: f:AB-взаимоодн-но.Рефл-ть:f:AA? F(a)=0 iA. Сим-ть:f:AB -->f-1:BaA.Тран-ть: (A,B) (B,C)f:AB-взаимоод-но, g:Bc-взаим-но.fog:AС-взаим-но. Мощн мн-ва А не превосх.Мощ.мн.В, если в мн.В сущ.такое подмн-во В1, что А и В равном-ны.|A|=|B|-равн-ны.
8.Свойства деревьев.

1)Верш.степ.1 наз.висящей.Во всяк.дер.,сод.>1 вер.есть вис.верш.Док-во:Будем измер.расст.м/у парами вер.числом дуг.Выделим самое больш.расст.Vн,Vк –внр.сам.больш.расст. Допустим,что из Vн есть еще одна дуга. Тогда в графе есть цикл и он не явл.дер.Во всяк.дер.есть хотя бы 2 вис.верш. 2)Люб.2 вер.дер. соед-ся единст.путем(т.к.граф связ.).Дерево:неор., связ.,отсут.циклов.Чтоб связ.неор.граф.явл.дер., необх.и дост.,чтоб q=p-1.Док-во:Пусть Г-дер.Если р=1,2-очев-но.Пусть это так,когда р=n(т.е.q=n-1). Пусть n+1 вер.У дер.есть вис.верш.Если ее отки-нуть,то оставш.будет дер-м с n вер и (n-1)дуг.Т.е. у исх.дер.n+1 вер.и n дуг.
9.Сравн-ие мощн.как отн-ие поряд.

Если |A|=|B|,|A|=|A’| , |B|=|B’|,то мощн. A’не пре-восх.мощ.B’.Док-во:B1’=h(B1).gofoh : A’B1’ причем взаимооднн.,т.к. g-также взаимоодн.соотв.,т.е.B’ найд-ся кус-к,кот.отобр.A.Отн-ие нестрогого порядка.Реф-ть:мощ.А не прев.мощ.А.Тран-ть: Если мощн.А не прев.мощ.В и В не прев.мощн. С,то мощ.А не прев. мощ.С..С2=g(B1), fog:Ac2 взаи-моод.отобр.Антисим-ть:.А посред-ством f отобр-ет какую-то часть B(B1).В поср-вом g отобр.какую-то часть B на A.Мощн.А не превосх.мощн.В.|A|<=|B|.
10.Структура центра дерева

l(V)-эксцентриситет верш.l(V)=max d(U,V),d-расст.,U,V-верш.r(Г)-рад.графа,r(г)=min{l(V)}, d=max{l(V)}.Центр графа-мн-во таких верш.V, эксцен-т кот.совпад.с рад.графа.{V:l(V)=r(l)}. Нарис.примеры.У люб.дер.центр сост.из 1 или 2 смеж.верш.Эксц-т уменьш-ся на 1,если мы удал.из дер.все висящ.верш.с соотв.дугами.В конце кон-цов мы придем к 1 или 2 верш.,кот.явл.центром.
11.Сумма степ.вершин ор.и неоргр.

Степ.верш.в неорюграфе наз.число дуг,инцид.этой верш.?dlg Vi=2q (i=1,p),p-число вер.,q-число дуг..Для истока dlg+Vi=0,для стока dlg-Vi=0. .?dlg+Vi=?dlg -Vi=q.
12.Счетные мн-ва и их свойства

Счет.наз.мн.,равномощ.мн-ву нат.чисел.Пусть а1є A, А-бескон.1)A\{a1}-бескон.,2)a2єA\{a1}, 3)a3єA\ {a1,a2}…Мы делим мн-во(а1,..,аn,…)-счетн.мн-во. 1-Во всяком бескон.мн-ве есть счет.подмн.Док-во: 2- Объед.счетного сем-ва счет.мн-в явл. счет.мн-вом.3-Всякое бескон.подмнож.счет. мн-ва явл. счет.4-Мн-во рац.чисел плотно во мн-ве вещ. чисел.5-для того,чтоб мн-во было бескон., необх.и дост.,чтобы оно было равном. некот.своей части.
13.Теорема Дирака

Пусть степени всех верш.неорграфа >=p/2,тогда граф явл.гамильт.Обратное неверно.Док-во.Пусть это не так,т.е.сущ.граф Г,степ.всех вер.>=p/2,но он не гам.Значит,граф не яв-ся полным(каких-то дуг не хват.)Будем доб-ть дуги.Если граф гам.,то дугу убираем.Если не гам.,то доб.др.дугу и т.д.пока граф не стан.гам.Степ.вер.растут(>=p вып-ся). Пусть дуга(чтоб граф стал гам.)соед-ет V1 и Vp.треуг. -те верш.,кот.смежны с Vi (их не меньше,чем p/2). квадрат-те верш.,кот.предшеств.треуг.Треуголь-ников>=p/2,квадратов>=p/2.Вершин не помеч. квадратом <=p/2,без i

=p/2,а вершин,не помеч.квадратом

14.Теорема Кэли

pp-2-различных неизоморфных дер.
15.Теорема об отн-ии эквивал-ти

Бинар.отн-я,кот.явл.рефл.,сим.,транз.,наз отн. эквив-ти.Напр,быть соседями.Если G-отн.экв-ти на мн-ве М,то мн-во М пред-мо в виде объед-ия попарно непересек.мн-в таких,что a~b тогда и т. тогда,когда эти Эл-ты попадают в одно мн-во.Мн-во М=M1UM2U..UMnU..;Ga={b:a~b}.1)UGa=M (под знаком U написать а);a~a; a є A.Значит,кажд. эл-т в какое-то мн.попадет.2)Докажем,что если GaGb<>ш,то Ga=Gb.Пусть с є GaGb;d є Ga; Значит,dGb.Так же Gb є Ga.Значит Ga=Gb. 3)Пусть a~b.b є Ga,a є Gaa и b попали в одно мн-во.4)Пусть b є Ga,c є Ga.Получ. a~b,a~cb~c.

16.Теорема Холла

Для того,чтобы в двудол.графе существовало остовное паросочетание, необх.и дост.,чтобы для люб.е паросочетание А1А выполнялось |Г(А1)|>=|А1|.Док-во:1)Пусть остов.паросоч.сущ. Если Г‘(А1)-число смеж.верш.из паросочетаний, то вып-ся св-во |Г(А1)’|>=|A1|.Значит,в исх.графе |Г(А1)|>=|Г’(А1)|=|A1|.2)Пусть указ-е св-во вып-ся т.е. для люб. А1А |Г(А1)|>=|A1|

Док-ть, что сущ. Ост-е парос-е Индукция по числу вершин |A|=|B|=1

Пусть это доказано для |A|=|B|
Надо разбить на 2 случ. а)для всяк мн-ва А1А, А1<>А |Г(А1)|>|A1|


здесь будет вып-ся |Г(А1)’|>=|A1| и здесь осталось вершин в А1(n-1) т.е. |A|=|B|
Б)Сущ такое мн-во А', А'<>A; |A'|=| Г(А')|
Рассм. Ту часть что осталась(A'')

A''=A-A’ B”=B\Г(А’) возьмем А2А'' Г''(A2)=Г(А2)?B'' (т.е. не вошли в Г(А’))

Берем А2UA’по ус-ю|Г(А2UA’)|?|А2UA’| |Г’’(A2)UГ(А')|=|Г’’(A2)|+|Г(А')|т.е. |Г’’(A2)|+|Г(А')|?|A2|+|A’| т.к. |Г(А')|=|A’| то Г’’(A2)|?|A2| след-но в том,что ост-сь тоже вып-ся св-во
17.Число эл. мн-ва подм. конеч. Мн

Счет. - мн-во, равномощ. мн-ву натур-ых чисел.

Т. Всякое бескон. подмнож. счет. мн-ва явл. счет.

Док-во: А-счет. ВА. В-беск.  СВ, С-счет. |C|<=|B|, а |B|<=|A| при том, что А и С -счетн. |A|=|C|, значит, мощн. В совпад. с мощн. А и С. |В|=|А|=|С|и т.д.
1.Критерий графовости вектора.

2.Критерий сущ-ия обратного отоб.

3.Критерийй Эйлеровости графа.

4.Несущ-ие мн-ва макс.мощности.

5.Несчет. множеств вещест.чисел…

6.Прав.нумерация вер.ацикл.графа

7.Равномощ-ть как отнош.эквив-ти

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

9.Сравн-ие мощн.как отн-ие поряд.

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

11.Сумма степ.вершин ор.и неоргр.

12.Счетные мн-ва и их свойства

13.Теорема Дирака

14.Теорема Кэли

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

16.Теорема Холла

17.Число эл. мн-ва подм. конеч. Мн


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