2. Реберный граф

46. Для произвольного графа реберный граф определяется следующими двумя условиями:

• ,

• вершины и смежны в тогда и только тогда, когда ребра и смежны в .

22. Реберный граф:

3. Операции над графами

• Объединение. Граф называется объединением (или наложением) графов и , если , . В этом случае пишут .

23. Объединение графов:

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

• Дополнение графа до полного (или просто дополнение). Граф называется дополнением графа до полного, если у него , а определяется следующим образом: вершины и смежны, если они не являются смежными в графе .

24. Дополнение графа:

• Дополнение подграфа до графа . Пусть – подграф графа . Граф называется дополнением до , если у него , а определяется следующим образом: вершины и смежны, если они не смежны в графе , но смежны в .

• Соединение. Граф называется соединением графов и , если , ,

5. – множество всех дуг, соединяющих вершины из разных графов.

В этом случае пишут .

25. Соединение графов:

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

26. Произведение графов:

1. Основные понятия теории вероятностей. Классическое, статистическое и геометрическое определения вероятности, свойства вероятности.

1)Основные понятия теории вероятностей.

Теория вероятностей – математическая наука, изучающая закономерности в случайных явлениях. Одним из основных понятий теории вероятностей является понятие случайного события (или просто события).

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

К понятию «вероятность» существует несколько подходов.

Современное построение теории вероятностей основывается на аксиоматическом подходе и опирается на элементарные понятия теории множеств. Такой подход называется теоретико-множественным.

Пусть производится некоторый опыт со случайным исходом. Рассмотрим множество W всех возможных исходов опыта; каждый его элемент   будем называть элементарным событием, а множество ? –пространством элементарных событий. Любое событие A в теоретико-множественной трактовке есть некоторое подмножество множества ?:  .

Достоверным называется событие W, которое происходит в каждом опыте.

Невозможным называется событие ?, которое в результате опыта произойти не может.

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

Суммой (объединением) двух событий A и B (обозначается A+B, A?B) называется такое событие, которое заключается в том, что происходит хотя бы одно из событий, т.е. A или B, или оба одновременно.

Произведением (пересечением) двух событий A и B (обозначается A?B, A?B) называется такое событие, которое заключается в том, что происходят оба события A и B вместе.

Противоположным к событию A называется такое событие  , которое заключается в том, что событие A не происходит.

События A_k (k=1, 2, …, n) образуют полную группу, если они попарно несовместны и в сумме образуют достоверное событие.

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

Р (A) = m / n,

где m — число элементарных исходов, благоприятствующих A; n — число всех возможных элементарных исходов испытания.

Здесь предполагается, что элементарные исходы несовместны, равновозможны и образуют полную группу. Из определения вероятности вытекают следующие ее свойства: Св о й с т в о 1. Вероятность достоверного события равна единице.Действительно, если событие достоверно, то каждый элементарный исход испытания благоприятствует событию. В этом случае m = n, следовательно,

Р (A) = m / n = n / n = 1.

С в о й с т в о 2. Вероятность невозможного события равна нулю.Действительно, если событие невозможно, то ни один из элементарных исходов испытания не благоприятствует событию. В этом случае m = 0, следовательно,

Р (А) = m / n = 0 / n = 0.

С в о й с т в о 3. Вероятность случайного события есть положительное число, заключенное между нулем и единицей.Действительно, случайному событию благоприятствует лишь часть из общего числа элементарных исходов испытания. В этом случае 0 < m < n, значит, 0 < m / n < 1, следовательно,

0 < Р (А) < 1

.Итак, вероятность любого события удовлетворяет двойному неравенству

0 <= Р (A) < 1.

Статистическое определение вероятности

При рассмотрении результатов отдельных испытаний очень трудно найти какие-либо закономерности. Однако в последовательности одинаковых испытаний можно обнаружить устойчивость некоторых средних характеристик. Частостью какого-либо события в данной серии из n испытаний называется отношение m/n, числа m тех испытаний, в которых событие А наступило, к общему числу испытаний n. Почти в каждой достаточно длинной серии испытаний частость события А устанавливается около определенного значения  , которое принимается за вероятность события А. Устойчивость значения частости подтверждается специальными экспериментами. Статистические закономерности такого рода были впервые обнаружены на примере азартных игр, т. е. на примере тех испытаний, которые характеризуются равновозможностью исходов. Это открыло путь для статистического подхода к численному определению вероятности, когда нарушается условие симметрии эксперимента. Частость события А называют статистической вероятностью, которая обозначается

,

(1.2)

где m_A — число экспериментов, в которых появилось событие А; n — общее число экспериментов.

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