Дан произвольный 9-однородный гиперграф с 10^8 гиперрёбрами на 8*(10^6) вершинах.

1) Всегда ли подмножество вершин, такое, что имеет непустое пересечение с любым гиперребром, имеет мощность меньше, либо равную 1400000 ?

2) Всегда ли подмножество вершин, такое, что имеет непустое пересечение с любым гиперребром, имеет мощность меньше, либо равную 1700000 ?

Гиперребро графа - это произвольное подмножество вершин графа.

9-однородный - это такой граф, что мощность каждого гиперребра равна 9.

задан 28 Апр 13:43

изменен 28 Апр 14:54

10|600 символов нужно символов осталось
0

“подмножество вершин, такое, что имеет непустое пересечение с любым гиперребром” = “минимальное вершинное покрытие”?

По аналогии с Вашим предыдущим вопросом по теме: попытайтесь собрать граф из нескольких подграфов так, чтобы суммарно в них было точное количество (10^8) ребер, и не больше, чем заданное количество вершин. Можно набирать ребра, сначала строя полные подграфы на некотором количестве вершин. Почему полные? Считать вершинное покрытие легко, оно равно n-8. Например, попробуем полные графы на 20 вершинах. Тогда получится (8*10^6)/20 = 400000 подграфов. Суммарное вершинное покрытие будет равно 4800000, что много больше данных оценок, но есть проблема: число ребер суммарно C(20,9) * 400000 = 67184000000 - многовато. В общем, надо пробовать другие разбиения, так, чтобы число ребер в них было близко к требуемому. Скорее всего, разбиение только на такие подграфы, которые бы покрывали в точности указанное количество ребер найти не удастся, оно слишком “круглое”. Но это не беда, потому что “хвост”, не покрытый полными подграфами, можно разбить, например, на отдельные ребра (у которых вершинное покрытие, конечно, равно 1). Или построить “почти” полный граф из “хвоста”, тогда у него вершинное покрытие будет меньше чем n-8. Поскольку оценки даны очень грубые, то скорее всего, вершинное покрытие для “хвоста” не сильно изменит суммарное вершинное покрытие.

ссылка

отвечен 28 Апр 18:27

Можно попробовать и другую стратегию: выбрать разбиение, посчитать параметры, и затем удалить некоторое число графов, так чтобы получить нужное число ребер и суммарное вершинное покрытие, которое больше данных оценок. Нам ведь необязательно иметь все 8*10^6 вершин, главное, чтобы их было не больше. В примере с 20 вершинами это вряд ли получится, но с другим разбиением может и повезет.

(28 Апр 18:35) navacho

Можно поступить так? 1) Рассмотрим вершины как: {1,2,...,10}, {11,12,...,21},....,{8(10^6)-9,...,8(10^6}. Далее, таких десяток всего: 8(10^5). Следовательно ребер: С(10,9)8(10^5)=8(10^6). Это меньше, чем 10^8, так что остальные набираем совершенно произвольно, т.к. нам нужно доказать неравенство. Из каждой десятки, очевидно, нужно взять по 2 элемента, которые в совокупности будут минимальным вершинным покрытием для системы ребер, которая в количестве 8*(10^6). Ясно, что мощность минимального вершинного покрытия для ребер, которые в количестве 10^8 еще больше. Т.о. получаем 2 * 8 * (10^5)

(28 Апр 18:43) worker

2 * 8 * (10^5) = 1600000>1400000. т.е. ответ: нет не всегда

(28 Апр 18:46) worker

@falcao, @navacho как Вы считаете: такое рассуждение верно?

(28 Апр 19:00) worker

Да, думаю, так тоже можно. Но надо показать, как можно набрать 10^8 - 8*10^6 ребер, которых нет в первом множестве ребер. Конечно, это можно сделать, например, брать ребра на подмножествах большего размера.

(28 Апр 19:33) navacho

А как поступить со второй задачей?

(28 Апр 19:35) worker
1

Попробуйте разбиение с 11. Вроде опять все получается. Полных графов будет floor(8 * 10^6/11) = 727272, задействованных вершин 727272 * 11 = 7999992, 8 оставшихся вершин можно не рассматривать. Тогда вершинное покрытие будет 727272 * 3= 2181816, ребер 727272 * C(11,9) = 39999960. Осталось обосновать, что можно добрать оставшиеся ребра.

(28 Апр 20:06) navacho
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,122
×548
×55

задан
28 Апр 13:43

показан
132 раза

обновлен
28 Апр 20:07

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru