Дискретная математика в анализе продвижения «ПолиВита»
Для успешной реализации пунктов 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 стр.
Книга посвящена теории случайных графов. Эта теория находится на стыке комбинаторики, теории графов и теории вероятностей. Книга основана на лекциях, которые автор читал на школах «Современная математика» в Дубне и «Комбинаторная математика и теория алгоритмов» в Судиславле, а также в Школе Анализа Данных Яндекса. Книга предназначена для широкого круга читателей.
Другим аспектом применения дискретной математики при продвижении Поливита является использование результатов теории Рамсея. Суть этой теории состоит в поиске регулярных подструктур в хаотических структурах.
Рис. 2. Пусть незнание группы из n потребителей о Поливите изображает полный граф (см. Рис. 2 слева). Будем считать все его ребра синими и назовем его . Распространение знаний о Поливите среди n потребителей будем характеризовать перекрашиванием синих ребер графа в красный цвет (см. Рис. 2 справа). Тогда числом Рамсея R (s,t) при заданных s, t (s — число синих рёбер, t — число красных рёбер) называется минимальное число n вершин графа , при котором существует полный подграф графа , у которого все ребра — красные, или полный подграф графа , у которого все ребра — синие, т. е.: Число Рамсея симметрично по параметрам s и t: . Для чисел Рамсея установлено такое неравенство: . Используя условие получается оценка что означает, что число Рамсея всегда конечно. Что же касается оценок числа Рамсея при других s, то известно лишь, что: Для диагонального числа Рамсея R (s,s) существует оценка:
Популярное: Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние... Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы... Как построить свою речь (словесное оформление):
При подготовке публичного выступления перед оратором возникает вопрос, как лучше словесно оформить свою... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (512)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |