Дискретная математика в анализе продвижения «ПолиВита»

Для успешной реализации пунктов 1 - 4 стратегии требуется оценка скорости распространения информации, а также необходимых для этого людских и финансовых ресурсов.

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

Отличие случайного графа от обычного заключается в том, что ребра случайного графа проводятся с некоторой заданной вероятностью р. Для случайного графа имеется ряд нетривиальных результатов, полученных выдающимися математиками 20-го века, такими как П. Эрдёш, А. Реньи и др., например теорема Эрдеша-Реньи:

Если p ≤ c/n при с < 1, то с вероятностью, стремящейся к 1 при n, стремящемся к бесконечности, все связные компоненты случайного графа имеют O(ln n) вершин.

Если p ≥ c/n при с > 1, то с вероятностью, стремящейся к 1 при n, стремящемся к бесконечности, в случайном графе есть только одна связная компонента с числом вершин O(n).

Рис. 1 иллюстрирует эту теорему для заданного n (сверху отложена возрастающая вероятность p проведения ребра случайного графа).

Рис. 1. Иллюстрация теоремы Эрдёша-Реньи

Теоретическая основа: Райгородский А.М. Модели случайных графов. — М.: МЦНМО, 2011, 136 стр.

Книга посвящена теории случайных графов. Эта теория находится на стыке комбинаторики, теории графов и теории вероятностей. Книга основана на лекциях, которые автор читал на школах «Современная математика» в Дубне и «Комбинаторная математика и теория алгоритмов» в Судиславле, а также в Школе Анализа Данных Яндекса.

Книга предназначена для широкого круга читателей.

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

— полный граф на n вершинах (все его рёбра — синие)	— все рёбра красные — все рёбра синие

Рис. 2.

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

Число Рамсея симметрично по параметрам s и t:

.

Для чисел Рамсея установлено такое неравенство:

.

Используя условие получается оценка что означает, что число Рамсея всегда конечно. Что же касается оценок числа Рамсея при других s, то известно лишь, что:

Для диагонального числа Рамсея R (s,s) существует оценка: