Шпарнгалка по "Дискретной математике"

Пр:                                     

Теорема: Для вычисления π функции справедлива формула:

Пр: π(G,λ)= -1*λ + 3*λ - 3*λ² = λ³ - 3λ²+2λ = λ (λ+1) ( λ+2)

Вычислим  отдельно каждый член формулы (*).

Пусть дан набор ребер u_i1, u_i2,...,u_ik. Рассмотрим суграф G’ графа G построенный таким образом, что P(G’)={u_i1, u_i2,...,u_ik} и пусть число компонент связности равно с. Если граф G’ раскрыть так, что концы его ребер раскрашены попарно одинаково, тогда в G’ одинаково раскрашена каждая компонента связности. Число таких раскрасок равно λ^с.

Воспользуемся формулой (*):

или суммируя по количеству компонентов связности  с получим:

, где

p(k,c)≠0.

Очевидно, что таких с может быть только конечное число, что и доказывает формулу (**). 

19 обобщеная формула  Эйлера

m-h+r=n+1

док-во:

рассм любой произвольный n-связный граф G который имеет n компонент связонности G1 G2 ... Gn

пусть m, h, r

произвольные  вершины графа G1 и G2 соединяем ребром (и т. д.)

m1=m, h1=h+n-1, r1=r

новый граф явл-ся связным для него справедлива  ф-ла Эйлера

m1-h1+r1=2

m-h+r=n+1 
 
 
 

10. Путь и контур. Путь в мультиграфе –конечная последовательность дуг графа таких, что конец предыдущей дуги явл-ся началом последующей. Если при этом начало первой дуги сов-ет с концом последней, то путь наз-ся контуром. Будем говорить, что путь простой, если каждая дуга прох-ся 1 раз, а путь элементарный, если посл-ть вершин, составляющих путь, не содержит совпадающих элементов, кроме может быть крайних. В случае симметричности мультиграфа аналогичная терминология, только понятию «путь» соответствует понятие «цепь», а понятию «контур» -«цикл». Простой цикл, содержащий все ребра мультиграфа, наз-т Эйлеровым. Будем говорить, что 2 вершины графа G связаны, если между ними путь, либо если они совпадают. Отношение связности явл-ся отношением эквивалентности. Каждый класс эквивалентности будем наз-ть компонентой связности. В случае если граф состоит из 1 компоненты связности, то граф наз-ся связным. Будем говорить, что ребро u в симметричном мультиграфе G –перешеек, если при его удалении кол-во компонент связности увеличивается на одну. Теорема Эйлера: Эйлеров цикл в симметричном связном мультиграфе G ó когда степени всех вершин четны. Док-во: Дан G симметр-й связный мультиграф, в нем Эйлеров цикл. Суть Эйлерова цикла заключается в том, что при его обходе в каждую вершину мы заходим и выходим каждый раз по новым ребрам, а кол-во ребер каждой вершины должно быть кратно 2. Нужно показать, что в данном графе есть Эйлеров цикл. Док-во по индукции числа ребер. St=1 (смотри рисунок) ч.т.д. Допустим, что условия теоремы выполняются для всех графов, состоящих из N ребер. Докажем что утверждение верно для N+1 ребра. Выберем

произвольный  граф геом. связанный степенью всех вершин с G. В этом графе должен хотя бы один простой цикл. Действительно если бы это было не так, тогда ребро входящее в граф должно было бы быть перешейком. Удаляя например ребро (x_i, x_j), мы получили бы 2, при этом степени вершин (x_i, x_j) станут нечетными. Склеим получившиеся компоненты по данным вершинам. Степень х_о четная. А ребер в нем N (в новом графе). Значит в нашем построенном графе Эйлеров цикл, что противоречит тому, что каждое ребро перешеек в графе G хотя бы один простой цикл. Обозначим найденный простой цикл µ. Если цикл µ содержит все ребра графов то теорема доказана. Рассмотрим случай, когда в цикл µ включены не все ребра. Рассмотрим граф G’=G\µ. Степени всех вершин графа G’ –четные и он состоит возможно из нескольких компонент связности. Кол-во ребер графа G’, а тем боле каждый компонент связности меньше N, а по допущению теоремы каждый компонент имеет свой Эйлеров цикл. Тогда общий Эйлеров цикл для всего графа G строится следующим образом: пусть цикл µ и компоненты связности смежны по вершине x_i, тогда начнем обход Эйлерова цикла компонента связности с вершины x_i. После чего производиться обход цикла µ. ч.т.д. 
 
 
 
 
 
 
 
 
 
 
 

15.хроматическое число графа K_n

  K_n – полный n-вершинный граф. K_n=(Х,Г).

Полным  n-вершинным графом принято называть n-вершинный граф, где Х={x₁, x₂,…, x_n}, Г=Х*Х (декартов квадрат).

Доказательство  этой формулы можно проводить  можно проводить двумя способами: π(G,λ)= λ*( λ-1)*…*( λ-n+1)

Способ 1. (метод математической индукции). Зная формулы для графов K₂ и K₃, доказать формулу по индукции при помощи лемм 3,4.

Способ 2. (аналитический). Заметим, что исходя из формул (*) и (**) функция    π(G,λ) для любого n-вершинного графа представляет собой полином степени n. Заметим, что для полного n-вершинного графа числа <n хроматическим числом быть не могут. Допустим противоположное: граф K_n можно раскрасить правильно при помощи k<n красок. Выберем произвольную вершину x_i є X. Пусть цвет, в который выкрашена вершина, будет обозначен α₁. Вершина x_i соединена со всеми остальными вершинами графа, т.е. имеет n-1 смежную вершину. При этом на раскраску этих вершин остается k-1 цветов (k-1 < n-1). Следовательно, среди вершин, смежных с x_i , найдутся хотя бы 2 одного цвета. Граф K_n – полный => и эти 2 вершины должны быть соединены между собой, т.е. полученная раскраска не является правильной => получили противоречие => λ(K_n) ≥ n.

π(K_n,0)=0

π(K_n,1)=0

…………       => функция π(K_n, λ) является многочленом степени n,

π(K_n,n-1)=0          имеющем как минимум n нулей (0,1,2,…,n-1).

По  основной теоремы алгебры: π(K_n, λ) λ*( λ-1)*…*( λ-n+1) =>

π(K_n, λ)=a* λ*( λ-1)*…*( λ-n+1). Раскроем скобки, старшим членом полученного многочлена будет a. Обратим внимание на формулу (*) и (**). Получаем, что a=1. Что и доказывает наша формула.

λ(K_n) =n, π(K_n, λ)=n!

Критерий  р-хроматичности: граф G р-хроматичен <=> π(G, p)≠0. При этом хроматическое число графа λ(G)=min α, p є N | π(G, p) ≠0. 

17. Гомеоморфизм, изоморфизм графов.2 графа G и G₁ называются изоморфными, если существует пара отображений Ф = (φ, ψ), причём φ: х->х₁, ψ: Г->Г₁, причём эти отображения сохраняют отношение инцидентности. Под этим будем понимать, что если вершина х инцидентна ребру u в графе G, то и вершина φ(х) будет инцидентна ребру ψ(u) в графе G_1.

Граф  G называется плоским, если все его вершины лежат в некоторой плоскости, а все рёбра пересекаются только по вершинам. Пример:

G₁ - плоский, G – неплоский.

Граф  называется планарным, если существует плоский граф изоморфный ему. Пример: граф G не является плоским, но изоморфен плоскому графу G₁, значит граф G₁ – планарный. Совокупность точек n-мерного пространства с определённой метрикой будем называть эвклидовым пространством (Еⁿ). Фигура М из пространства Еⁿ называется геометрической реализацией графа G, если G ~ М. Примером геом. реализации любого планарного графа является соответствующий ему плоский граф. 
 
 
 
 
 
 
 
 
 

18 Формула Эйлера Область огранич ребрами плоского графа и несодерх внутри себя вершин и ребер наз гранью r.

 m-h+r=2- ф-ла Эйлера. Для люб связного планарного графа будет справ ф-ла эйлера. Док-во индукцией по числу граней. r=1 граф Gпредставл собой ломаную с m-вершинами и m-1ребром. В этом случ ф-ла выполн. Док-м что теор справ для r=r0. док-м для r=r0+1. Рассм произв связный планарный граф G с r0+1 гранью. Уберём произв ребро Ui при этом возм-но два случ. 1- ребро Ui отделяет внеш грань в этом случ при его удалении кол-во вершин не изменится, кол-во рёбер уменьшится на 1, h’=h-1, r’=r-1, m’=m но r’=r0, а для всех графов содержащих не больше r0 –граней ф-ла эйлера по допущению выполн т.е. m’-h’+r’=2,   m-(h-1)+(r-1)=2 след-но для нашего графа G ф-ла эйлера выполн 2- Ui-явл внутр ребром графа док-во выполн по аналогии. 

20.Следствия из формулы Эйлера

Следствие 1: пусть G – связный планарный граф и m>3, тогда справедлива оценка: h≤3m-6. (m – вершины, h – рёбра, r - грани)

Доказательство: рассмотрим произвольный граф, где m>3. Заметим, что в графе G каждая грань ограничивается как min 3-мя рёбрами и в то же время каждое ребро разделяет ровно 2 грани, тогда можем сделать вывод: будет справедливо, что 3r≤2h. Воспользуемся полученной оценкой и подставим её в формулу Эйлера:                         2=m-h+r≤m-h+2\3h=m-1\3h≥2 → 3m-6≥h.

Следствие 2: графы К_3,3, К₅ непланарны.

Доказательство:1)рассмотрим граф К₅: m=5, h=10, r=11. Каждые 3 вершины образуют грань. Кол-во треугольников с вершинами в 5-ти точках r=m(m-1)\2. m-h+r=5-10+11=6≠2 → этот граф планарным не является.2)рассмотрим граф К_3,3. для оценки эйлеровой характеристики графа К_3,3 усилим оценку используемую в следствие 1: m=6, h=9. В нашем графе ни 1 грань не является треугольником, значит, каждая грань ограничивается как min 4-мя рёбрами → справедлива оценка: 4r≤2h, 2r≤h. Воспользуемся полученной оценкой:1)из формулы Эйлера, если бы граф был планарен, должно было бы следовать, что r=5, r=2-6+9.2)из нашей оценки получаем, что 2*5≤9 → формула Эйлера не выполняется и граф К_3,3 непланарен.  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

21.Критерий планарности

Основная  теорема теории графов: граф G планарен ттт, когда ни 1 его подграф негомеоморфен (К_3,3 или К₅).

Фактически  теорема утверждает, что для планарности  графа необходимо и достаточно, чтобы  он не содержал в качестве подграфа К_3,3 и К₅. Например, граф К₁₂₁ планарным не является, т. к. содержит внутри себя граф К₅.  
 
 
 

Действительно, выберем произвольные 5 вершин х₁, х₂, х₃, х₄, х₅. Рассмотрим подграф графа К₁₂₁, образованный только этими вершинами. Поскольку в полном графе К₁₂₁ проведены все возможные рёбра, то и в получившемся подграфе каждая вершина будет соединена с каждой. Таким образом, получим граф К₅. По сформулированной теореме граф К₁₂₁ не является планарным.

Следствие 3: в любом планарном графе G найдётся вершина х≤5.

Доказательство: (методом от противного). Допустим, существует планарный граф G, для которого не выполняется условие следствия, т. е. G=(X,P), ( ) stx≥6. В 

этом  случае , → -> 

2h≥6m, h≥3m. В то же время из следствия 1 получаем, что 3m≤h≤3m-6 →-> 3m≤3m-6, 6≤0. Полученное противоречие доказывает наше следствие. 

27. Сжатие текста.

Существ множество различных программных  средств, исп различные методы сжатия. Одним из простейших явл использование кодов перем длины, в частности исп-е кода Хаффмена дает возможность сократить V текста в среднем на 1,5-2 раза. Кроме того исп некоторые другие алгоритмы, позвол активизировать размещ инф-и в вида кода. Он закл в следующем: Кодируемый текст разбив на небольшие строки, кажд из которых составлена из одной из предыд строк и ещё одного символа. Считается что пустая строка имеет номер ноль. Использование этого метода оказ более эффективным, нежели метод Хаффмена. Во-первых, в плане сжатия текста в 1,5-2 раза,во-вторых, его применение не треб предвар просмотра всего текста целиком.методы, представ собой модифик метода Зива-Лемпеля явл более адаптивными, т.е. сами приспосабливаются к особенностям текста. Методы Хаффмена и Зива-Лемпеля лежат в основе работы практически всех наиболее извест архиваторов. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

22 Теорема о Пяти  красках. Введем дополнительн обозначения. Договоримся обозначать символом (хи)- хроматическое число графов

В таком  случае теор звучит следующим образом: G планарен . Док-во: Докажем теор для случая  связного графа G т.к если граф не связен и яв-ся объединением конечного числа компонент связности т.е G (от i=1 до u) , = max(i=1,n) .  Пусть G планарный связный граф докажем теор по индукции (по кол-ву вершин). 1) m 2) Пусть теор справедлива для всех графов  кол-во вершин у которых не превосходит m. Рассмотрим граф G с |x|:= m+1 B силу следствия 3(В любом планарном графе G существует вершина степени ) существует хотя бы одна вершина st обозначим эту вершину , если рассмотреть граф

по  допущению граф можно раскрасить  не более 5-ю красками относительно вершины возможно 3 случая: 1 st раскрасим граф для его раскраски потребуется не более 5-и красок . На раскраску соседних с вершин обозначим их x1,x2,x3,x4 уйдет не более 4-х цветов в таком случае пятым цветом  можем раскрасить  вершину , не  нарушая правила раскраски . 2 st , но для раскраски соседних вершин  использованы не все 5-ть цветов. 3 st и при раскраске соседних вершин использованы все 5-ть цветов