Какие нерешенные задачи есть? я спомощью компьютерного моделирования решу любую

Answer 1

Ну, рассмотрим такую задачу. Пусть G — граф на 2024 вершинах. Соединим вершины i и j ребром в том случае, если i-ая и j-ая цифры в десятичной записи числа пи взаимно просты. Если эти цифры имеют общий делитель (отличный от 1) , то ребро проводить не будем. Про этот граф можно задать четыре забавных вопроса:

Назовем кликой подграф графа G, такой что в нем все вершины попарно соединены ребрами. Найдите максимальную (по числу вершин) клику в описанном графе

Назовем полной раскраской в m цветов такую раскраску вершин графа G, что для каждой пары цветов в графе найдется ребро, вершины которого покрашены в эти цвета. Каково максимальное число цветов в полной раскраске нашего графа G?

Назовем независимым множеством такое множество вершин нашего графа, что никакие две из них не соединены ребром. Каков размер максимального по числу вершин независимого множества в нашем графе G?

Пусть в нашем графе получилось k компонент связности. Запустим в каждой из них по почтальону и попросим каждого почтальона пройтись по всем ребрам в своей компоненте связности, причем так, чтобы количество ребер, по которым пришлось пройти больше одного раза, было минимально. Сколько суммарно раз почтальоны пройдут по ребрам?