Вероятностный метод, Алон Н., Спенсер Д., 2013.
Одна из самых известных зарубежных книг в области применения вероятностных методов в комбинаторике. В книге содержатся основные элементы методологии. Строгие обоснования и доказательства сопровождаются ясными и неформальными обсуждениями задач, методов и их приложений. Каждый метод иллюстрируется целым рядом точно подобранных примеров.
Для специалистов в области дискретной математики и теории случайных графов, студентов, аспирантов и преподавателей соответствующих дисциплин.
ВЕРОЯТНОСТНЫЙ МЕТОД.
Вероятностный метод является мощным инструментом для решения многих задач дискретной математики. Грубо говоря, этот метод работает следующим образом: пытаясь доказать, что структура с некоторыми искомыми свойствами существует, мы определяем подходящее вероятностное пространство структур, а затем показываем, что искомые свойства выполняются для случайно выбранного элемента в этом пространстве с положительной вероятностью.
Метод лучше всего проиллюстрировать примерами. Ниже — один из них. Число Рамсея R(k, l) есть наименьшее целое n, такое, что при любой раскраске ребер полного n-вершинного графа в синий и красный цвета либо существует красный подграф Кk (т. е. полный подграф на к вершинах, каждое ребро которого раскрашено в красный цвет), либо существует синий подграф Kl. В 1929 г. Рамсей показал, что число R(k,l) конечно для любых k и l. Мы найдем нижнюю оценку для диагонального числа Рамсея R(k,k).
Купить .
Дата публикации:
Теги: учебник по математике :: математика :: Алон :: Спенсер
Смотрите также учебники, книги и учебные материалы:
Следующие учебники и книги:
Предыдущие статьи:
