Теорема: Для любого вероятность получить в испытаниях успехов равна

Событие означает, что в испытаниях схемы Бернулли произошло ровно успехов. Рассмотрим один элементарный исход из события : когда первые испытаний завершились успехом, остальные неудачей. Поскольку испытания независимы, вероятность такого элементарного исхода равна Другие элементарные исходы из события отличаются лишь расположением успехов на местах. Есть ровно cпособов расположить успехов на местах. Поэтому событие состоит из элементарных исходов, вероятность каждого из которых равна

Набор вероятностей в теореме называется биномиальным распределением вероятностей.

Билет 20. Условная вероятность. Формула полной вероятности. Формула Байеса.

Условная вероятность - Вероятность наступления события A при наступлении события B

Формула полной вероятности

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

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

Так как события образуют полную систему событий, то по определению событие можно представить следующим образом:

События попарно несовместны, значит, события тоже несовместны. Тогда, воспользовавшись определением условной вероятности, получаем:

Формула Байеса - соотношение различных предполагаемых вероятностей различных событий, которое дает вероятность, что какое-то событие является результатом ряда независимых друг от друга событий , который, возможно, привел к .

Билет 21. Случайная величина, распределение и функция распределения. Математическое ожидание. Дисперсия.

Случайная величина - численное выражение результата случайного события

Распределение - закон, описывающий вероятность наступления случайной величины

Функция распределения случайной величины (англ. cumulative distribution function (CDF)) — функция , определённая на как , т.е. выражающая вероятность того, что примет значение, меньшее чем

Свойства функции распределения:

• при

• непрерывна слева

• .

Математическое ожидание - среднее значение случайной величины

M(x)=SUMM(xi*pi)

Дисперсией случайной величины (англ. variance) называется математическое ожидание квадрата отклонения этой случайной величины от ее математического ожидания

D(x)=M((x-M(x))^2)

В силу линейности математического ожидания справедлива формула

D(x)=M(x^2)-(M(x)^2)

Билет 22. Основные определения. Изоморфизм графов. Ориентированные графы. Лемма о рукопожатиях. Дополнение графа. Объединение и пересечение графов.

Основные определения:

1. Граф - мат. объект, состоящий из вершин и ребер

2. Смежность

3. Инцидентность

4. Ор. граф

5. Псевдо -, мультиграф

6. Подграф, частичный раф, надграф

7. Путь, цепь, цикл

8. Собственный, несобственный подграф

Графы G(Vg,Eg) и H(Vh,Eh) изоморфны, если любые две вершины u,v смежны в G только когда f(u) и f(v) смежны в H

Ориентированные графы - Вместо ребер направленные дуги

Лемма о рукопожатиях

Неор:

Возьмем пустой граф. Сумма степеней вершин такого графа равна нулю. При добавлении ребра, связывающего любые две вершины, сумма всех степеней увеличивается на 2 единицы. Таким образом, сумма всех степеней вершин чётна и равна удвоенному числу рёбер.

Ор:

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

То есть возьмем пустой граф и будем добавлять в него рёбра. При этом каждое добавление ребра увеличивает на единицу сумму входящих и на единицу сумму исходящих степеней. Таким образом, сумма входящих и исходящих степеней всех вершин ориентированного графа чётна и равна удвоенному числу рёбер.

Дополненный граф - граф, содержащий ребра, которых исходному не хватает до полного

Объединение графов - Объединяются их множества вершин и ребер

Пересечение - аналогично

Билет 24. Путь и цепи. Реберно и вершинно простые пути. Лемма о существовании простой цепи при существовании пути в графе. Связность и компоненты связности. Слабая и сильная связность. Компоненты сильной связности.

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

Цепь - путь без повторения ребер

Реберно - простой путь - цепь

Вершинно - простой путь - путь, в котором каждая вершина не повторяется

Лемма о существовании простой цепи. Если в графе есть путь, то есть и простая цепь

Рассмотрим путь (v0,vn). Допустим, в нем есть повтор вершины: v0,A1,v,,A2,v,A3,v0

Тогда путь можно укоротить: v0,A1,v,A3,vn

Так можно проделывать с любым количеством повторяющихся вершин, в итоге получив простую цепь

Если повторов вершин нет, то путь - уже простая цепь

Связность - вершины связны, если между ними есть путь, отношение эквивалентности на графе

Компонента связности - класс эквивалентности на неор. графе

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

Сильная связность - есть ор. путь из a->b и b->a, отношение эквивалентности

Компонента сильной связности - отношение эквивалентности на ор. графе

Билет 25. Отношение реберной двусвязности. Мосты. Эквивалентные определения. Лемма и числе компонент после удаления моста. Лемма о цикле и мосте.

Две вершины реберно двусвязны, если между ними есть минимум два реберно непересекающихся пути:

Мост:

1. ребро, соединяющее две компоненты реберной двусвязности

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

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

4. Ребро является мостом графа , если существует разбиение множества вершин на такие множества и , что и ребро принадлежит любому простому пути

Пусть ребро соединяет вершины и . Пусть граф — связный. Тогда между вершинами и существует еще один путь, т.е. между вершинами и существуют два реберно-непересекающихся пути. Но тогда ребро не является мостом графа . Противоречие.

В условиях определения (4) пусть существует такие вершины и , что между ними существует простой путь . Но тогда граф — связный. Противоречие.

Возьмем и . Тогда простой путь содержит ребро . Утверждение доказано

Пусть . Пусть ребро не является мостом по определению (1).

Тогда между вершинами и есть простой путь . Составим такой путь , что . Сделаем путь простым. Получим простой путь , не проходящий по ребру . Противоречие.

Теорема (о мостах).Если ребро -мост графа , то .

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

Вспомогательная теорема: Если граф связный и его ребро -мост, то .

Допустим, это неверно и есть ребра a,b,c лежащие в разных компонентах связности G-e

Тогда как минимум 2 из них должны были лежать в одной компоненте реберной двусвязности графа G

Значит, как минимум между двумя из них были два реберно непересекающихся пути, которые не пострадали после удаления моста

То как минимум две из них связны в G-e, что противоречит условию

Лемма о мостах и циклах

Допустим, e=uv является мостом и принадлежит циклу. Тогда существует простая цепь {u,v}, которой e не принадлежит. Тогда при удалении e из графа, число компонент не увеличится, тогда e - не мост

Билет 26. Отношение вершинной двусвязности. Блоки и точки сочленения. Эквивалентные определения. Леммы про точку сочленения: о простых цепях и о единственности общей точки для двух блоков.

Теорема:

Отношение вершинной двусвязности является отношением эквивалентности на ребрах.

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

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

Замечание. Рассмотрим следующее определение: вершины и называются вершинно двусвязными, если между ними существуют 2 пути, не пересекающихся по вершинам, за исключением концов. Это определение не может претендовать на корректность, так как в этом случае отношение вершинной двусвязности перестанет быть транзитивным.

Определение:

Точка сочленения графа G — вершина, принадлежащая как минимум двум блокам G. (1)

Определение:

Точка сочленения графа G — вершина, при удалении которой в G увеличивается число компонент связности. (2)

Лемма:

Определения и эквивалентны.

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

Пусть вершина принадлежит некоторым блокам и . Вершине инцидентны некоторые ребра и . Ребра и находятся в различных блоках, поэтому не существует двух непересекающихся путей между их концами. Учитывая, что один из путей между концами - путь из в эту же вершину, получаем, что любой путь, соединяющий и , пройдет через . При удалении между и не останется путей, и одна из компонент связности распадется на две. Пусть принадлежала только одному блоку . Все вершины , смежные с , также лежат в (в силу рефлексивности отношения вершинной двусвязности). Между каждой парой вершин из существует как минимум два вершинно непересекающихся пути. Теперь удалим . Это разрушит путь , но не разрушит любой оставшийся, так как иначе он тоже прошел бы через . Рассмотрим — компоненту связности, в которой лежала . Пусть между вершинами существовал путь, проходящий через . Но он проходил также через некоторые вершины из , связность которых не нарушилась, поэтому есть как минимум еще один путь, отличный от удаленного. Противоречие: число компонент связности не увеличилось.

Теорема:

Следующие утверждения эквивалентны: — точка сочленения графа ; существуют такие вершины и , отличные от , что принадлежит любому простому пути из в ; существует разбиение множества вершин на такие два подмножества и , что для любых вершин и вершина принадлежит любому простому пути из в .

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

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

Теорема:

Пусть — связный граф с не менее чем тремя вершинами. Следующие утверждения эквивалентны: — блок ; любые две вершины графа принадлежат некоторому общему простому циклу; любая вершина и любое ребро графа принадлежат некоторому общему простому циклу; любые два ребра графа принадлежат некоторому общему простому циклу; для любых двух вершин и любого ребра графа существует простая цепь, соединяющая эти вершины и включающая данное ребро; для любых трех различных вершин графа существует простая цепь, соединяющая две из них и проходящая через третью; для каждых трех различных вершин графа существует простая цепь, соединяющая две из них и не проходящая через третью.

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

Пусть , - различные вершины графа , а - множество вершин, отличных от , которые лежат на простом цикле, содержащем . Поскольку в по крайней мере три вершины и нет точек сочленения, то в нет также мостов. Значит, каждая вершина, смежная с , принадлежит , т.е. не пусто. Предположим, что не принадлежит . Пусть - вершина в , для которой расстояние ( - )-цепь минимально. Пусть - кратчайшая простая ( - )- цепь, а и - две простые ( - )-цепи цикла, содержащего и . Так как не является точкой сочленения, то существует простая ( - )-цепь , не содержащая . Обозначим через ближайшую к вершину, принадлежащую , которая также принадлежит , и через последнюю вершину ( - )-подцепи в , которая принадлежит или , или . Не теряя общности, предположим, что ' принадлежит   . Пусть - простая ( - )-цепь, содержащая ( - )-подцепь цепи и ( - )-подцепь цепи , а - простая ( - )-подцепь, содержащая вслед за ( - ')-подцепью цепи . Ясно, что и - непересекающиеся простые ( - )-цепи. Вместе они образуют простой цикл, так что принадлежит . Поскольку принадлежит кратчайшей цепи, ( , )< ( , ). Это противоречит выбору и, следовательно, доказывает, что и лежат на одном простом цикле. Следует из того, что (2) - частный случай (3).(мб) Если принадлежит любому простому пути в , соединяющему и , то в нет простого пути, соединяющего эти вершины в . Поскольку не связен, то — точка сочленения графа .(мб)

Билет 28

28	Дерево. Эквивалентные определения. Граф блоков-точек сочленения. Док-во что он дерево. Граф компонент реберной двусвязности. Док-во что он дерево.

Дерево (англ. tree) — связный ациклический граф.

Лес (англ. forest) — граф, являющийся набором непересекающихся деревьев.

Определения

Для графа эквивалентны следующие утверждения:

1. — дерево.

2. Любые две вершины графа соединены единственным простым путем.

3. — связен и , где — количество вершин, а количество ребер.

4. — ацикличен и , где — количество вершин, а количество ребер.

5. — ацикличен и при добавлении любого ребра для несмежных вершин появляется один простой цикл.

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

7. — граф, отличный от и , а также , где — количество вершин, а количество ребер, и при добавлении любого ребра для несмежных вершин появляется один простой цикл.

Доказательство эквивалентности

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

Очевидно, что граф связен. Докажем по индукции, соотношение . Утверждение очевидно для связных графов с одной и двумя вершинами. Предположим, что оно верно для графов, имеющих меньше вершин. Если же граф имеет вершин, то удаление из него любого ребра делает граф несвязным в силу единственности простых цепей; более того, получаемый граф будет иметь в точности две компоненты. По предположению индукции в каждой компоненте число вершин на единицу больше числа ребер. Таким образом, .

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

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

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

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

Если имеет простой цикл, то он является отдельной компонентой по ранее доказанному. Все остальные компоненты должны быть деревьями, но для выполнения соотношения должно быть не более одной компоненты отличной от , так как в . Если это дерево содержит простой путь длины 2, то в можно добавить ребро так, что образуются два простых цикла. Следовательно, этим деревом является или . Значит является или , которые мы исключили из рассмотрения. Значит наш граф ацикличен. Если ациклический и , то из и верно, что — связен. В итоге получаем, что является деревом по определению.

Пусть граф связен. Обозначим — блоки, а — точки сочленения . Построим двудольный граф , поместив и в различные его доли. Если точка сочленения принадлежит блоку, проведем между ними ребро. Полученный граф называют графом блоков-точек сочленения (англ. block cutpoint graph) графа .

Лемма:

В определении, приведенном выше, — дерево.

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

Достаточно показать, что в нет циклов. Пусть — последовательные вершины , лежащие на цикле. Тогда существует последовательность точек сочленения и блоков, соединяющая и и не содержащая . По ней можно проложить путь в (можем переходить из блока в блок по точке сочленения и из одной части блока в другую) и замкнуть его в вершине , получив цикл, что противоречит тому, что — точка сочленения.

Граф компонент реберной двусвязности доказывается аналогично!

Билет 29

Лемма о безопасном ребре

Теорема:

Рассмотрим связный неориентированный взвешенный граф с весовой функцией . Пусть — подграф некоторого минимального остовного дерева , — разрез , такой, что ни одно ребро из не пересекает разрез, а — ребро минимального веса среди всех ребер, пересекающих разрез . Тогда ребро является безопасным для .

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

Достроим до некоторого минимального остовного дерева, обозначим его . Если ребро , то лемма доказана, поэтому рассмотрим случай, когда ребро . Рассмотрим путь в от вершины до вершины . Так как эти вершины принадлежат разным долям разреза, то хотя бы одно ребро пути пересекает разрез, назовем его . По условию леммы . Заменим ребро в на ребро . Полученное дерево также является минимальным остовным деревом графа , поскольку все вершины по-прежнему связаны и вес дерева не увеличился. Следовательно можно дополнить до минимального остовного дерева в графе , то есть ребро — безопасное.