немного о графах (математическое)
Mar. 5th, 2009 11:30 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
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). Как уже было сказано выше, из этого прямо следует, что такое доминирующее множество, хотя бы одно, должно существовать, что и требовалось доказать.
Вчера узнал красивый и одновремнно очень простой пример использования вероятностного метода в комбинаторике - настолько простой, что можно стоя на одной ноге рассказать, пожалуй.
Пусть 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). Как уже было сказано выше, из этого прямо следует, что такое доминирующее множество, хотя бы одно, должно существовать, что и требовалось доказать.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2009-03-05 10:25 pm (UTC)no subject
Date: 2009-03-05 10:31 pm (UTC)no subject
Date: 2009-03-05 10:46 pm (UTC)Просто когда результат - "лучший, который можно найти эффективным способом" для задачи в которой "даже приближение к минимальному множеству до фактора ln(d) NP-трудно найти" отличается всего лишь логарифмом от ответа который возникает в голове мгновенно - есть ощущение 'пшика'
no subject
Date: 2009-03-05 10:52 pm (UTC)(впрочем, я не спорю, что сам по себе результат не выглядит исключительным и вполне соглашается с интуицией. Мне он понравился просто как демонстрация метода)
no subject
Date: 2009-03-05 11:04 pm (UTC)Возьмем небольшой компактный граф с М элементами - прообраз доминирующего множества. Пусть каждый узел будет соеденен с окружением большим 'd' числом связей - такой ежик с 'd' иголками из каждого узла.
со сколькими вершинами N такой ежик мовет быть соеденен за один шаг ? N ~ М*d Следовательно М ~ N/d
Ясно что при больших d, малых М/Н число вхолостую потраченых связей внутри М не значительно, поэтому бопьших поправок к оценке трудно ожидать.
no subject
Date: 2009-03-05 11:07 pm (UTC)no subject
Date: 2009-03-05 10:32 pm (UTC)no subject
Date: 2009-03-05 10:48 pm (UTC)Вероятностные доказательства, непереводимые легко в чисто-комбинаторные, пользуются более сложными вероятностыми техниками, чем аддитивность матожидания или субаддитивность вероятности (из другого простого примера). Собственно я их и не знаю, хотя можно надеяться, что буду знать через какое-то время.
no subject
Date: 2009-03-05 11:05 pm (UTC)no subject
Date: 2009-03-06 09:35 am (UTC)Следует ли из этого, что понятия из ТВ имеют аномально высокий уровень воздействия на интуицию? Или же дело в том, что аппарат ТВ лучше проработан и занимает больше места в учебных программах?
no subject
Date: 2009-03-05 10:33 pm (UTC)no subject
Date: 2009-03-05 10:42 pm (UTC)no subject
no subject
Date: 2009-03-06 03:35 am (UTC)no subject
Date: 2009-03-06 11:33 am (UTC)супер!
Date: 2009-03-05 11:12 pm (UTC)Эх, если бы все в таком стиле писали математические статьи! :)
Re: супер!
Date: 2009-03-06 12:30 am (UTC)no subject
Date: 2009-03-05 11:42 pm (UTC)no subject
Date: 2009-03-06 12:31 am (UTC)no subject
Date: 2009-03-06 12:35 am (UTC)-- Назовем отношение половым, если оно рефлексивно и симметрично.
-- А зачем рефлексивность?
-- Ты что, мормон?
no subject
Date: 2009-03-06 01:25 am (UTC)очень заметно наличие вершин со связями ко многим други вершинам
no subject
Date: 2009-03-06 03:50 am (UTC)no subject
Date: 2009-03-06 09:18 am (UTC)no subject
Date: 2009-03-06 09:20 am (UTC)no subject
Date: 2009-03-06 03:23 pm (UTC)no subject
Date: 2009-03-07 01:33 am (UTC)верхний ряд
второй подграф справа
no subject
Date: 2009-03-06 09:25 am (UTC)no subject
Date: 2009-03-06 07:23 pm (UTC)no subject
Date: 2009-03-05 11:56 pm (UTC)no subject
Date: 2009-03-06 12:26 am (UTC)no subject
Date: 2009-03-06 12:32 am (UTC)(видимо лекции тоже, но не всем так везет ((( )
no subject
Date: 2009-03-06 06:56 am (UTC)Одно из приложений.
Date: 2009-03-06 01:00 pm (UTC)language nazi comment
Date: 2009-04-26 09:56 am (UTC)Одно замечание - по-русски, вроде бы, вершина А доминирует над вершиной Б, а не "А доминирует Б"...
Обзор давнишней гамы
Date: 2011-05-29 09:58 pm (UTC)Добрый день! пользователи avva.livejournal.com
Date: 2011-06-29 09:18 pm (UTC)Нашёл на [url=http://titati.ru/источник[/url]
Здравствуйте юзеры avva.livejournal.com
Date: 2011-07-06 12:14 am (UTC)[url=http://domashnee.org/analnyy-seks/]анальный секс[/url]
куплю квартиру с отделкой дизайн и отделка квартир
Date: 2011-07-12 01:44 am (UTC)Однако наша фирма является хорошим исключением из этого неприятного правила. Мы вот уже несколько лет занимается отделкой офисов, комнат, домов и еще ни разу нам не поступало от наших клиентов ни неприятных отзывов, ни каких-либо жалоб. [url=http://remroom.ru]ремонт квартир щелково[/url] Богатый опыт наших специалистов, а также высокий профессионализм всех без исключения наших сотрудников, поможет сделать хорошо, качественно и – главное - доступно как косметический, так и капитальный ремонт. [url=http://remroom.ru]ремонт квартир область[/url] Современное оборудование, новые технологии планировки и дизайна, а также индивидуальный подход к каждому клиенту и гибкая система скидок сделали нашу компанию самой успешной на сегодня организацией, оказывающей услуги реставрации и отделке офисов, комнат или загородных домов. [url=http://remroom.ru]ищу ремонт квартир[/url]
Привет юзеры avva.livejournal.com
Date: 2011-07-15 06:11 am (UTC)Найдено [url=http://videosuka.com]здесь[/url]
Давайте находить фразы коллективно
Date: 2011-07-29 01:07 am (UTC)Цитата:
And though you're still with me
I?ve been alone all along
[url=http://apocalyptotuesday.com/profile.php?mode=viewprofile&u=616939]тут[/url]
Собираем цитаты сообща
Date: 2011-08-12 10:50 pm (UTC)Я не была у нее с тех пор, как умер ее бедный муж. Никогда не видела, чтобы женщина так изменялась. Она выглядит лет на двадцать моложе.
заберите инфу где-то тут www.OGLI.ORG http://ogli.org/2011/06/07/gei-proboyut-chleny-na-piknike.html
Выкладываем де мотиваторы дня
Date: 2011-08-14 04:01 pm (UTC)_________________
В столовой. Андрей читает газету и находит статью про пропавшую судью.
Максим:"Ну что там, гороскоп на неделю плохой?"
Выкладывайте демотиваторы дня
Date: 2011-08-17 10:33 am (UTC)_________________
Все русские сказки заканчиваются свадьбами и словами: «Они жили счастливо и умерли в один день». Но сейчас в один день не умирают. Мужчины живут на 12 лет меньше, чем женщины. засунули в очко литровую банку
products
Date: 2012-02-14 02:41 am (UTC)