?

Log in

No account? Create an account
немного о графах (математическое) - Поклонник деепричастий [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) (Развернуть)
[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: shaggy
2009-03-05 10:33 pm
(Ответить) (Thread)
[User Picture]From: avva
2009-03-05 10:42 pm
Забавно и неожиданно :)
(Ответить) (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) (Развернуть)
From: illy_drinker
2009-03-05 11:56 pm
Это не из книги Нога Алона- Дж Спенсера?
(Ответить) (Thread)
[User Picture]From: avva
2009-03-06 12:26 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)