2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Вероятность выбора независимого множества вершин графа
Сообщение21.11.2017, 10:20 


21/11/17

25
Здравствуйте!

Вот такая задача.

Из графа размером $n$ вершин и $m$ рёбер наудачу выбрали $k$ вершин. С какой вероятностью никакие две выбранных вершины не соединены ребром?

Попробуем решить так

$p=1-\frac{m\cdot\binom{n-2}{k-2} - \binom{m}{2}\cdot\binom{n-3}{k-3} + \binom{m}{3}\cdot\binom{n-4}{k-4} - ...}{\binom{n}{k}}$

В числителе что-то вроде формулы включения-исключения. Складываем все случаи когда 2 вершины соединены, вычитаем когда 3 вершины соединены, и т.д.
Но формула неправильная, т.к 2-е слагаемое (когда выбрали 2 ребра) может исключить и 4 вершины, 3-е слагаемое (когда выбрали 3 ребра) - от 3 до 6 вершин. Итого, вообще кажется, что исходных $(n,m,k)$ данных недостаточно, решение зависит от конкретного графа.
Нельзя ли тем не менее получить какую-то оценку, исходя только из $(n,m,k)$?

 Профиль  
                  
 
 Posted automatically
Сообщение21.11.2017, 11:07 
Заслуженный участник


09/05/12
25179
 i  Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

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

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

 Профиль  
                  
 
 Posted automatically
Сообщение21.11.2017, 14:47 
Заслуженный участник


09/05/12
25179
 i  Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: B@R5uk


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group