Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

немного о графах (математическое)

(эта запись может быть интересна математикам и сочувствующим)

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

Пусть 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). Как уже было сказано выше, из этого прямо следует, что такое доминирующее множество, хотя бы одно, должно существовать, что и требовалось доказать.
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 34 comments