WWW.LIB.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Электронные материалы
 

«Далее заметим, что для графа (, 3, 1) из примера 1 минимальное число общих конкретному примеру 1, продемонстрировав, что бывают графы, к которым неприменим ...»

ЛЕКЦИЯ 2

ТУРНИРЫ.

ПОСЛЕДОВАТЕЛЬНОСТИ И

ГРАФЫ ДЕ БРЁЙНА. ТЕОРЕМА

ТУРАНА

В прошлый раз лекция закончилась на том, что мы захотели применить теорему 4 к

Далее заметим, что для графа (, 3, 1) из примера 1 минимальное число общих

конкретному примеру 1, продемонстрировав, что бывают графы, к которым неприменим

соседей у пар вершин этого графа не превосходит ((, 3, 1)).

критерий Дирака, а теорема 4 хорошо применяется.

Тогда рассмотрим, какие бывают варианты таких векторов.

1. Множества единичных координат этих двух векторов вообще не пересекаются:

соседей будет 9( 6).

У этих двух векторов общий сосед устроен таким образом: по единице на каждую тройку единиц из этих векторов и одна единица вне троек. Тогда число общих

2. Случай с единичным пересечением:

и на остальных 5 позициях. Число таких вариантов:

Есть два варианта устройства вектора общего соседа: с единицей на общей позиции u5 + 4( 5).

зумевая достаточно большим числом).

Значит, минимальное количество общих соседей уже заведомо в случае 1 (подраКонспект не проходил проф. редактуру, создан студентами и, ! 2 возможно, содержит смысловые ошибки.

Следите за обновлениями на lectoriy.mipt.ru.

3. Пересечение по двум элементам:

Снова имеем два случая устройства общего ребра. В одном из них одна единица будет на позиции одного из элементов пересечения, а две другие будут на позициях 2 u5 9( 6).



общих нулей. В таком случае число таких векторов будет:

((, 3, 1)) 9( 6), 0,

Значит:

((, 3, 1)) 9.

Теперь попробуем оценить снизу ((, 3, 1)). Из того, что нас интересует независимое множество вершин в таком графе, следует, что тройки либо пересекаются по двум Задача Как много бывает троек на элементов, если мы запрещаем им пересекаться элементам, либо по нулю.

С этим вопросом связано упражнение:

ровно по одному общему элементу?

Вернемся к оценке числа независимости нашего графа (, 3, 1). Из рассуждения о Это упражнение мы разберем, когда будем рассматривать линейно-алгебраический метод в комбинаторике, пока же предлагается подумать над ним самостоятельно.

размера 2. Например, для этого нужно взять все векторы, у которых две первые пересечении троек видно, что в таком графе можно построить независимое множество координаты есть единицы, тогда их попарные скалярные произведения равны двум.

Но Теорема 5 ((, 3, 1)).

–  –  –

2 0(2).

независимы, то их не больше, чем, что и требовалось доказать.

Проделаем аналогичную операцию для всех векторов, получим, что все константы равны нулю. Значит, эти векторы — линейно независимы. А если n-мерные векторы линейно Итак, мы получили, что ((, 3, 1)), а ((, 3, 1)) 9. Значит, по теореме (4) граф — гамильтонов.

фа ((, 3, 1)). Например, возьмем отрезок от 1 до, разобьем его на столько четверок, Существуют и другие способы оценить размерность независимого множества для грана сколько возможно, как показано на рис. 2.1.

–  –  –

Каждый получившийся отрезок заполним тройками. В одном отрезке помещается висимое множество. Если остаток от деления на 4 равен 3, то в последнем отрезке четыре тройки. Они пересекаются между собой всегда по два элемента внутри одного отрезка, а тройки из разных отрезков между собой не пересекаются. Значит, это неза

–  –  –

1(4) 1;

2(4), 3(4) 2.

(2.2)

Правильность оценки можно доказать по индукции, что остается в качестве упражнения:

–  –  –

Введем понятие турнир. Возьмем полный граф на вершинах, обозначим его u, затем

1. Турниры на каждое из ребер этого графа повесим ровно одну стрелочку. Получим определение турнира:

–  –  –

Скажем, что в таком графе тот, от кого идет стрелочка, является победителем данного матча.

Применительно к турниру будем понимать цепь с учетом правильности прохода по графу в зависимости от направления стрелок.

Пример турнира приведен на рис. 2.2.

В истории комбинаторики принято считать, что со следующей теоремы был принят Теорема 6 (1947, Селе) Существует турнир на вершинах, в котором не меньше, вероятностный метод в комбинаторике:

–  –  –

Док-во: Рассмотрим случайный турнир, то есть ориентируем каждое ребро независимо от остальных с одной и той же вероятностью. Возьмем случайную величину как

–  –  –

где 1 2 … u — слова, состоящие из последовательности 1, 2, …, u. Понятно, что таких слов 2u. Пусть эта последовательность устроена следующим образом:

–  –  –

Есть два способа построить интересующее нас слово:

1. Правило «0 лучше 1». Выставляем единиц, далее ставим 0 столько времени, сколько возможно, то есть нулей, так как поставь мы + 1 нулей, то возникло бы повторение — две последовательности из нулей. Тогда далее ставим 1, потом снова 0 (помним, 0 лучше 1), пока это возможно, и так далее.

–  –  –

2. Граф де Брёйна. Разберем случай = 3, далее покажем, как обобщить этот способ для произвольного. Выпишем все последовательности длины 2 из нулей и единиц:

–  –  –

001, 010, 100, 011, 101, 110, 111.

Слова из двух букв расположим в вершинах графа, как на рис. 2.3.

–  –  –

Двигаясь по списку трехбуквенных слов, рисуем ребра графа с указанием направления обхода, руководствуясь следующим правилом: трехбуквенное слово, к примеру, 010 означает выход ребра из вершины 01 и окончание в вершине 10 с привязанным соответствующим направлением (стрелочкой).

Очевидно, что у такого графа исходящая степень каждой вершины равна её входящей степени. Поэтому мы можем применить критерий эйлеровости, следовательно, в графе де Брёйна есть эйлеров цикл.

Построим для этого графа конкретный эйлеров цикл, двигаясь, как на рис. 2.3.

Например, выходим из вершины 000, идем в неё же, значит, записываем «000».

Далее идем в вершину 01, следовательно, добавляем к строке 1, получим «0001».

Затем идем в вершину 10, добавляем к строке 0, получим «00010» и так далее, следуя стрелкам на рис. 2.4. В итоге получим слово «0001011100».

Таким образом, найдем все слова для случая = 3.

Итак, по каждому ребру прошли ровно один раз, при этом прошли по всем ребрам.

–  –  –

3. Теорема Турана Пусть есть граф = (, ), () = — его число независимости. Обозначим за = | | количество его вершин. — это максимальное по мощности независимое множество вершин (см. рис. 2.4), следовательно:

|| =.

–  –  –

Она соединена хотя бы одним ребром с, так как это множество — максимально. Значит:

{, }.

Таким образом, мы набрали как минимум таких ребер. u u — граф, индуцированный на множество вершин.

–  –  –

жащих множеству. Рассмотрим все такие ребра. Число независимости такого графа:

Будем рассматривать часть графа, состоящую только из ребер, целиком принадле

–  –  –

Таким образом, мы нашли новых ребер не меньше, чем 2. Продолжая действовать

Теорема 8 (Турана) Если в вершин и () =, то:

аналогично, приходим к теореме:

Похожие работы:

«1100117 © Swiss Diamond ПОСУДА С АЛМАЗНЫМ АНТИПРИГАРНЫМ ПОКРЫТИЕМ золотая медаль а международной ставке изобретений Новое с алм Ш со "3 IQ. Амир Алон, директор компании Swiss Diamond International "В середине 80-х было крайне интересно наблюдать за развитием титаново­ го керамического антипригарного покрытия, покорившего мир благодаря сво...»

«Курсовая работа (Лабораторная работа №5). Моделирование нечетких систем Для заданного объекта управления (ОУ) предложить и реализовать в пакете MATLAB нечеткую модель управления, последовательно наращивая число доступных для наблюдения входных переменных и их значений. Последовательность выполнения задания включает в себя:1. Задание для каждого входа и...»

«С У ТР А С Е Р ДЦ А. Л Е К ЦИ Я 2 Я очень рад вновь видеть вас. Некоторые из вас приехали издалека. Вы должны понимать, что чем больше усилий вы прикладываете, чтобы получить учение, чем больше трудностей вы преодолеваете для этого, тем более эффективным и полезным будет учени...»

«Благодарим за то, что вы выбрали наш плеер. Прежде чем начать эксплуатацию устройства, внимательно прочтите данное руководство, чтобы воспользоваться всеми возможностями плеера и продлить срок его службы. Сохр...»

«DDS: прямой цифровой синтез частоты Еще несколько лет назад прямые цифровые синтезаторы частоты (Direct Digital Synthesizers или DDS) были диковинкой с очень ограниченной областью применения. Их широкое использование сдерживалось сложностью реализации, а также недостаточно широким диапазоном рабочих частот. Несмотря на то, что в настоящее вре...»

«1. Цели освоения модуля (дисциплины) Учебная дисциплина "Лабораторные методы изучения минерального сырья" принадлежит к числу специальных геологических дисциплин и тесно взаимосвязана с курсами "Кристаллография и минералогия", "Пет...»

«УТВЕРЖДАЮ Директор НОЧУ ДПО "ЭКСПЕРТ" Конова Татьяна Геннадьевна _ "12" января 2017 г. Положение о VIII Олимпиаде по английскому, немецкому и польскому языкам для учащихся лицеев, гимназий, общеобразовательных школ и частных образовательных...»

«Феномен Башкортостана: от трагической демографии к закономерной реконфигурации численности1 Ильдар Габдрафиков Р еспублика Башкортостан занимает первое место в Приволжском федеральном округе и седьмое в Российской Федерации по численности населения. Всероссийская перепись 2002 года насчитала 4104,3 тыс. жителей, в том...»









 
2017 www.lib.knigi-x.ru - «Бесплатная электронная библиотека - электронные материалы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.