Решение: Рассмотрим двудольный граф: одна его доля это все подмножества из k элементов из чисел от 1 до n, а вторая (k+1) элементные. icon

Решение: Рассмотрим двудольный граф: одна его доля это все подмножества из k элементов из чисел от 1 до n, а вторая (k+1) элементные.




НазваниеРешение: Рассмотрим двудольный граф: одна его доля это все подмножества из k элементов из чисел от 1 до n, а вторая (k+1) элементные.
Дата21.01.2013
Размер6.5 Kb.
ТипДокументы
источник

Комбинаторика-3. Из чисел от 1 до n составлены все неупорядоченные наборы по k различных чисел. Докажите, что в каждый набор можно добавить по одному числу (в разные наборы может добавляться одно и то же число) таким образом, что получатся различные неупорядоченные наборы из k+1 различных чисел.


Замечание: это верно только если 2k

Решение: Рассмотрим двудольный граф: одна его доля это все подмножества из k элементов из чисел от 1 до n, а вторая – (k+1) элементные. Две вершины соединены ребрами, если одно подмножество содержится в другом. Построенный граф, очевидно, является регулярным (степени вершин в одной доле совпадают), а значит, к нему можно применить лемму Холла (о свадьбах), откуда очевидно получается утверждение задачи надо из начальных подмножеств сделать те, с которыми они соединены ребрами в паросочетании из леммы Холла..



Похожие:

Решение: Рассмотрим двудольный граф: одна его доля это все подмножества из k элементов из чисел от 1 до n, а вторая (k+1) элементные. iconНапример, вводя в уравнении
Рассмотрим один из способов решения иррациональных алгебраических уравнений в области действительных чисел, считая в этой области...
Решение: Рассмотрим двудольный граф: одна его доля это все подмножества из k элементов из чисел от 1 до n, а вторая (k+1) элементные. icon«Анизотропное» пространство
Рассмотрим множество V, элементами которого служат упорядоченные наборы действительных чисел вида, где i = 1, n чисел в каждом наборе...
Решение: Рассмотрим двудольный граф: одна его доля это все подмножества из k элементов из чисел от 1 до n, а вторая (k+1) элементные. icon10 заповедей Slipknot не утеряй маски своей
Кори Тейлор: "Для нас это правило номер раз. Прямо скажем, непросто это делать день за днем, и, если потеряется хоть одна маска,...
Решение: Рассмотрим двудольный граф: одна его доля это все подмножества из k элементов из чисел от 1 до n, а вторая (k+1) элементные. iconО человеке, о его делении на физического человека и человека духовного, о его происхождении
Ими, благодаря которым он, несмотря на существующие между ним и животными различия, поступает все же согласно универсальным правилам,...
Решение: Рассмотрим двудольный граф: одна его доля это все подмножества из k элементов из чисел от 1 до n, а вторая (k+1) элементные. iconЗахотелось ей осмотреть весь дворец, и пошла она осматривать все его палаты высокие, и ходила она немало времени, на все диковинки любуючись
И была одна стена вся зеркальная, а другая стена золочёная, а третья стена вся серебряная, а четвёртая стена из кости слоновой и...
Решение: Рассмотрим двудольный граф: одна его доля это все подмножества из k элементов из чисел от 1 до n, а вторая (k+1) элементные. iconКонспект урока Тема: Сложение и вычитание трёхзначных чисел (закрепление зун)
Сегодня на уроке математики мы с вами попадём страну мультфильмов, встретимся с её героями. Для того, чтобы наше путешествие было...
Решение: Рассмотрим двудольный граф: одна его доля это все подмножества из k элементов из чисел от 1 до n, а вторая (k+1) элементные. iconРоль отца в воспитании ребенка
Воспитание процесс многогранный и всеобъемлющий. Всё, что окружает ребёнка, люди, вещи, события всё накладывает отпечаток на его...
Решение: Рассмотрим двудольный граф: одна его доля это все подмножества из k элементов из чисел от 1 до n, а вторая (k+1) элементные. iconРабота с родителями Консультация для родителей Отец как воспитатель
Воспитание процесс многогранный и всеобъемлющий. Всё, что окружает ребёнка, люди, вещи, события всё накладывает отпечаток на его...
Решение: Рассмотрим двудольный граф: одна его доля это все подмножества из k элементов из чисел от 1 до n, а вторая (k+1) элементные. iconСписок литературы для родителей будущих первоклассников закон «Об образовании» Российской Федерации. 1992 г. Все о младшем школьнике. Под редакцией Н. Ф. Виноградовой. Москва, «Вентана-Граф», 2004 г
Все о младшем школьнике. Под редакцией Н. Ф. Виноградовой. Москва, «Вентана-Граф», 2004 г
Решение: Рассмотрим двудольный граф: одна его доля это все подмножества из k элементов из чисел от 1 до n, а вторая (k+1) элементные. iconМетафора – это слово в переносном смысле. Чаще всего выражается глаголами, сущ. Например
...
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©lib3.podelise.ru 2000-2013
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Лекции
Доклады
Справочники
Сценарии
Рефераты
Курсовые работы
Программы
Методички
Документы

опубликовать

Документы