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

Пусть каждая из вершин x1,x2,..,x5 выкрашена в свой цвет обозначим такой подграф графа который порождается перекраской меняем и меняем . В случае если вершины x1 и x3 лежат в разных компонен-х связности, тогда поменяв в компоненте  содерж  x1 цвета следующим образом: получим опять правильную раскраску, но вершина x1 будет иметь цвет . В этом случае вершину можно выкрасить цветом . Иначе существует простая цепь м/у вершинами x1 и x3 состоящая из или . В этом случае вершины x2 и x4 принадлежат разным компонентам связности подграфа . В этом случае меняя цвета добиваемся того, что вершины x2 и x4 оказываются одного цвета, а оставшиеся подходят для вершины . 

13 Свойства функции  π(G,λ): Формула (**) выглядит проще формулы (*), но так же достаточно неудобна при вычисление хроматического числа достаточно сложных графов. Для графов с четырьмя или более вершинами обычно используется конструктивный подход, т.е. граф разбивается на более мелкие, для которых функция π вычислена, а для построения общих функций используется набор основных лемм:

Лемма 1: Пусть граф G состоит из двух компонентов связности G₁ и G₂, тогда π(G,λ)= π(G₁,λ)* π(G₂,λ).

Доказательство: Пусть для графа G₁ существует π(G₁,λ) правильных раскрасок λ-красками, а для G₂соответственно π(G₂,λ). Раскраски G₁ и G₂ независимы следовательно каждой раскраски графа G₁ соответствующей π(G₂,λ) правильных раскрасок графа G₂. Таким образом общее количество правильных раскрасок графа G составляет π(G,λ)= π(G₁,λ)* π(G₂,λ).Лемма 2: Если граф G получен из двух склеиванием по одной вершине x₀, то его π функция вычисляется: π(G,λ)= π(G₁,λ)* π(G₂,λ).

Лемма 3: Пусть граф G получен из G1 и G2   склейкой с помощью ребра l внешнего для обоих графов

π(G,λ)=(1-1/ λ )π(G₁,λ)* π(G₂,λ).

Лемма 4: Пусть граф G получен из G1 добавлением ребра без изменения числа вершин

π(G,λ)=π(G₁,λ) – π(G|,λ).

23 Основные модели  теории вероятности.Исход.События.Для разрешения ситуации зависящих от параметров необх знать в точности какие именно знач-я приняли эти параметры. Для предсказания исхода и выбора необ стратегии необх уметь сравнивать исходы по мере их правюоподобия. Оцениванием меры правдоподобия занимается теория вероятности. В кратце основн понятия теории можно продемонстрировать на основе 3 моделей: модель1-подбрасывание монет «орёл»-«решка». Моднль2- кости или игра кубик «1»… «6». Модель3- игральные карты. 52 исхода выпала карта, 4 исхода- выпала мать, 13 исходов – выпало значение, 2 исхода – цвет. Будем счиать что все исходы явл равновозможными, тогда люб событие содерж неск равноправ исходов. Ex: А={выпал орёл}-1 исход,  В={выпала карта пик}-исход. Кол-во исходов в событии не явл самодостат числовой хар-й. Для объектив оценки необх знать сколько всего исходов могло быть. Для этого вводитсмя понятие частоты событии. Частота нах как отнош кол-ва исходов способств событию к общему кол-ву событии. На основе провед-х рассужд можно дать простейшие опред вероятности: Рассм мн-во Q-мн-во элементарных событии , Q={w}БУДЕМ СЧИТАТЬ ЧТО ВСЕ ЭЛЕМЕНТ . событи явл явновероятными.Рассм подмн-во А принадл Q будем наз случайным событием. Вероятностью случ события А будем наз соотнош P(A)=|A|/|Q| Ex: {выпал туз черви, выпал король черви … выпала 2 пик}-52 элем события. А={туз черви, туз вини, туз крести, ткз буби} P(A)=4/52=1/13. Событик вероятность кот =1 наз достоверным. Если вероятность событии =0 то его наз невозможным. Если вероятность одноврем выпадения 2-х событии =0 то события наз несовместимыми.Ex:модель 2-2 кубика А={выпало больше 11 очков} Q=36 А={(5,6),(6,5), (6,6)} P(А)=1/12.  

16.Дерево.Хромат число н-верш дерева

 Граф  d_n – дерево с n вершинами. По определению граф является n-вершинным деревом, если он связен и не содержит циклов.

Рассмотрим  произвольное дерево с n вершинами. Часть ребер, входящих в дерево являются тупиками. Удалим одно из ребер-тупиков.

Удалим  ребро (x_n-2, x_n) и обозначим получившийся граф G1. Граф d_n получается из графа G1 добавлением ребра без изменения количества вершин. По лемме 4: π(d_n,λ)= π(G1,λ)- π(G',λ), где G'- граф, образованный за счет слияния вершин x_n и x_n-2, т.е. G'- дерево с (n-1) вершиной (G'= d_n-1).

Рассмотрим  подробнее граф G1. G1 состоит из 2-х несвязных между собой подграфов: d_n-1 и x_n. По лемме 1, если граф состоит из 2-х несвязных между собой частей, то π(G1,λ)= π({x_n},λ)* π(d_n-1,λ)= λ*π(d_n-1,λ) =>

π(d_n,λ)=(λ-1)* π(d_n-1,λ)

Мы  получили рекурсивную зависимость. Применив ее (n-1) раз, получим

π(d_n,λ)=(λ-1)^n-1*π(d₁,λ)= λ*(λ-1)^n-1

Возникает вопрос: любой ли многочлен с целыми коэффициентами будет π-функцией для некоторого графа. Из определения мы можем сделать вывод, что π-функция должна удовлетворять следующим условиям:

1). π(G,n₀)=0 => n< n₀: π(G,n)=0

2). π(G,k₀)≠0 => k>k₀: π(G,k) ≠0

3). π(G,n)≥0 => n є N 
 
 
 

24 Математическое ожидание. Среднее квадратическое  отклонение. Примеры. Часто рассматривается элемент события, имеющий некоторые собственные характеристики. Например, Колич-во бракованных деталей, продолж безотказно работать. Такие характеристики в вероятностных моделях вводятся как функции элементарных событий:  Q={w} через обозначим вероятностн элементарные события Q, заданная на мн-ве Q функция f f:Q R называется случайной величиной. Различные случайные величины, заданные на одном и том же мн-ве могут быть как независимыми друг от друга, так и находиться в некоторой зависимости. Пример: С завода «Бракодела» поступают 3 агрегата. Вероятность того, что не сломан ни один агрегат=1/10. Вероятность того, что сломан 1 агрегат=0,7, 2=0,15, 3=0,05. Сформирован вероятностн модель. Q={w1,w2,w3,w4} =»сломано (i-1) агрегатов». Т.О каждый исход и f( )=i-1.

При помощи таблицы мы можем ожидаемые в  среднем кол-во неисправленных агрегатов  и на сколько будет отклонятся результат от полученной величины при  каждом следующем испытании. Опр.: Величина называется математическими ожиданиями случайной величины и приближен соответ наибольшему вероятностному значению этой величины : Е f=0.1*0+0.7*1+0.15*2+0.05*3=1.15

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

Опр.: корень из дисперсии наз-ся средним квадратичным отклонением. Они используются для оценки средних относит-о отклонения случайной величины от математич ожидания

  Наибольшее  вероятностное значение нашей  случайной величины будет находиться  в интервале (0, 53; 1,17). В случае, если при некотором наборе  случайных сообщений замеряются 2 характеристики  , то можно выяснить на сколько эти 2 величины зависимы. В качестве таких критериев можно выбрать затраты на поиск в худшем случае либо математич-е ожидание затрат на поиск.  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

26. Коды.

При записи текстов в том или ином виде часто ипользуется идея кодирования, она лежит в основе любого письменного языка.Для записи русскоязычного текста необходимо иметь набор из как min 36 символв. Наиболее важной задачей кодирования оказывается при работе со связью и вычислительными устройствами. В связи издавна использовались общеизвестные коды (Морзе). Для работы вычислительных устройств используется несколько общеупотребимых кодов: ASCII-пример кода постоянной длины(8 битов), Unicode-код постоянной длины(2-х байтовый).В случае когда необходимо получить доп символы использ идея специального расшир символа. Пара из такого символа и стандартног дает некий новый символ, устанавливаемый по договоренности. Код постоянной длины обеспечивает большую простоту при использовании,однако не является оптимальным в плане затрат на обработку информ. Каждый символ в кодируемом сообщении имеет определенную частоту, т.е. имеет определенную вероятность, с которой он может встретиться в тексте. По видимому разумно наиболее часто встречаемые символы обозначать кратчайшей послед символов кода и наоборот. Такой подход породил идею кодопеременной длины. Примером такого кода м.б. код  Шеннона-Фэна.Сложность при этом возникает в разделении символов.В Азбуке Морзе, для разделения символов (код. последовательностей) исп. «третий » символ-пауза.Шеннон и Фэно предложили построение кода, облад св-ми: Никакая кодовая последов не явл началом другой код послед. Код, облад таким свойством наз префиксом.Критерий выбора длины код после-ти для каждого символа базируется на вероятностном подходе. ] символ a встречается в тексте с вероятностью и ] S -длина последовательности, кот будет ее изображать. В этом случае задача уменьшения затрат на передачу информации сост в уменьшении матем ожидания длины код комбинации случайновыбранного символа: Ea= P S Набор длин, для кот это математич ожидание min наз оптимальным. Св-ва оптим набора:1) Математически выраж идею сформул нами ранее, наиб часто встреч символ должен иметь кратчайшую код послед.

P1 P2 … Pn =>S1 S2 … Sn. 2) S =Sn, т.е. длины двух max код послед. совпадают.Док-во: ] Sn> S , т.е. кодовая послед символа an содерж больше элем, чем у a . Но поскольку никакая код послед не явл нач другой, то первые S символов n-послед не должны совпадать ни с одной из предыдущих, а => все оставшиеся символы n-послед можно отбросить. Идея кода Шеннона-Фэно: Если в алфавите 2 символа, то кодируем их: 1 и 0.Если больше, то объединяем 2 самых редких символа в один и возращ в начало.Этот метод наз методом Хаффмена. По сравнению с кодами постоян длины метод дает выигрыш в V инф-го сообщ. Чем больше V текста , тем больше фективность метода Хаффмена. Этод метод допускает возможное усовершенствование. Так например при многократном повторении некоторого набора символов логично сначала заменив этот набор на один символ, а затем уже переходить к кодировке. Также различные симолы могут иметь одинаковые вероятности появления, что в итоге может дать разл варианты кодовых деревьев. Математ ожидание числа знаков на один символ при использовании любого такого дерева будет одинаковым. 
 
 
 
 
 
 
 
 
 
 
 

28. Избыточное кодирование.

При выборе способа кодировки, необходимо учитывать  все цели, поставл перед исполнителями. О сжатии текста было сказано ранее. Другой важной характеристикой явл  помехоустойчивость. Поставим перед  собой задачу передать инф таким  образом, чтобы при небольших ошибках, вкравшихся при передаче, можно было полностью установить исх сообщение.Эта задача важна при работе с кодами перем длины. Рассмотр простейший случай, когда м.б. искажен max один символ в сообщении, при этом использ метод основанный на понятии контр сумм. Простейший вариант исп-я контрольн сумм вшит в любую электр технику. При передаче 1 байта инф перед 8 бит инф и 9 бит-бит четности, который дополняе передаваемое число либо до четног, либо до нечетного по договоренности. Четность инф-и провер автоматически и в случае её наруш происх фиксация ошибки. Та же идея, но в более сложном виде исп при передаче более сложной инф, при помощи идеи так называемого избыточного кодирования. В этом случае каждая единица инф несет в себе доп инф, позвол установить наличие ошибки. Код Хемминга. ] треб передать n битов инф, а передается N. Для распознавания возможной ошибки нужно чтобы в передав-м тексте кроме n битов основного текста хватило места для распознавания N+1 варианта расположения места ошибки.(считается, что ошибок не более одной, т.е. N+1 мест для ошибки и еще один вариант для отсутствие ошибки). Т.о. должно вып соотношение: 2 N+1 (*). Приведем общую схему исп кода Хемминга. ] задана некот n-длина сообщения. N подобрано так, чтобы вып нер-во (*). Передав биты, располж в местах 1,2,..,n ,перенумеруем т.о, чтобы ячейки 1,2,4,6,8,16,.. остались забронированными для контрольных сумм. Формир матрицу контрольн суммиров-я, содерж N столбцов и N-n строк.Каждый j столбец матрицы будет содержать двоичное предстакление числа j. Кодирование будем производить след образом,умножая перед вектор на каждую строку матрицы по принципу скалярного произведения векторов. Как рез-т получим бит четности для каждой строки, кот пишем на заброниров служебные места. В случае появл одной ошибки при передаче, умножение результатов на ту же матрицу даст номер ячейки, в которой произошел сбой. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

9. Граф, мультиграф. Симметричный  граф. Примеры. Матрицы смежности и инцидентности. Графом или графом без кратных дуг будем наз-ть пару объектов G=(X, Г), где X некоторое конечное множ-во, а Г подмножество декартова квадрата. Заметим что в def графа множество Г(гамма) можно рассм-ть как отношение. Действительно если задать отношение следующим образом: . Тем не менее можем сказать, что граф определяет отображение из множества Х во множ-во Х. Множ-во Х принято наз-ть множеством вершин. Множ-во Г –множеством дуг. В общем случае обе вершины могут соединяться несколькими дугами. Такие дуги наз-ся кратными, а граф –мультиграфом. Мультиграфом G будем наз-ть пару объектов (Х, Г), где .   Вообще говоря, номера дуг необязательно должны идти по порядку, в качестве номеров можно выбирать числа N, лишь бы они были разные. Х-множество вершин мультиграфа. Г-множество дуг мультиграфа. Иногда нет необходимости в указании направления связи, в этом случае будем рассматривать симметричный граф, где , тогда такие спаренные дуги будем наз-ть ребрами, а множ-во ребер будем обозначать . Будем говорить, что дуга и ребро инцидентны, если х=Пр₁u и х=Пр₂u. Вершины и смежны, если дуга и инцидентная им обеим, степенью вершины stx будем наз-ть кол-во дуг ей инцидентных. Предположим, что все вершины и все ребра графа пронумерованы начиная с единицы. Граф может быть представлен виде матрицы типа , где n-число вершин, а m-число ребер (или дуг). Для неориентированного графа элементы матрицы задаются так: Для ориентированного графа элементы матрицы задаются так: Матрицу (а_ij) типа , определенную указанным образом, наз-т матрицей инциденций. Более эффективной матричной структурой представляющей граф, служит матрица смежности вершин, или булева матрица графа. Это квадратная матрица В порядка n, элементы которой определяют следующим образом: 1)для неориентированного графа: 2)для ориентированного графа:

Пример: Для ориентированного графа на этом рисунке нумерация страниц уже  задана. Зададим нумерацию дуг  следующим образом: дуге (u₁, u₂) присвоим номер 1, дуге (u₁, u₃) присвоим номер 2, дуге (u₂, u₃) присвоим номер 3 и дуге (u₃, u₂) присвоим номер 4. Матрицу инцидентности удобно заполнять по столбцам, записывая для k-й дуги (u_i, u_j) 1 в i-й и -1 в j-й строках k-го столбца и 0 во всех остальных строках k-го столбца. . В результате получим матрицу: