?

Log in

немного о графах (математическое) - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

немного о графах (математическое) [мар. 5, 2009|11:30 pm]
Anatoly Vorobey
(эта запись может быть интересна математикам и сочувствующим)

Вчера узнал красивый и одновремнно очень простой пример использования вероятностного метода в комбинаторике - настолько простой, что можно стоя на одной ноге рассказать, пожалуй.

Пусть G - граф; доминирующим называется такое подмножество вершин G, что любая вершина либо в нем, либо соседствует с кем-то, кто в нем. Например, в полном графе - где любые две вершины соединены - подмножество из любой одной вершины является доминирующим.

Интуитивно ясно, что в графе с очень высокой минимальной степенью d - из каждой вершины выходит не менее d ребер - должны существовать небольшие по размеру доминирующие множества - связей очень много, поэтому даже из небольшого множества будет можно добраться до всех за один шаг. Теорема: в графе из n вершин с минимальной степенью d есть доминирующее множество размером не больше n*(1+ln(d+1))/(d+1). При большом d это всего лишь малая часть n - например, при минимальной степени около 100 теорема говорит, что можно составить доминирующее множество из всего 5% вершин графа.

Доказательство. Построим случайное подмножество вершин Y следующим образом: каждая вершина попадает в Y с фиксированной вероятностью p (ее значение пока оставим открытым); выбор для каждой вершины независим от всех остальных. Y необязательно доминирующее множество, но если мы обозначим R(Y) все вершины, которые Y не доминирует, т.е. не находящиеся в Y и не связанные ребром с членами Y, то ясно, что объединение Y и R(Y) вместе - доминирующее множество. Предположим, мы доказали, что матожидание размера этого доминирующего множества меньше или равно X. Тогда хотя бы для одного возможного выбора членов Y размер доминирующего множества будет меньше или равен X (если бы во всех случаях был больше X, то и матожидание было бы больше); значит, мы доказали, что есть доминирующее множество размером не больше X. В этом и состоит - в данном случае - применение вероятностного метода.

Можно легко оценить матожидание случайной переменной "размер множества Y": E(|Y|). Ее значение - всего лишь количество исходов "попала в Y", каждый из которых имеет вероятность p, из n независимых экспериментов; матожидание поэтому E(|Y|) = n*p. Что касается R(Y), то каждая конкретная вершина x имеет вероятность (1-p)^(d(x)+1) попасть в R(Y), где d(x) - степень x: потому что для этого нужно, чтобы ни x, ни ее соседи не были выбраны в Y, а вероятность каждого такого непопадания равна 1-p. Значит, матожидание случайной переменной R(x) "x=1 если x попала в R(Y) и x=0 если нет" равно (1-p)^(d(x)+1) <= (1-p)^(d+1), ведь 1-p < 1 и d - минимальная степень среди всех вершин. Тогда (используя линейную аддитивность матожидания) матожидание размера R(Y) равно сумме R(x) по всем x в R(Y), что меньше или равно n * (1-p)^(d+1).

Матожидание размера доминирующего множества, состоящего из Y и R(Y), поэтому меньше или равно n*p + n*(1-p)^(d+1) = n*(p + (1-p)^(d+1)). Мы вольны выбрать p так, чтобы сделать выражение в скобках как можно меньшим; для крайних значений p=0,1 оно равно 1. Чтобы получить удобную формулу, воспользуемся неравенством 1-p <= e^(-p), верным всегда, и получим n(p + e^(-p(d+1))). Подставив сюда вероятность p = ln(d+1)/(d+1), мы получим во втором слагаемом e^(-ln(d+1)), т.е. 1/(d+1), и вместе с первым слагаемым получим, что матожидание размера доминирующего множества меньше или равно n(1+ln(d+1))/(d+1). Как уже было сказано выше, из этого прямо следует, что такое доминирующее множество, хотя бы одно, должно существовать, что и требовалось доказать.
СсылкаОтветить

Comments:
From: dmpogo
2009-03-05 10:25 pm
В сравнении с наивной оценкой ~ n/d результат кажется совсем не интересным с 'физической' точки зрения
(Ответить) (Thread)
[User Picture]From: avva
2009-03-05 10:31 pm
Дело в том, что предлагаемая этим результатом оценка n*ln(d)/d - лучшая, которую можно найти эффективным способом. Задача нахождения минимального множества не только сама по себе NP-полна, даже приближение к минимальному множеству до фактора ln(d) NP-трудно найти.
(Ответить) (Parent) (Thread)
From: dmpogo
2009-03-05 10:46 pm
Да я понимаю.

Просто когда результат - "лучший, который можно найти эффективным способом" для задачи в которой "даже приближение к минимальному множеству до фактора ln(d) NP-трудно найти" отличается всего лишь логарифмом от ответа который возникает в голове мгновенно - есть ощущение 'пшика'
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2009-03-05 10:52 pm
Погодите, но результат ~n/d существует только в специальных случаях, далеко не всегда, сколь бы он ни казался интутитивным и сколь бы не возникал в голове мгновенно.

(впрочем, я не спорю, что сам по себе результат не выглядит исключительным и вполне соглашается с интуицией. Мне он понравился просто как демонстрация метода)
(Ответить) (Parent) (Thread)
From: dmpogo
2009-03-05 11:04 pm
Мое картина была такое.
Возьмем небольшой компактный граф с М элементами - прообраз доминирующего множества. Пусть каждый узел будет соеденен с окружением большим 'd' числом связей - такой ежик с 'd' иголками из каждого узла.
со сколькими вершинами N такой ежик мовет быть соеденен за один шаг ? N ~ М*d Следовательно М ~ N/d

Ясно что при больших d, малых М/Н число вхолостую потраченых связей внутри М не значительно, поэтому бопьших поправок к оценке трудно ожидать.

(Ответить) (Parent) (Thread)
From: dmpogo
2009-03-05 11:07 pm
Кстати log, асимптотически, кажется фиктивным, поскольку оценка в пределе не дает правильного результата для d=N-1 (а без log слагаемого, было бы как раз правильно)
(Ответить) (Parent) (Thread)
[User Picture]From: mi_b
2009-03-05 10:32 pm
по-моему, это легко переделывается в невероятностный аргумент с подсчетом среднего размера доминирующего множества с выделенным подмножеством или что-то вроде
(Ответить) (Thread)
[User Picture]From: avva
2009-03-05 10:48 pm
Да, наверняка - но это свойство любого вероятностного аргумента на конечном множестве с фиксированными вероятностями, по понятным причинам :)

Вероятностные доказательства, непереводимые легко в чисто-комбинаторные, пользуются более сложными вероятностыми техниками, чем аддитивность матожидания или субаддитивность вероятности (из другого простого примера). Собственно я их и не знаю, хотя можно надеяться, что буду знать через какое-то время.

(Ответить) (Parent) (Thread)
[User Picture]From: mi_b
2009-03-05 11:05 pm
ну, просто аргументы с усреднением легче укладываются в систему и обобщаются - через теорию homogenous spaces in duality, например
(Ответить) (Parent) (Thread)
[User Picture]From: janatem
2009-03-06 09:35 am
Если действительно есть примеры, где вероятностное представление оказывается существенно проще комбинаторного, то как это объяснить?

Следует ли из этого, что понятия из ТВ имеют аномально высокий уровень воздействия на интуицию? Или же дело в том, что аппарат ТВ лучше проработан и занимает больше места в учебных программах?
(Ответить) (Parent) (Thread)
[User Picture]From: shaggy
2009-03-05 10:33 pm
(Ответить) (Thread)
[User Picture]From: avva
2009-03-05 10:42 pm
Забавно и неожиданно :)
(Ответить) (Parent) (Thread)
[User Picture]From: kapahel
2009-03-06 12:38 am

Меня называют графом, потому что я люблю графы
(Ответить) (Parent) (Thread)
[User Picture]From: ygam
2009-03-06 03:35 am
Связный граф - это не математика, а революция!
(Ответить) (Parent) (Thread)
From: ext_134706
2009-03-06 11:33 am
Ролик отлично гармонирует с юзерпикой :-)
(Ответить) (Parent) (Thread)
[User Picture]From: falcao
2009-03-05 11:12 pm

супер!

Очень красиво само по себе, и объяснено великолепно! Читается "на одном дыхании", ни разу не возникает ощущение чего-либо недосказанного.

Эх, если бы все в таком стиле писали математические статьи! :)
(Ответить) (Thread)
[User Picture]From: avva
2009-03-06 12:30 am

Re: супер!

Спасибо :)
(Ответить) (Parent) (Thread)
[User Picture]From: kapahel
2009-03-05 11:42 pm
"Все со всеми знакомы".
(Ответить) (Thread)
[User Picture]From: avva
2009-03-06 12:31 am
Ну или 'все со всеми переспали', соответственно.
(Ответить) (Parent) (Thread)
[User Picture]From: kapahel
2009-03-06 12:35 am
Не так давно разговор был (обсуждалось, что в некоторых социальных сетях есть графа про significant other, которую многие заполняют зачем-то, и было бы интересно проследить за динамикой на большом масштабе):
-- Назовем отношение половым, если оно рефлексивно и симметрично.
-- А зачем рефлексивность?
-- Ты что, мормон?
(Ответить) (Parent) (Thread)
From: illy_drinker
2009-03-06 01:25 am
в одной из статей Марка Ньюмана (вот в этой http://arxiv.org/abs/cond-mat/0303516, третья страница), классика в этой области приводится пример графа "переспали"
очень заметно наличие вершин со связями ко многим други вершинам
(Ответить) (Parent) (Thread)
[User Picture]From: ygam
2009-03-06 03:50 am
(Ответить) (Parent) (Thread)
[User Picture]From: _navi_
2009-03-06 09:18 am
I see two blue dots connected to each other in the upper right part of a big subgraph
(Ответить) (Parent) (Thread)
[User Picture]From: janatem
2009-03-06 09:20 am
Я нашел только одну пару Ж-Ж. Это странно: если исследовались только гетеро- отношения, то Ж-Ж -- ошибка, если же гомо- не отсеивались специально, то их подозрительно мало. ;)
(Ответить) (Parent) (Thread)
[User Picture]From: doktor_gradus
2009-03-06 03:23 pm
А я нашёл только одну пару М-М, и ни одной пары Ж-Ж.
(Ответить) (Parent) (Thread)
From: illy_drinker
2009-03-07 01:33 am
ЖЖ пара
верхний ряд
второй подграф справа
(Ответить) (Parent) (Thread)
[User Picture]From: janatem
2009-03-06 09:25 am
Представляю себе текст математической статьи: "Определение: назовем вершину типа F блядью, если...".
(Ответить) (Parent) (Thread)
[User Picture]From: utnapishti
2009-03-06 07:23 pm
Кстати, есть два одинаковых компонента (вида 4-path).
(Ответить) (Parent) (Thread)
From: illy_drinker
2009-03-05 11:56 pm
Это не из книги Нога Алона- Дж Спенсера?
(Ответить) (Thread)
[User Picture]From: avva
2009-03-06 12:26 am
очень может быть - я это услышал на лекции Ноги Алона.
(Ответить) (Parent) (Thread)
From: illy_drinker
2009-03-06 12:32 am
Его книга - совершенно потрясающее собрание таких изумительных доказательств
(видимо лекции тоже, но не всем так везет ((( )
(Ответить) (Parent) (Thread)
From: glukanat
2009-03-06 06:56 am
Еще один момент - насколько помню - эта оценка еще и по сути неулучшаема, то есть в среднем, для очень больших графов с числом вершин n, а ребер m доминирующее множество имеет порядок $n^2\ln n / m$ в предположении что m имеет рост выше $n^1+\epsi$, без этого предположения - есть оценка $n^2\ln\ln n n / m.$
(Ответить) (Thread)
From: (Anonymous)
2009-03-06 01:00 pm

Одно из приложений.

Кто имеет быстрый доступ к полной базе данных ЖЖ, может при помощи подобных методов анализировать распространение идеологий и, при наличии также подконтрольных СМИ, эффективно управлять этим процессом.
(Ответить) (Thread)
From: ionial
2009-04-26 09:56 am

language nazi comment

хорошее доказательство.
Одно замечание - по-русски, вроде бы, вершина А доминирует над вершиной Б, а не "А доминирует Б"...
(Ответить) (Thread)