Полный граф с рёбрами 3 цветов
Полный граф с рёбрами 3 цветов
Задача с регаты 2021. Не удалось решить.
Есть полный граф с 2000 вершинами. Рёбра раскрашены каждое в один из трёх цветов.
Найти максимальный , такой что для любой раскраски всегда можно выбрать вершин, так чтобы все рёбра между этими вершинами были одного цвета.
Какие идеи?
Есть полный граф с 2000 вершинами. Рёбра раскрашены каждое в один из трёх цветов.
Найти максимальный , такой что для любой раскраски всегда можно выбрать вершин, так чтобы все рёбра между этими вершинами были одного цвета.
Какие идеи?
Полный граф с рёбрами 3 цветов
Обозначим N(k,l,m) число вершин, для которых верно,что либо будет полный подграф из k с первым цветом,либо полный из l вершин со вторым цветом, либо полный из m третьего цвета. Рекурсия по уменьшению суммы k+l+m: Берем одну вершину . Из остальных N(k,l,m)-1 найдется либо N1 которые с ним 1-го цвета, либо N2, которые с ним 2-го цвета, либо N3, которые с ним 3-го цвета. Неравенства:
[math]
[math]
[math]
Чтобы было верно, что найдется, надо [math] Вот и обсчитывать весь такой "тетраэдр Паскаля",получим точный ответ
[math]
[math]
[math]
Чтобы было верно, что найдется, надо [math] Вот и обсчитывать весь такой "тетраэдр Паскаля",получим точный ответ
Полный граф с рёбрами 3 цветов
Да блин исходная задача-то другая. Из любой в любую добраться,хоть бы с пересадками. Неправильно прочитано мной,и не только мной. Давайте решим и эту (на теорию Рамсея) и исходнуюzykov писал(а):Задача с регаты 2021. Не удалось решить.
Есть полный граф с 2000 вершинами. Рёбра раскрашены каждое в один из трёх цветов.
Найти максимальный , такой что для любой раскраски всегда можно выбрать вершин, так чтобы все рёбра между этими вершинами были одного цвета.
Какие идеи?
Полный граф с рёбрами 3 цветов
Их условие:
Их ответ: 1000
В стране 2000 городов, любые два соединены самолётом, поездом или пароходом. Для какого наибольшего k гарантированно можно выбрать k городов и один из видов транспорта так, чтобы из любого из этих k городов можно было этим видом транспорта добраться до любого другого?
Их ответ: 1000
Последний раз редактировалось zykov 22 май 2021, 17:50, всего редактировалось 1 раз.
Полный граф с рёбрами 3 цветов
Вообще, честно говоря - жестко, за 2 часа 25 подобных задач...
Тут над каждой надо изрядно подумать (может кроме некоторых по 100).
Вот все задачи:
Тут над каждой надо изрядно подумать (может кроме некоторых по 100).
Вот все задачи:
Полный граф с рёбрами 3 цветов
zykov писал(а):Source of the post чтобы из любого из этих k городов можно было этим видом транспорта добраться до любого другого?
Я понимал так, что для каждого города есть рейс в другой город из этих k.
Но можно понять, что можно добратся с несколькими пересадками.
Ещё можно тогда понять, что добратся вообще до любого из 2000 городов, но этот вариант отпадает как тривиальный (может быть 3 города, так что из каждого только один вид транспорта и для этих 3 городов все 3 разных вида).
Полный граф с рёбрами 3 цветов
Да.
В первой формулировке это чистая теорема Рамсея.
Нужно найти максимальный , такой что .
Но никто не знает значений даже для маленьких , кроме ну совсем маленьких (0, 1, может 2).
(Найти перебором их можно, но это нереально долго.)
Видимо имелась ввиду вторая формулировка - минимум от максимума размеров связных графов по трём цветам и по всем раскраскам.
В первой формулировке это чистая теорема Рамсея.
Нужно найти максимальный , такой что .
Но никто не знает значений даже для маленьких , кроме ну совсем маленьких (0, 1, может 2).
(Найти перебором их можно, но это нереально долго.)
There are (up to symmetries) only two non-trivial multicolour Ramsey numbers for which the exact value is known, namely R(3, 3, 3) = 17 and R(3, 3, 4) = 30.
Видимо имелась ввиду вторая формулировка - минимум от максимума размеров связных графов по трём цветам и по всем раскраскам.
Полный граф с рёбрами 3 цветов
zykov писал(а):Есть полный граф с 2000 вершинами. Рёбра раскрашены каждое в один из трёх цветов.
Найти максимальный , такой что для любой раскраски всегда можно выбрать вершин, так чтобы все рёбра между этими вершинами были одного цвета.
Код: Выбрать все
(k=2) l m N
2 3 3 6
2 3 4 10
2 4 4 20
2 4 5 35
2 5 5 70
2 3 5 15
k l m N
3 3 3 17
3 3 4 36
3 4 4 91
4 4 4 272
3 3 5 65
3 4 5 190
4 4 5 651
3 5 5 449
4 5 5 1750
5 5 5 5251
Наоборот в теории Рамсея белых пятен нет,обращайтесь)). Обозначения введены мной выше. Еще одно: N(l,m)=N(2,l,m) двухместная функция
Конечно везде полная симметрия по аргументам.
[math] -отсюда мой первый блок вычислений.
Второй блок вычислений приводит по формуле [math]
(эта формула необходима и достаточна,так как выдает и способ построения контрпримеров.И как видите N(3,3,4)=36 а не 30)
к значениям N(4,4,4)=272, но N(5,5,5)=5251, почему я и защищал интуитивно 4, но также вероятным считал 5
Полный граф с рёбрами 3 цветов
Ian писал(а):Наоборот в теории Рамсея белых пятен нет,обращайтесь)).
....
[math]
(эта формула необходима и достаточна,так как выдает и способ построения контрпримеров.И как видите N(3,3,4)=36 а не 30)
...
Статья в вики https://ru.wikipedia.org/wiki/Теорема_Рамсея обсуждалась на старом E-S лет 10 назад, тогда много заинтересованных людей как-то пришли к выводу, что в формуле равенство , по крайней мере для двухместной N(l,m) и значит белых пятен нет...Я это запомнил и базировался. Надо еще проверять, конечно.
Так или иначе, то что в задаче Рамсея N(4,4,4) не больше 272 это точно, ну и легкие неравенства N(5,5,5)>2*N(4,5,5)>4*N(4,4,5)>8*N(4,4,4) ну и какое должно быть точное значение N(4,4,4) чтобы там получалось не больше 2000. 249- маловато
-
- Сообщений: 620
- Зарегистрирован: 29 дек 2015, 13:17
Полный граф с рёбрами 3 цветов
Поиск по старому форуму (раздел Математика) по ключевому слову "рамсея" выдает только две темы:
Определенный интеграл нашел
Многоугольник
Определенный интеграл нашел
Многоугольник
Полный граф с рёбрами 3 цветов
Ian писал(а):Source of the post Наоборот в теории Рамсея белых пятен нет
Не знаю, про какие "белые пятна" говорите.
Факт, что точно посчитать например нереально долго.
Согласен, что скорее всего можно малой кровью получить грубые оценки сверху и снизу.
И этого может быть достаточно, если одна оценка сверху не более 2000, а следующая оценка снизу больше 2000.
А что собственно по их задаче, где ответ 1000, где речь про размер связных графов?
Полный граф с рёбрами 3 цветов
Некорректно сработал поиск. одна тема там не по делу. И главное была еще личная переписка почти с каждым, только важные позитивные результаты из нее потом выносились на всеобщее обозрение. С одной стороны, вроде бы убедились, что рекурсия дает не оценку а критерий. С другой стороны - и в этой теории и в комбинаторике вообще столько правдоподобных но неверных рассуждений проскакивает. И то что не вынесли в общую тему значит все-таки сомневались.peregoudov писал(а):Поиск по старому форуму (раздел Математика) по ключевому слову "рамсея" выдает только две темы:
Определенный интеграл нашел
Многоугольник
Полный граф с рёбрами 3 цветов
Есть пример где все связные компоненты всех цветов не более 1000. Разобьаем вершины на 4 группы по 500, A c B, С с D только одним цветом, A с С, B с D только другим, А с D, В с С третьим. Внутри групп неважно.
-
- Сообщений: 620
- Зарегистрирован: 29 дек 2015, 13:17
Полный граф с рёбрами 3 цветов
Ну, вашу личную переписку я по понятным причинам скачать не смог (только свою личную). Так что всего того великолепия, о котором вы пишете, ссылаясь на старый форум, к сожалению, не сохранилось... Впрочем, если вы уговорите Соула отдать базу данных...Ian писал(а):Source of the post И главное была еще личная переписка почти с каждым
Полный граф с рёбрами 3 цветов
Ian писал(а):Есть пример где все связные компоненты всех цветов не более 1000. Разобьаем вершины на 4 группы по 500, A c B, С с D только одним цветом, A с С, B с D только другим, А с D, В с С третьим. Внутри групп неважно.
Продолжение.Предположим, любая связная компонента любого цвета менее 1000. Тогда для каждого цвета компонент как минимум три . Каждой вершине присвоим тройку (i,j,k)- номера компонент, которым она принадлежит. Могут быть вершины с одинаковыми тройками. Но у любых двух вершин не могут быть полностью различные тройки,хотя бы одним цветом они соединены. Рассмотрим клетки [math], не менее 3х3 клеток.Каждая вершина в одной из клеток, и клетки с несовпадающими и строкой, и столбцом -имеют одинаковое k .Тогда все клетки имеют одинаковое k, или этому мешает большое количество пустых клеток (тут нестрого)
В общем рассуждения приводят к оптимальной таблице (i,j) 2х2, а k одинаково для клеток одной диагонали, в клетках по 500 вершин
Или ее можно представить как трехмерную таблицу 2х2х2, в которой непустые клетки строго в шахматном порядке
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 2 гостей