Графы. Реализация графов на плоскости. Деревья.

Определение: Графом G (в широком понимании) называется любая пара (V,E), где V = {v₁, v₂, ... } - множество вершин графа, а E = {e₁, e₂, ... } – множество неориентированных ребер, причем допускаются пары вида (v_i, v_i) и одинаковые пары. Если пары в V рассматриваются как неупорядоченные, то граф называется неориентированным, если как упорядоченные, то граф называется ориентированным(орграфом).

Элементы множества V называются вершинами графа, а пары из E - его ребрами; в орграфе они называются ориентированными ребрами или дугами.

Говорят, что ребро e = (u,v) в неориентированном графе соединяет вершины u и v, а в ориентированном графе дуга e = (u,v) идет из вершины u в вершину v.

Пара вида (v_i, v_i) называется петлей в вершине v_i(т.е. повторяются вершины в множестве). Если пара (v_i, v_j) встречается в E более одного раза, то говорят, что (v_i, v_j) - кратное ребро.

Определение: Говорят, что вершины v_i и v_j смежны в графе G = (V,E), если в E входит пара (v_i, v_j) или (v_j, v_i). Говорят, что ребро (дуга) (v_i, v_j) инцидентно вершинам v_i и v_j.

Определение: Смешанные графы - графы, в которых часть ребер ориентированы, а часть – нет.

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

Определение: Путем в графе (орграфе) G = (V,E) называется последовательность вершин и ребер (дуг) вида v₀, (v₀, v₁), v₁, ... , v_n-1, (v_n-1, v_n), v_n, где все v_i ℮ E и все (v_i, v_i+1) ℮ E. Длина пути - это число ребер (дуг) в нем. Говорят, что этот путь идет из v₀ в v_n.

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

Определение: Путь называется циклом, если v_n = v₀ и ребра (дуги) не повторяются(т.е. начальная и конечная вершины совпадают). Путь называется простым циклом, если v_n = v₀ и больше нет повторений вершин.

Определение: Граф G = (V,E) называется связным, если для любых двух вершин v_i, v_j О V в G существует путь из v_i в v_j.

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

Определение: Граф G = (V,E) называется деревом, если он связный и не содержит циклов. Вершины степени 1 в дереве называют его листьями.

Пусть задан неориентированный граф G = (V,E). Пусть каждой вершине v_i из V сопоставлена точка a_i в некотором евклидовом пространстве, причем ai ≠ a_j при i ≠ j. Пусть каждому ребру e = (v_i, v_j) из E сопоставлена непрерывная кривая L, соединяющая точки a_i и a_j и не проходящая через другие точки a_k. Тогда если все кривые, сопоставленные ребрам графа, не имеют общих точек, кроме концевых, то это множество точек и кривых называется геометрической реализацией графа G.

Теорема. Каждый конечный граф G можно реализовать в трехмерном евклидовом пространстве (без пересечения ребер).

Определение: Граф называется планарным, если существует его планарная реализация, то есть геометрическая реализация на плоскости (без пересечения ребер).

Определение:Связный граф называется Эйлеровым, если в нем присутствует цикл, содержащий все ребра.

Теорема. (формула Эйлера.) Для любой планарной реализации связного планарного графа G = (V,E) с p вершинами, q ребрами и r гранями выполняется равенство: p-q+r = 2.

Критерий Эйлера: граф является Эйлеровым т. и т. т., когда он связный и все степени его вершин четны.

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

Правило суммы: пусть имеется n попарно непересекающихся множеств A₁, A₂, …, A_n , содержащих m₁, m₂, …, m_n элементов соответственно. Число способов, которыми можно выбрать один элемент из всех этих множеств, равно m₁ + m₂ + … + m_n.

Пример. Если на первой полке стоит X книг, а на второй Y, то выбрать книгу с первой или второй полки, можно X+Y способами.

Пример. Ученик должен выполнить практическую работу по математике. Ему предложили на выбор 17 тем по алгебре и 13 тем по геометрии. Сколькими способами он может выбрать одну тему для практической работы?

Решение: По правилу суммы получаем 17+13=30 вариантов.

Кортеж - конечная последовательность (допускающая повторения) элементов какого-нибудь множества.

Правило произведения: пусть имеется n множеств A₁, A₂, …, A_n содержащих m₁, m₂, …, m_n элементов соответственно. Число способов, которыми можно выбрать по одному элементу из каждого множества, т. е. построить кортеж (а₁, а₂, ..., а_n), где а_i Î А _i1 (i = 1, 2, …, n), равно m₁ · m₂ · … · m_n.

Пример. Если на первой полке стоит 5 книг, а на второй 10, то выбрать одну книгу с первой полки и одну со второй можно 5*10=50 способами.

Пример. Переплетчик должен переплести 12 различных книг в красный, зеленый и коричневые переплеты. Сколькими способами он может это сделать?

Решение. Имеется 12 книг и 3 цвета, значит по правилу произведения возможно 12*3=36 вариантов переплета.

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

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

Пример. Из цифр 1, 2, 3, 4, 5 можно составить следующие трехзначные числа 123, 431, 524, ...и т.д. Это упорядоченные трехэлементные выборки, так как 123 и 132 - разные числа.

Пример. Из 20 учащихся класса выбрать двух дежурных. Любая пара дежурных представляет собой неупорядоченную двухэлементную выборку, так как порядок их выбора не важен.

Размещения

Размещениями из n элементов по m элементов (m < n) называются комбинации, составленные из данных n элементов по m элементов, которые отличаются либо самими элементами, либо порядком элементов.

Число размещений без повторений из n по m (n различных элементов) вычисляется по формуле:

(3.1)

Размещениями с повторениями из n элементов по m называются упорядоченные m-элементные выборки, в которых элементы могут повторяться.

Число размещений с повторениями вычисляется по формуле:

(3.2)

Пример. Возьмем буквы Б, А, Р. Какие размещения из этих букв, взятых по две, можно получить? Сколько таких наборов получиться, если: 1) буквы в наборе не повторяются; 2) буквы могут повторяться?

Решение.

1. Получатся следующие наборы: БА, БР, АР, АБ, РБ, РА.

По формуле (3.1) получаем: наборов.

2. Получатся наборы: ББ, БА, БР, АА, АБ, АР, РР, РБ, РА.

Перестановками из n элементов называются размещения из этих n элементов по n (Перестановки - частный случай размещений).

Число перестановок без повторений (n различных элементов) вычисляется по формуле:

(3.3)

Число перестановок c повторениями (k различных элементов, где элементы могут повторяться m₁, m₂, …, m_k раз и m₁ + m₂ +… + m_k = n, где n - общее количество элементов) вычисляется по формуле:

(3.4)

Пример. Возьмем буквы Б, А, Р. Какие перестановки из этих букв можно получить? Сколько таких наборов получится, если: 1) буквы в наборе не повторяются; 2) буква А повторяется два раза?

Решение.

1. Получатся наборы: БАР, БРА, АРБ, АБР, РАБ, РБА.

Число сочетаний без повторений (n различных элементов, взятых по m) вычисляется по формуле:

Число сочетаний c повторениями (n элементов, взятых по m, где элементы в наборе могут повторяться) вычисляется по формуле:

(3.6)

Пример. Возьмем буквы Б, А, Р. Какие сочетания из этих букв, взятых по две, можно получить? Сколько таких наборов получится, если: 1) буквы в наборе не повторяются; 2) можно брать по два одинаковые буквы.

Решение.

1. Получатся наборы: БА (БА и АБ - один и тот же набор), АР и РБ

По формуле (3.5) получаем: наборов.

2. Получатся наборы: ББ, БА, БР, АА, АР, РР.

По формуле (3.6) получаем: наборов.

Пример. Из 20 учащихся надо выбрать двух дежурных. Сколькими способами это можно сделать?

Решение. Надо выбрать двух человек из 20. Ясно, что от порядка выбора ничего не зависит, то есть Иванов-Петров или Петров-Иванов - это одна и та же пара дежурных. Следовательно, это будут сочетания из 20 по 2.

По формуле (3.5) получаем: способов.

Пример. В хлебном отделе имеются булки белого и черного хлеба. Сколькими способами можно купить 6 булок хлеба?

Решение. Обозначая булки белого и черного хлеба буквами Б и Ч, составим несколько выборок: ББББББ, ББЧЧББ, ЧЧЧЧЧБ, ... Состав меняется от выборки к выборке, порядок элементов несущественен, значит это - сочетания с повторениями из 2 по 6. По формуле (3.6) получаем способов.

Cделаем проверку и выпишем все варианты покупки: ББББББ, БББББЧ, ББББЧЧ, БББЧЧЧ, ББЧЧЧЧ, БЧЧЧЧЧ, ЧЧЧЧЧЧ. Их действительно 7.

 

 

№5.

Вероятностное пространство.Свойства σ-алгебры и вероятности.Теорема о непрерывности вероятности.Примеры вероятостных пространств.

 

Определение1: Класс F - подмножествo Ω, то пара (Ω,F) называется σ-алгеброй, если F удовлетворяет условиям:

1. ΩϵF ;

2. Если AϵF, то

3. Если

Если F-σ-алгебра подможетв пространства Ω, то пара (Ω,F) называется измеримым пространством.

Определение 2: Пусть (Ω,F) – измеримое пространство. Функция множеств Р(.): F->[0;1], удовлетворяющая условиям:

1. Р(Ω)= 1.

2.если ( ϵ F, ∩ , при i ≠j, то Р( )= – называется вероятностью.

При этом (Ω,F,P(.)) называется вероятностным пространством, а свойства 1 и 2 – аксиомами вероятностного пространства, Ω – называется пространством элементарных событий, элементы σ-алгебры F называются случайными событиями.

Теорема о непрерывности вероятности:

Пусть (Ω,F,P)- вероятностное пространство. Тогда:

1. Если ϵ F , , nϵN, то )

2. Если ϵ F , , nϵN, то )

 

6 Условная вероятность. Независимость

Определение 6.1. Условной вероятностью случайного события А относительно слу­чайного события B , имеющего ненулевую вероятность, называется

P(A|B) =

Теорема 6.1. (Формула полной вероятности). Пусть А - случайное событие; J - ко­нечное или счетное множество; ( ) - семейство случайных событий, удовлетворяющее

условиям: P ( ) ≠ 0 для каждого jϵJ, ∩ = Ø при i ≠ j, А⊂ . Тогда

P (А) =

Теорема 6.2. (Формула Байеса). Пусть выполнены условия теоремы 5.1. и P(А)≠0. Тогда

 

Определение 6.2. События А и B называются независимыми, если

P(А∩B) =P(A)P(B).

Определение 5.3. События A₁,...,A_n называются независимыми в совокупности, если

P( ∩… )=P( P(

 

для любого k, 1<k≤n, и для любых j₁, … , таких, что 1 j₁ < … < ≤ n.

События А₁, А₂, … называются независимыми в совокупности, если для любого n > 1 события А₁, …, А_n независимы в совокупности.

Утверждение 5.3. Пусть А₁, … , А_n - независимые в совокупности события, Bj = Aj либо Bj = , j = 1, … , n. Тогда B₁, … , B_n - независимые в совокупности события.

 

 

Вопрос № 37.

Случайная величина. Функция распределения случайной величины. Плотность распределения. Примеры вероятностных пространств и случайных величин.

Определение: Пусть (W, f) и (Х, В) - два измеримых пространства. Функция x(·): W®Х (с областью определения W и множеством значений в Х) называется f |В - измеримой, если

x^-1(В) = {w | x(w)ÎВ}Îf " ВÎВ.

Определение: Пусть (W, f, P) - вероятностное пространство и (Х, В) - некоторое измеримое пространство. f |В - измеримая функция x: W®Х называется случайным элементом.

В частном случае, когда X=R¹, B= B(R¹) функцию x называют случайной величиной.

Если X = Rⁿ, B = B(Rⁿ) функцию x называют случайной вектором.

 

Пусть (W, f, P) - вероятностное пространство. Пусть x - случайная величина, определённая на этом пространстве.

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

1) F_x(x) = P{x £ x}, xÎR называется функцией распределения случайной величины x.

2) Q_x(B) = P{xÎ B}, BÎB(R ) называется распределением случайной величины x.

3) Если существует борелевская функция f_x(x): P{xÎ B}= , " BÎB(R ), то f_x(x) называется плотностью распределения случайной величины x.

4) Если множеством значений случайной величины x является не более чем счётное

{x₁, …}Ì R, то говорят, что x - дискретная случайная величина, а набор вероятностей р(к) = Р{x = х_к} к = 1, 2, …называется распределением дискретной случайной величины:

р(к) ³ 0 и р_к = Р{x = х_к}= (в силу аддитивности) = Р( {x = х_к}) = Р(W) = 1.

 

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

1) Если -¥ < a < b < +¥ |Þ F_x(a) £ F_x(b). P{a < x £ b}= F_x(b) - F_x(a).

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

Рассмотрим {x £ a}, {x £ b} {x £ a}Ì{x £ b}, {a < x £ b}={x £ b}\{x £ a}.

2) F_x(x) = 1, F_x(x) = 0.

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

В силу монотонности F_x достаточно показать, что F_x(n) = 1, F_x(-n) = 0.

1⁰ Рассмотрим события {x £ n}Ì{x £ n+1}- последовательность монотонно возрастает |Þ

{x £ n}= {x £ n} = {x < ¥} Р{|x| = ¥}= 0.

F_x(n) = Р{x £ n}= Р{x < ¥}= 1.

2⁰ {x £ -n}É{x £ -(n+1)}- монотонно убывает |Þ {x £ -n}= {x £ -n} = {x = -¥}

F_x(-n) = Р{x £ -n}= Р{x = -¥}= 0. (что и требовалось доказать)

3) Функция F_x(x) непрерывна справа в каждой точке, т.е. если x < x_n+1 < x_n; x_n = x, то

F_x(x_n) = F_x(x).

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

Рассмотрим {x £ x_n}É{x £ x_n+1}- последовательность событий |Þ последовательность монотонно убывает и {x £ x_n}= {x £ x_n}= {x £ x}.

F_x(x_n) = Р{x £ x_n}= P{x £ x}.

4) F_x(y) = P{x < x}.

Надо доказать, что если x_n < x_n+1 < x и x_n = x, то F_x(x_n) = P{x < x}.

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

{x £ x_n}Ì{x £ x_n+1}.

{x £ x_n}= {x £ x_n} = {x < x}.

F_x(x_n) = Р{x £ x_n}= (по теоремы о непрерывности меры) = Р{x < x}.

{x £ x_n}= {x £ x} {x £ x_n} = {x £ x}

] ] ] ] ] |

x x_n x_n ® x

5) P{x = x} = F_x(x) - F_x(x-).

Доказательство: {x = x}={x £ x}\{x < x}. Значит Р{x = x}=Р{x £ x}- Р{x < x}.

6) Пусть x - дискретная случайная величина принимающая значения {x₁, x₂, …} с вероятностями {р(1), р(2), …}.

F_x(x) = P{x £ x}= P({x £ x}ÇW) = (где W = {x = х_к}) = Р( {x £ x, x = х_к}) =

= Р{x £ x, x = х_к}= P(k).

 

Определение: Функция F(x), xÎR называется функцией распределения, если она обладает свойствами:

1) F(x) монотонно не убывает,

2) F(x) непрерывна справа,

3) F(x) = 1, F(x) = 0.

Теорема: 1) Если Q - распределение на (R, B(R )), то F(x) = Q(]-¥, x]) является функцией распределения, xÎR.

2) Если F(x) - функция распределения, то $ распределение Q на (R, B(R )): F(x) = Q(]-¥, x])

" xÎR.

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

1) а) a < b Þ Q(]-¥, a]) £ Q(]-¥, b]) в силу монотонности меры.

b) если x < x_n+1 < x_n : lim x_n = x, то Q(]-¥, x_n]) = Q(]-¥, x]).

c) Q(]-¥, n]) = Q(R) = 1, Q(]-¥, -n]) = Q(Æ) = 0.

2) Если F(x) - функция распределения Þ $! Q(·) на (R, B(R )): Q(]a, b]) = F(b) - F(a).

Q(]a, b]) = Q(]-¥, b]) = F(b).

Q(R ) = Q(]-¥, b]) = 1. (что и требовалось доказать)

Следствие 1: Пусть F - функция распределения. Тогда $ (W, f, P) - вероятностное пространство и x определённая на этом пространстве: F(x) = P{x £ x}.

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

Положим W = R, f = B(R ), P - распределение соответствующее F. Определим

x(w): x(w) = w. P{x £ x} = P{w: x(w) £ x} = P(]-¥, x]) = F(x).

Определение.Cлучайная величина ξ имеет абсолютно непрерывное распределение, если существует неотрицательная функция такая, что для любого борелевского множества B имеет место равенство:

Функцию называют плотностью распределения случайной величины ξ .

Замечание.Интеграл выше есть интеграл Лебега. При этом площадь над множеством B, имеющим нулевую меру Лебега, равна нулю. Заметим, что любая функция, отличающаяся от функции лишь в конечном или счётном числе точек (или на множестве нулевой меры Лебега), будет являться плотностью того же распределения, так как интеграл не изменится от изменения подынтегральной функции на множестве меры нуль.

Теорема.Плотность распределения обладает свойствами:

(f1) для любого x; (f2) .

Доказательство. (f1) выполнено по определению плотности, (f2) также следует из определения:

QED

Эти два свойства полностью характеризуют класс плотностей:

Теорема .Если функция f обладает свойствами (f1) и (f2), то существует вероятностное пространство и случайная величина ξ на нём, для которой f является плотностью распределения.

Доказательство.Пусть Ω есть область, заключенная между осью абсцисс и графиком функции f. Площадь области Ω равна единице по свойству (f2). Пусть F — множество борелевских подмножеств Ω, а P — мера Лебега (площадь) на множествах из F. И пусть случайная величина ξ есть абсцисса точки, наудачу брошенной в эту область.

Тогда для любого выполнено:

(10)

Здесь область есть криволинейная трапеция под графиком плотности, с основанием B. По определению, равенство (10) означает, что функция f является плотностью распределения случайной величины ξ

QED

 

Если бросается игральная кость, то в результате верхней гранью может оказаться одна из шести граней с количеством точек от одной до шести. Выпадение какой-либо грани в данном случае в теории вероятностей называется элементарным событием ^[1], то есть

· — грань с одной точкой;

· — грань с двумя точками;

· ...

· — грань с шестью точками.

Множество всех граней образует пространство элементарных событий , подмножества которого называются случайными событиями ^[1]. В случае однократного подбрасывания игровой кости примерами событий являются

· выпадение грани с нечётным количеством точек, то есть событие — это выпадение грани с одной точкой или грани с тремя точками, или грани с пятью точками). Математически событие записывается как множество, содержащее элементарные события: , и . Таким образом, ;

· выпадение грани с чётным количеством точек, то есть событие — это выпадение грани с двумя точками или грани с четырьмя точками, или грани с шестью точками. Математически событие записывается как множество, содержащее элементарные события: , и . Таким образом, ;

 

 

Вопрос 38

Предыдущая12345678910111213141516Следующая