Архив рубрики «Математика»

Гамма-распределение – теория вероятностей

Такой закон распределения проявляется тогда, когда отказы элементов подчинены экспоненциальному закону с интенсивностью λ0, а отказ всего объекта наступает после возникновения k отказов отдельных элементов. То есть гамма-распределение находит применение при решении задач об отказах сложных систем с резервированием.
Прочитать остальную часть записи »

Экспоненциальный закон – теория вероятностей

Экспоненциальному закону распределения подчиняется:
1. Наработка до отказа многих невосстанавливаемых изделий (лопатки паровых турбин, крепежные детали, набивка уплотнений и др.);
2. Внезапные отказы оборудования в тех случаях, когда явления износа и старения выражена слабо;
3. Наработка восстанавливаемых изделий между соседними отказами до окончания периода их приработки;
4. В ряде случаев, в первом приближении, время восстановления изделий распределено по экспоненциальному закону.
Прочитать остальную часть записи »

Закон Пуассона — теория вероятностей

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

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

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

Чаще всего на практике применяют моменты двух видов: начальные и центральные.
Прочитать остальную часть записи »

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

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

Числовые характеристики случайных величин

Числовые характеристики случайных величин

Для дискретной величины:
• функция распределения;
• ряд распределения (графический многоугольник).

Для непрерывной величины:
• функция распределения;
• плотность распределения.
Прочитать остальную часть записи »

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

Рассмотрим непрерывную случайную величину X с функцией распределения F(x), которую предположим непрерывной и дифференцируемой. Вероятность попадания этой случайной величины на участок от х до х+Δх:
F(x < X < x +Δx) = F(x +Δx) - F(x), т.е. приращение функции распределения на этом участке. Рассмотрим отношение этой вероятности к длине участка, т.е. среднюю вероятность, приходящуюся на единицу длины на этом участке, и будем приближать Δх к нулю. В пределе получим производную от функции распределения: Прочитать остальную часть записи »

Вероятность попадания случайной величины на заданный участок

График функции распределения F(x) в общем случае представляет собой график неубывающей функции, значения которой начинаются от 0 и доходят до 1, причем в отдельных точках функция может иметь скачки (разрывы).

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

Прочитать остальную часть записи »

Случайные величины и законы их распределения

Повторение опытов

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

Основные теоремы теории вероятностей

На практике обычно требуется определить вероятность событий, непосредственное экспериментальное воспроизведение которых затруднено.

Обычно такая оценка и производится с целью выявления наиболее рациональных конструктивных параметров элементов перспективной техники.
Прочитать остальную часть записи »

Лемма Бернсайда о числе орбит группы подстановок

Определение: Подстановка р:Х→Х={1,2,…,n} сохраняет элемент а (а есть неподвижная точка подстановки р), если р(а)=а.

Стабилизатор элемента а из Х группы G есть множество Ga = {p∈G: p(a) = a} всех подстановок, сохраняющих элемент а.
Прочитать остальную часть записи »

Графы и группы подстановок, орбита группы подстановок

Определение: Группа есть множество G с определенными на нем операциями: X*Y : GxG→G и взятие обратного элемента x-1: G→G и выделенным элементом 1 или е, удовлетворяющее следующим аксиомам: ∀x, y, z ∈ G:
1. x*(y*z) = (x*y)*z
2. ∃e∈G e*x = x*e = x
3. ∀x∈G ∃x-1∈G x*x-1 = x-1*x = e
Прочитать остальную часть записи »

Матричная теорема Кирхгофа о деревьях

Пусть граф G=(V,E) имеет множество вершин V={v1, …, vp} и множество рёбер Е.

Пусть А есть матрица смежности вершин для G. Пусть М есть матрица, полученная из матрицы А заменой элемента i на главной диагонали на степень вершины vi, то есть на число рёбер, принадлежащих вершине vi.
Прочитать остальную часть записи »

Теорема Кэли о числе помеченных деревьев с р вершинами

Дерево есть связный подграф без циклов.
Индукцией по числу вершин можно показать, что (p,q) дерево имеет q = p-1 рёбер.
Теорема Кэли: Число помеченных деревьев (tp) с p вершинами равно: рр-2, то есть tp = pp-2.
Прочитать остальную часть записи »

Перечисление графов. Производящая функция для числа помеченных графов с р вершинами

Определение: Пусть G=(V,E) есть (p,q)-граф, где V={v1,…,vp}-множество вершин (узлов), E={e1=(vi1, vj1), …, eq=(viq, vjq)}-множество неориентированных ребер без петель, т.е. ik ≠jk, k=1,2,…q. Пусть множество Р={1,2,…,p}. (p,q)-граф G=(V,E) является помеченным графом, если взаимнооднозначная функция f:V→P приписывает пометку для любой вершины v из V из G. Пометки f1, f2 графа G одинаковы, если существует изоморфизм φ: G→G , сохраняющий пометки вершин f1(v)=f2(φ(v)).
Прочитать остальную часть записи »

Теорема Форда-Фалкерсона о максимальном потоке

Теорема (Форда-Фалкерсона) о максимальном потоке: всякая транспортная сеть имеет максимальный поток и его величина Mf = cmin.
Прочитать остальную часть записи »

Потоки в транспортных сетях

Двухполюсные графы
Определение: Двухполюсная сеть S = (V,E,s,t) есть ориентированный граф G = (V,E) с двумя выделенными вершинами (полюсами) s – входная вершина (Исток) t – выходная вершина (Сток).

Определение: Внутренние вершины сети есть вершины, отличные от полюсов. Полюсная дуга сети инцидентна одному из полюсов. Пусть S = (V,E,s,t) — есть сеть и вершина v∈V. Введем следующие обозначения: D+(v) – множество дуг сети, исходящих из v. D(v) множество дуг сети, входящих в v. D(v) – множество дуг сети, инцидентных вершине v.
Прочитать остальную часть записи »

Раскрашивание планарных графов. Теорема о пяти красках. Теорема о четырех красках

Теорема (о пяти красках, Теорема Хивуда): Всякий связный планарный граф G можно правильно раскрасить не более чем 5-ю красками.

Доказательство: Индукцией по числу p вершин графа.
Базис: Для графа с числом вершин p= k ≤ 5 Теорема очевидна, ибо всякие 5 вершин раскрашиваемы 5-ю различными красками.
Прочитать остальную часть записи »

Оптимальная раскраска вершин графа

Пусть граф G = (V,E) правильно раскрашен. Вершины, окрашенные в один цвет, образуют внутреннее устойчивое множество вершин в G. Хроматическое число графа G можно определить как минимальное число внутренне устойчивых множеств, в сумме дающих все множество V. Такое минимальное покрытие можно найти следующим образом. Пусть S1, S2, …,Sк – есть все максимальные внутренне устойчивые множества вершин в G. С каждым Si свяжем логическую переменную XSi означающую, что вершина v ∈Si. Построим логическую формулу – условие оптимальной раскраски вершин графа G: F = &v∈V(∨v∈SiXSi). Взяв по одной переменной в каждой скобке формулы F, получим некоторую конъюнкцию XSa*XSb*…*XSc, для которой семейство внутренне устойчивых множеств {Sa, Sb,…,Sc} в сумме покрывает все множество V. Пусть ∨iKi – есть минимальная ДНФ D для формулы F. Пусть дизъюнктивному слагаемому Ki = XSj1*XSj2*…*XSjk в D соответствует наименьшее по длине k семейство Li = {Sj1, Sj2,…,Sjk} новых вершин. Хроматическое число χ(G) = k. Ему соответствует следующая оптимальная раскраска вершин графа G. В цвета 1,2,…, k последовательно окрашено семейство вершин Sj1, Sj2-Sj1, Sj3-(Sj1∪Sj2),…., Sjk – (Sj1∪…∪Sjk-1) соответственно.
Прочитать остальную часть записи »

Верхняя и нижняя оценки для хроматического числа. Внутренне и внешне устойчивые множества вершин графа

Теорема (верхняя оценка): если граф G имеет максимальную степень вершины, равную S, то хроматическое число χ(G) ≤ S+1.

Доказательство: Индукцией по числу p вершин.
Базис: Если число вершин в графе G не превосходит S+1, то Теорема тривиально справедлива, ибо S+1 вершин можно правильно раскрасить в S+1 цветов. По 1-му цвету на каждую вершину.
Прочитать остальную часть записи »

Двудольные и бихроматические графы

Определение: Граф G с хроматическим числом χ(G)=2 называется бихроматическим.

Теорема: Граф G двудолен ⇔ G есть бихроматический граф.

Необходимость⇒: пусть G = (V1,V2,E) есть двудольный граф. Вершины из V1 окрасим в один цвет, а вершины из V2 в другой. Полученная раскраска вершин – правильна, ибо соседние раскрашенные вершины, одна из V1, другая из V2, окрашена в разные цвета. Следовательно, граф есть бихроматический.
⇐Достаточность: Пусть G есть бихроматический граф, тогда множество его вершин можно разбить на два класса:
V1 – вершины из G, окрашенные в один цвет.
V2 – вершины из G, окрашенные в другой цвет.
Прочитать остальную часть записи »

Раскраска графов, хроматическое число и хроматический класс

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

Замечание: Всякий подграф правильно раскрашенного графа также правильно раскрашен.
Прочитать остальную часть записи »

Графы К5 и К33. Критерий планарности Понтрягина-Куратовского

Утверждение: Полный граф K5 – не планарен.

Доказательство: допустим противное – граф K5 планарен и G есть его плоская укладка. Т.к. граф K5 и G изоморфны, то каждое ребро G есть 3-цикл. Положим n=3, p=5, q=10, получаем 10 ≤ 3*(5-2) / (3-2) = 9 ⇒ что противоречит условию ⇒ граф K5 – не планарен.
Прочитать остальную часть записи »

Формула Эйлера

Формула Эйлера: в любом связном плоском графе числа p,q,r его вершин, ребер, граней соответственно связаны равенством Эйлера (p-q+r=2)

Доказательство: Индукцией по числу q ребер.
Базис: q=0 ⇒ p – q + r = 1 – 0 + 1 = 2
Предположение индукции: Допустим, что формула Эйлера справедлива для всех связных плоских графов с числом ребер < q. Прочитать остальную часть записи »

Планарные и плоские графы

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

Системы различных представителей, теорема Холла о совершенном паросочетании в двудольном графе

Определение: Система различных представителей для семейтсва конечных множеств S = {A1, A2,..,Ai,…,Am} есть система попарно различных элементов {a1, a2,…, ai,…, am}, для которых ai ∈ Ai [i=1,2…m].
Прочитать остальную часть записи »

Двудольные графы и парасочетания

Определение: Граф G = (V,E) называется двудольным графом (биграфом), если множество V его вершин допускает разбиение на 2 непересекающихся подмножества V1 и V2 (две доли). Причем каждое ребро графа соединяет вершины из различных долей. Обозначается через G = (V1,V2,E) – двудольный граф с долями V1 и V2. Будем считать, что |V1| ≤ |V2|.
Прочитать остальную часть записи »

Циклический ранг графа

Определение: Циклический ранг CR(G) или цикломатическое число графа G есть размерность подпространства четных подграфов линейного пространства всех подграфов графа G.
Прочитать остальную часть записи »

Фундаментальная система циклов

Определение: Фундаментальная система циклов есть базис линейного пространства всех четных подграфов данного графа.
Прочитать остальную часть записи »

Подпространство четных подграфов

Пусть G есть (p,q) – граф и LGq есть линейное пространство всех подграфов графа G.

Теорема: Множество Lчет всех четных подграфов графа G образует подпространство линейного пространства LGq всех подграфов графа G.
Прочитать остальную часть записи »




Статистика