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

приобрести
Шпоры по дискретной математике
скачать (212.2 kb.)
Доступные файлы (1):
n1.docx213kb.08.07.2012 21:39скачать

n1.docx



Множества и функции

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

Объекты, объединенные одним общим свойством, называют эле

ментами множества и обозначают a, b, c, ... x, y, z. Множества обозначают A, B, C, ... X, Y, Z. Запись a? A означает, что элемент "a" принадле-

жит множеству А, b?A означает, что элемент "b" не принадлежит множеству А.

Множество U , которое содержит все рассматриваемые нами в данный момент множества называется универсальным множеством.

Множества задаются различными способами:

1)С помощью перечисления всех его элементов.{0,1,2,3,4,5,6,7,8,9}

2)Алгоритмическая форма (в виде последовательности или фомул).

а) конечное М={2;4;6;8} <=> М={m|2n;n-целое;1<=n<=4}

б) бесконечное А={х| |х-1|<3}

Если каждый элемент множества А есть в месте с тем элемент мно-

жества В, то множество А называется частью, или подмножеством мно-

жества В и обозначается А?В.

Если А?В и В?А, то множества А и В называются равносильными

и обозначаются А=В.

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

Пусть А и В - произвольные множества. Их пересечением называется множество

АВ={x| xA и xB}.

Объединением множеств А и В называется множество

АВ={x|xA или xB}.

Разностью множеств А и В называется множество А\В={x|xA, но x B}.

Используя понятие универса, можно ввести еще две операции над множествами - дополнение и симметрическую разность множеств.

Дополнением множества А (до универса J) называется множество =J\A, т.е. ={x| xJ, но xA}.

Симметрической разностью множеств А и В называется множество

АВ=(A\B) (B\A).

Если АВ=, то говорят, что множества А и В не пересекаются.

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

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

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

Мощность множества

Число элементов конечного множества M называется мощностью множества M и обозначается |M|, если |A|=|В| - множества равномощные.

Булеан:

Опр: Множество всех подмножеств множества А наз. булеаном А (степень множ. показатель множества) , обозн.

Теорема: Число подмножеств конечного множества состоящего из n элементов равно .

Док-во: (по индукции) Пусть утверждение справедливо для n=0. Пусть утв. верно для n, и пусть множество мощности n+1. Зафиксируем некоторый элемент множества М - и разделим подмножества множества М на 2 типа: 1) сод. 2) без . Подмножеств второго типа по предположению индукции , а подмножеств первого типа столько же, т.к. подмножества первого типа получаются из подмножеств 2го типа добавлением подмножеств первого типа тоже поскольку эти множества не пересекаются .

Прямым произведением множеств А и В называется множество М всех пар (), таких, что

Теорема: мощность произведения .

Док-во: первый элемент пары можно выбрать числом способов, а второй элемент числом способов. Т.о. у нас имеется упорядоченных пар.

Отношения на множествах

Определение. Упорядоченной парой называется совокупность, состоящая из двух элементов x и y, расположенных в определенном порядке.

Определение. Две пары считаются равными тогда и только тогда, когда x=u и y=v.

Определение. Бинарным или двуместным отношением называют множество упорядоченных пар. Элементы x и y называют координатами или компонентами отношения ??.

Записи ?? и x?y означают, что пара принадлежит бинарному отношению . ?

Определение. Областью определения бинарного отношения ? называют множество D?={x | существует такое y, что x ? y}. Областью значений называют множество R??={y | существует такое x, что x ? y}.||

Примеры.

1.Множество {<1,2>,<2,4><3,3>,<2,1>}– бинарное отношение.

D?={1,2,3}, R?={2,4,3,1}={1,2,3,4}.

2. { | x, y – действительные числа и x=y} - отношение равенства на множестве действительных чисел (специальное обозначение «=»). D?={x | x?R}, R?={y | y?R}.

Свойства бинарных отношений на множестве М.

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

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

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

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

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

Определение. Упорядоченным набором длины n или n-кой элементов называется последовательность, состоящая из n элементов x1, x2, x3,…, xn, расположенных в определенном порядке и обозначается 1, x2, x3,…, xn>.

Определение. n-нарным отношением называют множество упорядоченных наборов длины n.

Определение. Обратным отношением для ?={ | ??} называют отношение ?-1={ | ??}.

Определение. Композицией отношений ?1 и ?2 называют отношение ?2??1={ | ? z такое, что ??1 и ??2}.

Операции над отношением(т.к. отношение явл. множ. => все операции опр. для множеств. справедливы для отношений)

1) сравнение множеств. Множество А содержится в множестве В, если каждый элемент А есть элемент В . А- подмножество В, В - надмножество А. Говорят, что А=В, если все элементы А являются элементами В, и наоборот. Если , то А - собственное подмножество. Мощность множества А обозначается как |А|, для конечных множеств - это число элементов , если |A|=|В| - множества равномощные. 2) Объединение. 3)Пересечение. 4) Разность (относительное дополнение) 5) Симметрическая разность 6(добавляется) Отношение называется обратным к отношению R и обозн. , если 7) Опр.: Пусть , композицией наз. отношение , которое определяется след. образом: Пример: Пусть и , тогда

Функции

Определение. Бинарное отношение f называется функцией, если из ?f и ?f следует, что y=z. (Функция является однозначной).

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

Если Df =X и Rf =Y, то говорят, что f осуществляет отображение множества X на множество Y. Обозначения:

f:X?Y или . fXY?

?f ? y=f(x); y – образ, x – прообраз элемента

Определение. n-местной функцией называют отношение f, если f:Xn?Y. Обозначение y=f(x1,…,xn).

Определение. Функция f:X?Y называется инъективной, если

?x1, x2, y : y=f(x1), y=f(x2) ? x1=x2. (То есть, одинаковые значения y могут соответствовать только одинаковым x).

Определение. Функция f:X?Y называется сюръективной, если

?y?Y ?x?X : y=f(x). (То есть, каждому значению y соответствует некоторое x).

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

Говорят, что биективная функция f осуществляет взаимно однозначное соответствие между множествами X и Y.

Примеры.

f(x)=ex - инъективна, но не сюръективна при x ? R

f(x)=x3-x - сюръективна, но не инъективна;

f(x)=2x+1, f(x)=x3+x – биективна.

Теорема. Композиция двух функций есть функция.

Доказательство. Допустим, композиции g?f принадлежат две пары:

vgzxfvvugyxfuufgzxfgyx,:,:o,o,???⎭⎬⎫>?<>?<.

Поскольку f – функция, то u=v. Поскольку g – функция и u=v, то y=z, т.е. gof – функция.

Теорема

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


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

ex: X?X такое, что ?x?X ex(x)=x. Тогда f?ex=f, ey?f=f.
Теорема

Отображение f:X?Y имеет обратное отображение f?1:Y?X тогда и только тогда, когда f – биекция.

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

Пусть f – биекция. Поскольку f – сюръективна, то f-1 определена на множестве Y (каждому y соответствует определенное x).

В связи с инъективностью функции f обратное отношение f-1 является функцией (так как функция – однозначна, а инъективность означает невозможность соответствия различных x одному y). Прямое утверждение доказано.

Пусть теперь отображение f имеет обратное – f-1, определенное на множестве Y со значениями во множестве X. Тогда f сюръективно.

Но f также инъективно, так как f-1 – функция.

Утверждение доказано.

Замечание. Для того, чтобы обратное отношение f-1 было функцией, достаточно, чтобы функция f была инъективной. Тогда для инъективных функций выполняются следующие свойства бинарных отношений

1) (f?1)?1=f; 2) (g?f) ?1= f?1?g?1.
Специальные бинарные отношения

В данном разделе рассматриваются отношения элементов одного и того же множества X.

Определение. Отношение ? на множестве X называется рефлексивным, если для любого Xx? выполняется xx?.

Определение. Отношение ? на множестве X называется антирефлексивным, если xx? не выполняется ни для какого . x?X x

Определение. Отношение ? на множестве X называется симметричным, если для любых yyxизXy,x????.

Определение. Отношение ? на множестве X называется антисимметричным, если для любых x,y?X из x?y и y?x ? x=y.

Определение. Отношение ? на множестве X называется строго антисимметричным, если для любых x,y?X из ?? ? ??.

Определение. Отношение ? на множестве X называется транзитивным, если для любых xzyиyxизXz,y,x?????. z

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

Определение. Классом эквивалентности, порожденным элементом x, называется подмножество множества X, состоящее из таких элементов y?X, для которых x?y. Обозначение: [x]. Т.е. [x]={y?X | x?y}.

Примеры.

1. Отношение равенства: ?x?Z [x]={x}, т.е. каждый класс эквивалентности состоит из одного элемента – числа x.

2. Отношение сравнимости по модулю n: [x]={x+kn, k?Z}.

Определение. Разбиением множества X называется совокупность попарно не пересекающихся подмножеств X, таких, что каждый элемент множества X ? одному и только одному из этих подмножеств.

Примеры.

1. . Разбиение:. }5,4,3,2,1{X= 4{},5,3{},2,1{{}}

2. Разбиением множества студентов института может быть совокупность групп.

Теорема. Всякое разбиение множества X определяет на X следующее отношение эквивалентности ?:

x?y тогда и только тогда, когда x и y принадлежат одному подмножеству разбиения.

Справедливость очевидна.

Утверждение. Всякое отношение эквивалентности определяет разбиение множества X на классы эквивалентности.

Определение. Совокупность классов эквивалентности элементов любого множества X по отношению эквивалентности называется фактор-множеством множества X по отношению ?? и обозначается X/?.

Пример. Множество студенческих групп данного вуза является фактор-множеством множества студентов вуза по отношению принадлежности к одной группе.

Определение. Множества A и B называются равномощными, если между A и B существует взаимно однозначное соответствие (т.е. биективное отображение ). f:AB?

Теорема

Отношение равномощности множеств является отношением эквивалентности.

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

1) Рефлексивность можно установить, отображая множество само на себя с помощью функции f(x)=x. То есть |A|=|A|.

2) Симметричность. Если взаимно однозначное соответствие, то и - также взаимно однозначное соответствие. f:AB?1f:BA??

3) Транзитивность a?b,b?c?a?c Т. е. |A|=|B|, |B|=|C| ? |A|=|C|.

Определение. Говорят, что мощность множества A не превосходит мощности множества B (пишут|A|<=|B| ), если ? множество B1? B:|A| =|B1|

В частности, если A?B, то B1=A.

Определение. Говорят что |A| меньше |B| (|A|< |B|), если:

  1. |A|?|B||

  2. |A|?|B|

Теорема Кантора. Пусть N – множество натуральных чисел, A=[0,1] – отрезок действительной оси. Тогда |N|<|A|.

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

1) Во-первых, |N|?|[0,1]|, поскольку подмножество множества A 1,1/2,1/3…-

очевидно, равномощно N.

2) Неравенство|N|? |[0, 1]| докажем от противного.

Допустим, |N|=|A|. Тогда ? ? f:N? [0,1]

Любое число из A можно представить в виде бесконечной десятичной дроби

f(1)=a1=0,a11a12

f(2)=a2=0,a21a22

f(3)=a3=0,a31a32a33

………………..

f(n)=an=0,an1an2an3…ann

………………..

Построим число b=0,b1b2b3… следующим образом:

Bi=? b?[0,1] и b?an, поскольку b отличается от an в n-ном знаке.

Приходим к противоречию. Теорема доказана.

СЧЕТНЫЕ МНОЖЕСТВА

Определение. Множество, равномощное множеству натуральных

чисел |A|=|N| называется счетным.

Теоремы о счетных множествах

Теорема 1. ?? множество содержит счетное подмножество.

Док-во.

Выберем элемент a1?A (A не пусто, так как оно бесконечно);

выберем элемент a2?A\{a1} (A\{a1} не пусто, так как A бесконечно);

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

Теорема 2. ? ? подмножество B счетного множества A счетно.

Д-во. Согласно Т1 из ? множества B можно выделить счетное C.

Тогда C?B?A. В силу определения мощности |C|?|B|?|A|. Так как A и C – счетные, то |A|=|C|. Т. е. |A|?|B|?|A|. Отсюда следует, что |B|=|A|.

Тем самым, счетное множество равномощно своей ? части.

Теорема 3. Объединение конечного или счетного семейства счетных множеств – есть счетное множество.

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

A1={a11,a12,…},

A2={a21,a22,…},

A3={a31,a32,a33,…}

………………..

An={an1,an2,an3,…,ann,…},

………………..

Расположим элементы A в следующем порядке

a11,a12,a21,a31,a22, a13,a14,a23,a32,a41,…

Тем самым, получили взаимно однозначное отображение N на A.

Если в множествах A1, A2, A3,… есть общие элементы, то их объединение A есть подмножество рассмотренной выше последовательности. Но согласно теореме 2 оно счетно.

Следствие 1. Если A и B счетные, то A x B – счетное.

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

Теорема доказана.

Теорема. Мощность булеана (множества-степени) счетного множества = мощности континуума: |P(N)|=| [0,1] |

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

Пусть 0,010…1… – запись любого числа из A=[0,1] в 2ой системе счисления.

Сопоставим этому числу подмножество N, состоящее из чисел, равных номерам разрядов, в которых записана единица. Этим устанавливается взаимно однозначное соответствие между B(N) и [0,1].

ГРАФЫ

Графом G(V, Е) называется совокупность двух множеств — непустого множества V (множества вершин) и множества Е неупорядоченных пар различных элементов множества V (Е — множество ребер).

G{V,E) = (V;E),

Число вершин графа G обозначим р, а число ребер — qp:=p{G)-. = \V I, q:=q(G): = \E\.

Если пары (v,w) являются упорядоченными, граф называется ориентированным (орграфом).

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

Псевдограф без петель называется мультиграфом.

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

Ребра ориентированного графа называются дугами.

Неориентированный граф - {v,w}.

Ориентированный граф - (v,w).

Обозначают v,w - вершины, x,y,z - дуги и ребра.

Смежность

Пусть v1, v2 вершины, e = (v1 ,v2) соединяющее их ребро. Тогда вершина v1 и ребро е инцидентны, вершина v2 и ребро е также инцидентны. Два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными.

Множество вершин, смежных с вершиной v, называется множеством смежности вершины v и обозначается Г+( v): Г+( v) : = {и Ђ V | (и, v)

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

Графы G1=(V1,X1), G2=(V2,X2) называются изоморфными, если ? биективное (взаимно однозначное) отображение ϕ: V1?V2, сохраняющее смежность, т.е.

{v,w}?X1 ? {ϕ(v), ϕ(w)}?X2 .

Подграфы

Граф G'(V', Е') называется подграфом графа G(V, Е) (обозначается G' с G), если V' С V и/или Е' с Е.

Если V' = V, то G' называется остовным подграфом G.

Если V' С V & Е' С E& (V' ± V V Е' ? Е), то граф G' называется собственным подграфом графа G.

Некоторые виды неорентированных графов

Граф, в котором каждая пара вершин смежна, называется полным.

Маршрутом в графе называется чередующаяся последовательность вершин и ребер

Если все ребра различны, то маршрут называется цепью

Замкнутая цепь называется циклом; замкнутая простая цепь называется простым циклом.

Для орграфов цепь называется путем, а цикл — контуром.
Двудольный граф
— это граф G(V,E), такой что множество V разбито на два непересекающихся множества V1 и V2 (V1 U V2 = V& V1 ^V2 = 0), причем всякое ребро из Е инцидентно вершине из V1 и вершине из V2 (то есть соединяет вершину из V1 с вершиной из V2). Множества V1 и V2 называются долями двудольного графа. Если двудольный граф содержит все ребра, соединяющие множества V1 и V2, то он называется полным двудольным графом

Маршруты и

связность

Степени вершин

опр Вершины v, w называются смежными, если {v,w}?X.

опр Степенью вершины v графа G называется число ?(v) ребер графа G, инцидентных вершине v.

опр Вершина графа, имеющая степень 0 называется изолированной, а степень 1 – висячей

замеч || В неориентированном псевдографе вклад каждой петли инцидентной вершине v в степень вершины v равен 2.

опр || Полустепенью исхода (захода) вершины v орграфа D называется число ?+(v) (??(v)) дуг орграфа D, исходящих из v (заходящих в v).

Маршруты

Маршрутом в графе называется чередующаяся последовательность вершин и ребер v0,ei,vi,e2,v2,... ,ek,vk, в которой любые два соседних элемента инцидентны.

v2x2v3x4v4 - подмаршрут.

Число ребер в маршруте (дуг в пути) называется длиной маршрута (пути).

Маршрут (путь) называется замкнутым, если начальная вершина совпадает с конечной v1=vk+1.

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

Цепь, в которой все вершины попарно различны называется простой цепью.

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

Цикл (контур), в котором все вершины попарно различны называется простым.

Если все ребра различны, то маршрут называется цепью. Если все вершины (а значит, и ребра) различны, то маршрут называется простой цепью. В цепи v0,ei,... ,ek,vk вершины v0 и vk называются концами цепи. Говорят, что цепь с концами и и г; соединяет вершины и и». Цепь, соединяющая вершины и и г;, обозначается (к,г;). Очевидно, что если есть цепь, соединяющая вершины и и v, то есть и простая цепь, соединяющая эти вершины.

Говорят, что вершина w орграфа D (графа G) достижима из верш. v, если либо w=v, либо существует путь (маршрут) из v в w.

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

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

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

Пусть D=(V,X) орграф, V={v1,...,vn}, X={x1,...,xm}.

Матрицей смежности орграфа D называется квадратная матрица

A(D)=[aij] порядка n, где



Матрицей инцидентности называется матрица B(D)=[bij] порядка nЧm, где

Определение. Матрицей достижимости орграфа D называется квадратная матрица T(D)=[tij] порядка n, элементы которой равны

Алгоритм выделения компонент сильной связности.

1. Присваиваем p=1, S1=S(D).

2. Включаем в множество вершин Vp компоненты сильной связности Dp вершины, соответствующие единицам первой строки матрицы Sp. В качестве матрицы A(Dp) возьмем подматрицу матрицы A(D), состоящую из элементов матрицы A, находящихся на пересечении строк и столбцов, соответствующих вершинам из Vp.

3. Вычеркиваем из Sp строки и столбцы, соответствующие вершинам из Vp. Если не остается ни одной строки (и столбца), то p- кол-во компонент сильной связности. В противном случае обозначим оставшуюся после вычеркивания срок и столбцов матрицу Sp+1, присваиваем p:=p+1 и переходим к п. 2.

Кратчайшие пути в графе

(ненашел xD)
Деревья

Утверждения об эквивалентных определениях дерева

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

Утверждения об эквивалентных определениях дерева

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

Дерево - это связный граф, имеющий п вершин и п—1 ребер. > Непосредственной проверкой устанавливаем справедливость этого утверждения при п=1, 2, 3. Допустим, что оно верно для дерева с п-1 вершинами, и рассмотрим случай, когда дерево T имеет п вершин. Если в нем удалить любое ребро, то в силу утверждения 2, получим два дерева с п<(п—1) и п2<(п—1) вершинами. По индуктивному предположению число ребер в них п — 1 и п2 1 соответственно. По этому T содержит [(п — 1)+(п2 — 1)]+1=п +п2 1=п—1 ребер. <

Листом (висячей вершиной) называют вершину, степень которой равна 1, если она не рассматривается как корень.

. Ориентированное дерево это граф, в котором полустепень захода у одной вершины, называемой корнем, равна нулю, а у остальных - единице.

Матричное представление.

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

Код Прюфера.

Каждое дерево имеющее n вершин может быть однозначно описано числовым кодом, содержащим n-2 элементов и называемым кодом Прюфера

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

Отыскиваем вершину степени 1 с наименьшим номером и включаем в код номер смежной с ней вершины, после чего удаляем найденную вершину (вместе с ребром). С получившимся подграфом выполняем ту же операцию, повторяя ее, пока не останется только одно ребро.
Алгоритм восстановления дерева, представленного кодом Прюфера, позволяет получить соответствующей список ребер.
Назовем антикодом упорядоченную по возрастанию последовательность номеров вершин, не вошедших в код Прюфера.
Дерево строится путем последовательного добавления ребер. Очередное добавляемое ребро, начиная с первого, образуется парой вершин, номера которых стоят первыми в строке кода и в строке антикода. После этого использованные элементы строк вычеркиваются. Если номер, вычеркнутый из строки кода, не содержится среди оставшихся в ней элементов, его следует добавить к строке антикода, не нарушая ее упорядоченность.
Описанные действия повторяются с "остатками" строк кода и антикода, пока не будут вычеркнуты все элементы первой из них. При этом строка антикода будет содержать два элемента, определяющих последнее ребро, которое следует добавить к формируемому списку. В результате получаем список из n1 ребер, соответствующий дереву, заданному кодом Прюфера.
Теорема Кэли

Число различных помеченных деревьев с n вершинами равно nn-2

Этот результат может быть легко получен на основе кода Прюфера. Действительно, поскольку любое дерево, имеющее n вершин , помеченных числами от 1 до n, однозначно описывается (n2) -разрядным кодом, каждый разряд которого может принимать некоторое, вполне определенное значение из множества {1, 2,.. .,n}, и наоборот, каждому (n—2)- разрядному коду, составленному на основе чисел из указанного множества, соответствует конкретное дерево, то общее число деревьев должно быть равно nn-2
Задача о кратчайшем остове графа
Пусть G связный неориентированный граф, каждому ребру которого приписан некоторый вес cij > 0.


Алгоритм Прима


Описание алгоритма. В отличие от алгоритма Краскала, алгоритм Прима обеспечивает построение остова графа G(V,E), заданного списком ребер, путем наращивания единственного древовидного фрагмента T(VT, ET), который вначале вообще не имеет ребер и состоит из одной произвольно выбранной вершины графа. На каждой итерации к фрагменту добавляется самое короткое ребро из числа ребер, у которых одна из концовых вершин v уже включена в строящийся остов, а другая Vj еще нет, т. е. ETk:=ETk-1+{vi,Vj} и VTk:=VTk-1 +Vj, где viЈVTk-1, Vj^VTk-1, a cij минимально.

Процесс заканчивается после присоединения к Т n-1 ребер.

Таким образом, при выполнении алгоритма формируется последовательность деревьев: T0, T1,..., Tn-1, где T0=({v}, пуст. мнж), a Tn-1 — кратчайший остов. Если список упорядочен по возрастанию весов ребер, то включению в остов на очередной итерации подлежит первое от начала списка ребро {vi,vj}, отвечающее указанному выше условию.

Эйлеров цикл это простой цикл, содержащий все ребра связного неориентированного мультиграфа. Простую цепь, проходящую через все ребра, называют эйлеровой цепью. Граф, в котором есть эйлеров цикл, называется эйлеровым, а граф, содержащий эйлерову цепь – полуэйлеровым
ТЕОРЕМА Если граф G связен и нетривиален, то следующие утверждения эквивалентны:

  1. G — эйлеров граф;

  2. каждая вершина G имеет четную степень;

  3. множество ребер G можно разбить на простые циклы.

Д-во

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

3 G — связный и нетривиальный граф, следовательно, V v d(v) > 0. Степени вершин четные, следовательно, V v d(v) ^ 2. Имеем:

Следовательно, граф G — не дерево, а значит, граф G содержит (хотя бы один) простой цикл Z\. (Zi — множество ребер.) Тогда G Zi остовный подграф, в котором опять все степени вершин четные. Исключим из рассмотрения изолированные вершины. Таким образом, GZ\ тоже удовлетворяет условию 2, следовательно, существует простой цикл Zi с (GZi). Далее выделяем циклы Zi, пока граф не будет пуст.

3 1 Возьмем какой-либо цикл Z\ из данного разбиении. Если Z\ = Е, то теорема доказана. Если нет, то существует цикл Z2, такой что

3ui (vt е Z-i&cvi е z2),

так как G связен. Маршрут Z\ U Z2 является циклом и содержит все свои ребра по одному разу. Если Z\ U Z2 = Е, то теорема доказана. Если нет, то существует цикл Z3, такой что 3v2 (v2 Ђ Zi U Z2 к v2 6 Z3). Далее будем наращивать эйлеров цикл, пока он не исчерпает разбиения. □

Алгоритм Флёри, которая заключается в следующем. Начиная с некоторой вершины, произвольным образом "идем" по смежным ребрам графа, удаляя пройденное ребро и вершину, ставшую после удаления ребра изолированной. Не проходим по ребру, если после его удаления граф становится несвязным. Нетрудно показать, что процесс завершается после обхода (удаления) всех ребер, а значит, и вершин графа, и обязательно в исходной вершине, степень которой к этому моменту становится нулевой. Отметим, что каждая вершина (в отличие от ребер, проходимых однократно), вообще говоря, может быть пройдена неоднократно, точнее — deg v/2 раз. Порядок, в котором были пройдены ребра, определяет конфигурацию найденного цикла.
Гамильтоновы и полугам. графы
Гамильтоновым называют простой цикл, включающий все вершины связного неориентированного графа.

ТЕОРЕМА (Дирак) Если в графе G(V, E)для любого vЂV d(v) ? р/2, то граф G является гамилътоновым.

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

От противного. Пусть G не гамильтонов. Добавим к G минимальное количество новых вершин ui,...,un, соединяя их со всеми вершинами G так, чтобы G' : = G + u1+..+ ип был гамилътоновым.

Пусть v, ux,w,... ,v гамильтонов цикл в графе G', причем v Ђ G, u1 Ђ G', u1 неЂ G. Такая пара вершин v и u1 в гамильтоновом цикле обязательно найдется, иначе граф G был бы гамильтоновым. Тогда w Ђ G, w неЂ {u1,..., ип}, иначе вершина u1 была бы не нужна. Более того, вершина v несмежна с вершиной w, иначе вершина u1 была бы не нужна.

Далее, если в цикле v, щ, w,..., v', w',..., v есть вершина w', смежная с вершиной w, то вершина v' несмежна с вершиной v, так как иначе можно было бы построить гамильтонов цикл v,v',... ,w, w'... v без вершины и\, взяВ последовательность вершин w,...,v' в обратном порядке. Отсюда следует, что число вершин графа G', не смежных с v, не менее числа вершин, смежных с w. Но для любой

вершины w графа G d(w) ? р/2 + n по построению, в том числе d(v) ? p/2 +n. Общее число вершин (смежных и не смежных с v) составляет п + р — 1. Таким образом, имеем:

п + р- 1 = d(v) + d(V) ?d(w) + d(v)?p/2+n+p/2+n=2n+p

Следовательно, 0?n+1, что противоречит тому, что n>0.
Задача коммивояжера

Рассмотрим следующую задачу, известную как задача коммивояжера. Имеется р городов, расстояния между которыми известны. Коммивояжер должен посетить все р городов по одному разу, вернувшись в тот, с которого начал. Требуется найти такой маршрут движения, при котором суммарное пройденное расстояние будет минимальным.

Очевидно, что задача коммивояжера — это задача отыскания кратчайшего га- мильтонова цикла в полном графе.

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

Как известно, р! с ростом р растет быстрее, чем любой полином от р, и даже быстрее, чем 2Р (см. раздел 5.2). Таким образом, решение 'задачи коммивояжера описанным методом полного перебора оказывается практически неосуществимым даже для сравнительно небольших р. Более того, известно, что задача коммивояжера принадлежит к числу так называемых NP-полных задач, подробное обсуждение которых выходит за рамки этого учебника. Вкратце суть проблемы NP-полноты сводится следующему. В различных областях дискретной математики, комбинаторики, логики и т. п. известно множество задач, принадлежащих к числу наиболее фундаментальных, для которых, несмотря на все усилия, не удалось найти алгоритмов решения, имеющих полиномиальную трудоемкость. Более того, если бы удалось отыскать эффективный алгоритм решения хотя бы одной из этих задач, то из этого немедленно следовало бы существование эффективных алгоритмов для всех остальных задач данного класса. На этом основано общепринятое мнение, что таких алгоритмов не существует.

Раскраска Вершин графа

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

ТЕОРЕМА Если граф G к-раскрашиваемый, то существует такая последовательность выборов множества S на шаге 1 процедуры Р, что применение процедуры Р к графу G построит не более чем к-раскраску графа G.

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

Пусть имеется некоторая k-раскраска графа G(V,E). Перестроим ее в не более чем k-раскраску, которая может быть получена процедурой Р. Пусть Vi с V — множество вершин в данной fc-раскраске, покрашенных в цвет 1. Множество Vi — независимое, но, может быть, не максимальное. Рассмотрим множество Vi', такое что Vx U Vi — максимальное независимое множество (может оказаться, что Vi' = 0). Вершины из V\ не смежны с Vi, значит, вершины из Vi' можно перекрасить в цвет 1. Пусть далее V2 с V\(Vi U Vi') ~ множество вершин, покрашенных в цвет 2. Аналогично рассмотрим множество V2', такое что V2 U V2 максимальное независимое в G\(V1UVi'), покрасим вершины V2UV2' в цвет 2 и т. д. Всего в исходной раскраске было к независимых множеств. При перекраске их число не возрастет (но может уменьшиться, если x(G) < к). На каждом шаге алгоритма рассматривается одно из множеств, следовательно, процесс закончится. □

Паросочетанием (или независимым множеством ребер) называется множество ребер, в котором никакие два не смежны. Независимое множество называется максимальным, если никакое его надмножество не является независимым.

Пусть G(Vi, V2,E) — двудольный граф. Совершенным паросочетанием из V1 в V2 называется паросочетание, покрывающее вершины V1.

ТЕОРЕМА (Холла) Пусть G(V1, V2, Е) — двудольный граф. Совершенное паросочетание из V1 в V2 существует тогда и только тогда, когда для любого А С V1 |А| ? |Г(А)|

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

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

Достаточность. Добавим в G две новые вершины и и», так что и смежна со всеми вершинами из V1, а v смежна со всеми вершинами из V2. Совершенное паросочетание из V1 в V2 существует тогда и только тогда, когда существуют |V1| вершинно-непересекающихся простых (и, v)



Множества и функции.

Множества, способы задания множеств, операции над множествами, свойства операций над множествами. Мощность множества. Булеан. Теорема о мощности булеана. (1,2 шпора)

Прямое произведение множеств. Теорема о мощности прямого произведения. Отношения на множествах. Примеры. Свойства бинарных отношений: рефлексивность, симметричность, транзитивность.(3,4 шпора)

Операции над бинарными отношениями. (5 шпора)

Функции, отображения. Типы отображений: инъекция, сюръекция, биекция. Композиция отображений. Теорема о биективности композиции функций. Обратное отображение. Теорема об обратном отображении композиции функций. Теорема о необходимом и достаточном условии существования обратного отображения (6,7 шпора)

Отношение эквивалентности. Классы эквивалентности. Разбиение множества. Теоремы о классах бинарных отношений. (В билетах : 1.Теорема о связи между отношениями эквивалентности на множестве и разбиении этого множества на классы. 2.Теорема о связи между разбиением множества на классы и отношениями эквивалентности на этом множестве.). Мощность множеств. Равномощность множеств. Необходимое и достаточное условие равномощности конечных множеств (теорема). Равномощность, как отношение эквивалентности (теорема). Теорема Кантора о сравнении мощности множества натуральных чисел и отрезка (0,1). (8,9 шпора)

Счетные множества. Теорема о существовании счетного подмножества бесконечного множества. Теорема о счетности бесконечного подмножества счетного множества. Теорема о счетности множества рациональных чисел. Теорема о равномощности булеана отрезку [0,1]. Теорема о несчетности множества вещественных чисел. (10 шпора)

Теория графов.

Теоретико-множественное определение графа. Изоморфизм графов. Подграфы: остовные, вершинно - порожденные, реберно-порожденные. (11 шпора)

Некоторые виды неориентированных графов (примеры): полный граф, вполне несвязный граф, цикл, цепь, полный двудольный граф. Маршруты и связность: степени вершин, маршрут, цепь, простая цепь, взаимная достижимость вершин, компоненты сильной связности. (12,13 шпора)

Представление графа в ЭВМ: матрица смежности, матрица инцидентности (неориентированного и ориентированного графов), список дуг. Матрица достижимости. Алгоритм выделения компонент сильной связности в графах (или просто связности для неорграфа). (14 шпора)

Кратчайшие пути в графе. Волновой алгоритм. Кратчайшие пути во взвешенном графе: алгоритм Дейкстры.(хрен знает, не нашел xD)

Деревья. Неориентированные деревья. Утверждение об эквивалентных определениях дерева. Ориентированные деревья. Описание деревьев в виде матриц и с помощью кода. Построение помеченных деревьев (код Прюфера). (15 шпора) Теорема Кэли. (16 шпора)

Задача о кратчайшем остове графа: алгоритм Прима. Радиус, диаметр и центр графа. Теорема о центре дерева. Эйлеровы и полуэйлеровы графы. Теорема об условиях эйлеровости графа. Алгоритм Флери.(17,18 шпора)

Гамильтоновы и полугамильтоновы графы. Теорема Дирака(достаточное условие гамильтоновости неориентированного графа). (19 шпора)

Метод ветвей и границ. Задача коммивояжера. Графовые вектора. Теорема о необходимом и достаточном условии графовости вектора. Раскраска вершин графа. Теорема о раскраске произвольного графа. Паросочетания в двудольном графе. Теорема Холла.(20,21 шпора)

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




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