Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Числа Рамсея.






Число Рамсея R(k, m) это наименьшее число n такое, что в любом графе с n вершинами, найдутся либо k попарно смежных, либо m попарно несмежных.

Теорема Рамсея гарантирует существование чисел Рамсея для любых k и m. Таким образом можно говорить о содержании в бесконечном графе высокоорганизованной структуры любой сложности. Но об этом позже (быть может). А пока хочется остановиться на числах Рамсея. Для удобства перефразируем определение:
Число Рамсея R(k, m) это наименьшее число n такое, что в любом полном графе с n вершинами, ребра которого раскрашены в красный и синий цвета, найдется либо подграф с k вершинами, все ребра которого окрашены в красный цвет, либо подграф с m вершинами, все ребра которого окрашены в синий цвет.
Чтобы понять сложность вычисления чисел Рамсея, то следует отметить что число R(5, 5) до сих пор не найдено.
Можно заметить три очевидных факта, касающихся чисел Рамсея:

1. R(k, m) = R(m, k)

2. R(1, m) = 1

3. R(2, m) = m

 

Остальные числа вычисляются индивидуально.

Задача о вычислении R(3, 3) известна как "задача о вечеринке": среди любых 6 человек найдется либо 3 попарно знакомых, либо 3 попарно незнакомых. Другими словами R(3, 3) <= 6. Доказательство строится следующим образом (в терминах второго приведенного определения):
Изобразим граф с шестью вершинами и возьмем одну из них - A:

Вершина A соединена с пятью другими вершинами (красными и синими ребрами). Без ограничения общности можно считать, что она соединена красными ребрами по крайней мере с тремя вершинами - B, C, D. Далее, если одно из ребер BC, CD, BD красное (например BC), то имеем красный треугольник (ABC). Если же все они синие, то BCD - синий треугольник. Конец доказательства.
Имея в виду то, что число 5 не удовлетворяет требованиям задачи, получаем R(3, 3) = 6.
Дальше докажем, что R(3, 4) = 9. Сначала установим, что R(3, 4) > 8. Для этого достаточно привести пример раскраски графа из 8 вершин, не содержащего красных треугольников и полных синих подграфов из 4 вершин:

Осталось доказать, что полный граф из 9 вершин так раскрасить нельзя. Допустим, такая раскраска возможна. Будем рассуждать как в предыдущем доказательстве. Возьмем одну из вершин (A), с остальными вершинами она соединена 8 ребрами. Пусть k из них покрашены в красный цвет, а остальные 8-k - в синий.
Если k >= R(2, 4) = 4, то A соединена красными ребрами хотя бы с четырьмя вершинами (B, C, D, E). Если две из этих вершин соединены красным ребром, то сразу имеем красный треугольник, а если нет, то BCDE - полный синий граф из четырех вершин. Значит k < 4.
Аналогичным образом 8-k < R(3, 3) = 6.
Из этих двух неравенств имеем (k < 4) && (k > 2) => k = 3.
Так как наши рассуждения не зависят от выбора вершины, то можно утверждать, что из любой вершины выходит ровно три красных ребра, а значит общее число красных ребер в графе равно 3 * 9 / 2. Но это число не является целым, мы пришли к противоречию. Следовательно требуемой раскраски не существует и R(3, 4) = 9. Конец доказательства.

P.S. Данное доказательство пока не слишком сложное, но все же сложнее вычисления R(3, 3). Для больших параметров доказательства значительно усложняются. Дело в том, что не существует системного метода поиска чисел Рамсея (есть только грубые оценки), а с ростом параметров начинается очень обширное комбинаторное многообразие, не позволяющее найти решение даже компьютеру...

P.P.S. Практического применения чисел Рамсея нет, но в процессе их поиска было разработано масса полезного инструментария как в теории графов, так и в смежных областях.

 







Дата добавления: 2015-10-01; просмотров: 1244. Нарушение авторских прав; Мы поможем в написании вашей работы!




Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...


Кардиналистский и ординалистский подходы Кардиналистский (количественный подход) к анализу полезности основан на представлении о возможности измерения различных благ в условных единицах полезности...


Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...


Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...

Оценка качества Анализ документации. Имеющийся рецепт, паспорт письменного контроля и номер лекарственной формы соответствуют друг другу. Ингредиенты совместимы, расчеты сделаны верно, паспорт письменного контроля выписан верно. Правильность упаковки и оформления....

БИОХИМИЯ ТКАНЕЙ ЗУБА В составе зуба выделяют минерализованные и неминерализованные ткани...

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

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

ПРОФЕССИОНАЛЬНОЕ САМОВОСПИТАНИЕ И САМООБРАЗОВАНИЕ ПЕДАГОГА Воспитывать сегодня подрастающее поколение на со­временном уровне требований общества нельзя без по­стоянного обновления и обогащения своего профессио­нального педагогического потенциала...

Эффективность управления. Общие понятия о сущности и критериях эффективности. Эффективность управления – это экономическая категория, отражающая вклад управленческой деятельности в конечный результат работы организации...

Studopedia.info - Студопедия - 2014-2025 год . (0.01 сек.) русская версия | украинская версия