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