Докажите что дерево это двудольный граф

Дерево как двудольный граф: доказательство

Дерево двудольный граф – это граф, особая структура, которая состоит из двух долей, между которыми нет ребер. Такой граф является основой многих математических моделей, которые применяются в различных областях науки и техники. В этой статье мы рассмотрим основные свойства и примеры деревьев двудольных графов, а также докажем, что любой граф является деревом двудольным графом, если и только если в нем нет нечётных циклов.

Доказательство этого факта основывается на свойствах двудольных графов и широко применяется в теории графов. Важно отметить, что каждый граф можно представить в виде дерева двудольного графа, раскрасив его вершины в два цвета – один для каждой доли. Это позволяет эффективно решать различные задачи, связанные с графами, например, поиск максимального паросочетания или определение гамильтонова цикла.

Примеры деревьев двудольных графов можно найти в различных областях – от биологии до экономики. Например, в биологических сетях деревья двудольные графы применяются для моделирования взаимодействий между организмами или генами. В экономике они могут использоваться для анализа взаимодействий между различными субъектами или компаниями.

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

Дерево двудольный граф

В дереве двудольного графа нет циклов, то есть не существует пути, который вернется в исходную вершину. Это свойство делает дерево двудольный граф особенно полезным для моделирования различных практических задач.

Дерево двудольного графа имеет несколько свойств:

1. Количество вершин в первой доле равно количеству вершин во второй доле.
2. Максимальное количество ребер, которое может быть в дереве двудольного графа, равно произведению количества вершин в каждой доле.
3. Если в дереве двудольного графа удалить одну вершину и все ребра, связанные с ней, граф остается связным.

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

Дерево двудольного граф является одной из важных структур данных в графовой теории и имеет много различных приложений в реальном мире.

Доказательство существования дерева двудольного графа

У любого связного графа существует деление его вершин на две доли таким образом, что каждое ребро графа соединяет вершины различных долей.

Доказательство этого утверждения может быть проведено с помощью алгоритма обхода графа в ширину. Алгоритм начинает с выбора произвольной вершины и помещает ее в первую долю. Затем алгоритм обходит все непосещенные вершины графа, добавляя их во вторую долю. При этом алгоритм обрабатывает все ребра графа, и если обнаруживает ребро, соединяющее две вершины из одной доли, то граф не является двудольным и алгоритм прекращает свою работу.

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

Примером применения данного доказательства является следующая ситуация: представим, что у нас есть компания, в которой сотрудники занимаются двумя направлениями – разработкой программного обеспечения и тестированием. У нас есть информация о связях между сотрудниками, и нам нужно определить, могут ли эти два направления работать автономно, независимо друг от друга. Мы можем представить сотрудников компании в виде вершин графа и связи между ними в виде ребер. Если мы можем разделить сотрудников на две группы таким образом, чтобы в каждой группе были сотрудники только одного направления, то это означает, что компания может работать двудольно — каждое направление может работать независимо от другого.

Свойства дерева двудольного графа

Дерево двудольного графа имеет несколько важных свойств:

1.	Каждое ребро графа соединяет вершины, принадлежащие разным долям.
2.	Граф не содержит циклов.
3.	Количество вершин в каждой доле равно.
4.	Максимальное количество ребер в дереве двудольного графа равно произведению количеств вершин в каждой доле.
5.	Минимальное количество ребер в дереве двудольного графа равно максимальному потоку.

Эти свойства позволяют использовать деревья двудольных графов в различных задачах. Они могут быть полезны при моделировании социальных сетей, планировании расписаний, оптимизации процессов и других задачах.

Примеры двудольных графов

Двудольные графы встречаются во многих областях, и они помогают нам изучать различные свойства и характеристики объектов.

Ниже приведены несколько примеров двудольных графов:

A -- B A -- B | | или | | C -- D E -- F

В первом примере граф состоит из двух долей, помеченных A и B, и соединенных ребрами. Вершины A и B соединены ребром, а также вершины C и D. Граф второго примера также содержит две доли, но ребра соединяют вершины разных долей.

A -- B -- C | | D -- E -- F

В этом примере граф также состоит из двух долей, но вершины в каждой доле соединены ребрами только с вершинами из другой доли. Например, вершина A соединена только с B, а вершина B соединена с A и C.

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

Двудольные графы — Теория графов

В этом уроке мы разберем еще один тип графа — двудольный. Узнаем, что это за граф, и как его определить.

Что такое двудольный граф

Двудольный граф — это граф, вершины которого можно разбить на две части. При этом ребра будут проходить только между частями, но никогда внутри одной из них.

Так выглядят двудольные графы:

Вершины графа разбиты на две части — верхнюю и нижнюю. Пересечения возможны только между двумя частями, но не внутри них. При этом верхняя и нижняя части — независимые множества.

Обычно двудольные графы рисуют так, чтобы множество

располагалось сверху, а множество

— снизу. Несмотря на это, не все двудольные графы рисуются именно так. Например, ниже показаны двудольные сетки:

Как определить, что граф двудольный

Чтобы определить двудольный граф, начните с любой вершины и пометьте ее буквой

. Каждую из ее соседей пометьте буквой

, а далее снова пометьте каждую из соседей

. Продолжайте помечать вершины и их соседей противоположными метками.

Если получится, что у двух соседних вершин одинаковые метки или какая-то вершина окажется помеченной и

, значит, граф — не двудольный. Если это не произошло, граф — двудольный. Пример показан ниже:

Предположим, мы попробуем алгоритм на треугольнике

. Начнем с того, что обозначим вершину

. Затем две соседние вершины обозначим

. Далее появляется проблема, так как эти вершины — смежные. Аналогичная проблема возникает и

Такое происходит только с нечетными циклами, поэтому у двудольных графов их не бывает. Нечетные циклы — это единственное, чего не может быть у двудольных графов. Докажем это.

Как доказать теорему о двудольных графах

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

. Выберем любой цикл в графе и пометим вершины

Предположим, мы начинаем трассировку с вершины

. Тогда вторая, четвертая, шестая и следующие четные вершины находятся в

. Когда мы вернемся в начальную вершину, пройдем четное количество шагов. Это значит, что у цикла четная длина:

Предположим, что у нас есть граф, в котором нет нечетных циклов. Выберем любую компоненту графа и любую вершину в ней. Пусть

— все вершины компоненты на четном расстоянии от

— все вершины компоненты на нечетном расстоянии от

Мы утверждаем, что это образует двудольное разбиение компоненты. Для этого покажем, что нет ребер ни внутри

Предположим, что существует такое ребро между вершинами

, которые находятся в

находятся либо на четном расстоянии от

, либо на нечетном.

Напомним, что расстояние между вершинами — это длина кратчайшего пути между ними. Рассмотрим кратчайшие пути из

— последняя общая вершина этих путей. Путь

, за которым следует ребро

Его длина — это сумма слагаемых:

• Расстояние от до
• Расстояние от до

При этом сумма этих слагаемых будет четной. Внутри

не может быть ни одного ребра. Таким образом,

образуют двудольное разбиение компонента. Мы можем проделать тот же процесс для каждой компоненты, чтобы получить двудольное разбиение всего графа.

Пример нечетного цикла, который создали во второй части доказательства:

Теперь нужно выбрать вершину и разбить граф на две группы:

• Вершины, которые находятся на четном расстоянии от выбранной вершины
• Вершины, которые находятся на нечетном расстоянии от выбранной вершины

Это основная идея доказательства. Во многих теоремах в теории графов есть одна большая идея, вокруг которой вращается доказательство.

Что такое полный двудольный граф

У двудольных графов есть еще один класс — полные двудольные графы. У них есть возможные ребра между двумя частями.

обозначает полный двудольный граф, одна часть которого состоит из

вершин, а другая —

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно

• 130 курсов, 2000+ часов теории
• 1000 практических заданий в браузере
• 360 000 студентов

Наши выпускники работают в компаниях:

Используйте Хекслет по-максимуму!

• Задавайте вопросы по уроку
• Проверяйте знания в квизах
• Проходите практику прямо в браузере
• Отслеживайте свой прогресс

Задавайте вопросы, если хотите обсудить теорию или упражнения. Команда поддержки Хекслета и опытные участники сообщества помогут найти ответы и решить задачу

Для перемещения по курсу нужно зарегистрироваться
1. Введение ↳ теория
2. Типы графов ↳ теория
3. Оптимизация маршрутов ↳ теория
4. Нотации ↳ теория
5. Подграфы ↳ теория
6. Связанность графов ↳ теория
7. Изоморфизм ↳ теория
8. Двудольные графы ↳ теория
9. Деревья ↳ теория
10. Остовные деревья ↳ теория
11. Взвешенный граф ↳ теория
12. Алгоритм Дейкстры ↳ теория
13. Эйлеровы схемы ↳ теория
14. Гамильтонов цикл ↳ теория
15. Доказательство гамильтонова цикла ↳ теория
16. NP-полнота ↳ теория
17. Раскрашивание графа ↳ теория
18. Диграфы ↳ теория
19. Связанность ↳ теория
20. Теорема Менгера ↳ теория
21. Поточная сеть ↳ теория

Поможем, если трудно

Порой обучение продвигается с трудом. Сложная теория, непонятные задания… Хочется бросить. Не сдавайтесь, все сложности можно преодолеть. Рассказываем, как

Не понятна формулировка, нашли опечатку?

Выделите текст, нажмите ctrl + enter и опишите проблему, затем отправьте нам. В течение нескольких дней мы улучшим формулировку или исправим опечатку

Что-то не получается в уроке?

Загляните в раздел «Обсуждение»:

1. Изучите вопросы, которые задавали по уроку другие студенты — возможно, ответ на ваш уже есть
2. Если вопросы остались, задайте свой. Расскажите, что непонятно или сложно, дайте ссылку на ваше решение. Обратите внимание — команда поддержки не отвечает на вопросы по коду, но поможет разобраться с заданием или выводом тестов
3. Мы отвечаем на сообщения в течение 2-3 дней. К «Обсуждениям» могут подключаться и другие студенты. Возможно, получится решить вопрос быстрее!

Подробнее о том, как задавать вопросы по уроку

Двудольный граф: примеры. Теория графов

Двудольные графы — удивительные математические объекты с множеством практических применений в самых разных областях. Давайте разберемся, что это такое, изучим примеры и научимся строить такие графы.

Определение двудольного графа

Формально, двудольный граф — это граф, множество вершин которого можно разбить на две части так, что каждое ребро соединяет вершину из одной части с вершиной из другой. Иными словами, нет ни одного ребра, которое соединяло бы две вершины внутри одной части.

Интуитивно это можно представить так: есть две группы объектов, и связи между ними образуют ребра графа. Но объекты внутри каждой группы не связаны ребрами.

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

Рассмотрим пример полного двудольного графа \K3,3\. Здесь 3 вершины в первой доле и 3 вершины во второй. И каждая вершина первой доли соединена ребрами со всеми вершинами второй:

Как проверить, является ли граф двудольным

Чтобы проверить, является ли произвольный граф двудольным, можно использовать следующий алгоритм:

1. Выбрать любую непосещенную вершину и поместить в первую долю
2. Пройти по графу в ширину, помещая новые вершины во вторую долю
3. Если при обходе ребро ведет в уже посещенную вершину, проверить, чтобы обе вершины были в разных долях
4. Повторять обход из непосещенных вершин, пока есть такие

Разберем этот алгоритм на конкретном примере графа:

Начнем обход из вершины A и поместим ее в первую долю. Затем по ребрам перейдем в вершины B и C, добавив их во вторую долю. Далее обходим оставшиеся вершины, не нарушая правило разделения на доли. Таким образом, получаем разбиение на 2 доли и видим, что граф действительно двудольный.

Асимптотическая сложность этого алгоритма составляет O(V+E), где V — количество вершин, E — количество ребер. То есть линейная сложность от размера графа. Что вполне приемлемо для практики.

Для оптимизации стоит начинать обход из висячих вершин (со степенью 1). Тогда с вероятностью 50% мы сразу попадем в нужную долю и сократим количество переборов.

Примеры двудольных графов

Двудольный граф естественным образом моделирует бинарные отношения между объектами двух типов. Например, отношение «студент сдал экзамен по предмету». Здесь студенты — объекты первого типа, предметы — второго типа. А сдача экзамена — это ребро между соответствующими вершинами графа.

Другой классический пример — граф футболистов и клубов. Где футболисты — первая доля вершин, клубы — вторая. А ребро означает, что игрок выступал за данный клуб.

Еще один интересный пример — сеть знакомств. Пусть есть компания людей, разбитая на мужчин и женщин. Тогда знакомство между мужчиной и женщиной — это ребро двудольного графа знакомств.

Задачи на двудольных графах

Рассмотрим некоторые типичные задачи, возникающие на двудольных графах.

Задача о паросочетаниях

Паросочетанием в двудольном графе называется подмножество ребер, никакие два из которых не имеют общей вершины. Паросочетания часто применяются при составлении расписаний и решении задач о назначениях.

Например, если вершины — это уроки и учителя, то максимальное паросочетание соответствует такому назначению уроков учителям, чтобы каждый учитель вел максимально возможное количество уроков одновременно.

Задача о минимальном разбиении на паросочетания

Если нужно разбить все ребра двудольного графа на паросочетания так, чтобы их было минимально возможное число — это тоже классическая задача теории расписаний.

Например, чтобы спланировать минимальное число дней экзаменационной сессии, при условии что в один день студент может сдавать только один экзамен.

Неориентированный граф против ориентированного

До сих пор речь шла о неориентированных графах, где направление ребер не имеет значения. Но что если ввести ориентацию?

Например, в графе студентов и предметов направление ребра «студент -> предмет» может обозначать желание студента сдавать данный предмет, а обратное направление — то, что предмет уже сдан.

Особенности ориентированного двудольного графа

При работе с ориентированным двудольным графом следует учитывать дополнительные особенности:

• Различаются входящие и исходящие ребра для каждой вершины
• Могут существовать ребра только в одном направлении между вершинами
• Понятие паросочетания требует корректного определения

Применение двудольных графов на практике

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

Двудольное представление конфликтов

Если есть две группы агентов с противоположными интересами, то все потенциальные конфликты между ними можно представить в виде ребер двудольного графа. Это позволяет использовать известные алгоритмы для анализа и предотвращения конфликтов.

Моделирование транспортных сетей

Транспортные сети, соединяющие пункты отправления и пункты назначения, также можно представить с помощью двудольного графа. Здесь в одной доле находятся пункты отправления грузов, а в другой — пункты получения. Ребра обозначают возможные маршруты доставки.

Такое представление позволяет эффективно решать задачи оптимизации логистических потоков методами теории графов.

Построение расписаний

Уже упоминалась возможность использования двудольного графа для моделирования задачи составления расписания. Рассмотрим подходы к решению такой задачи более подробно.

Жадный алгоритм

Простой эвристический алгоритм заключается в следующем:

1. Выбрать вершину с максимальной степенью
2. Назначить ей максимально возможное число паросочетаний
3. Повторять, пока есть неназначенные вершины

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

Метод ветвей и границ

Для точного решения можно применить метод ветвей и границ — перебор вариантов с отсечением заведомо неоптимальных решений. Это позволяет найти оптимальное расписание, но требует экспоненциального времени в худшем случае.

Открытые проблемы теории двудольных графов

Несмотря на кажущуюся простоту, двудольные графы продолжают привлекать внимание исследователей. Рассмотрим две известные открытые проблемы в этой области.

Гипотеза о паросочетаниях

Эта гипотеза утверждает, что любой двудольный граф с n вершинами в каждой доле имеет паросочетание размера не меньше 0.8n. Пока не удалось ни доказать, ни опровергнуть эту гипотезу в общем случае.

Докажите что дерево это двудольный граф

Доказать, что всякое дерево является двудольным графом.

Пожалуйста, используйте IE6/7/8 с плагином MathPlayer, Firefox с установленными математическими шрифтами или Opera 9.5 и выше.

Объявления		Последний пост
Работодателям и кадровым агентствам: Размещение вакансий	26.03.2008 03:07
Запущен новый раздел «Задачки и головоломки»	29.08.2019 00:42
Книги по математике и экономике в добрые руки!	07.10.2023 13:49

26.01.2011 11:42
Дата регистрации:
12 лет назад
Доказать, что всякое дерево является двудольным графом.

«Доказать, что всякое дерево является двудольным графом.»

Нужно полное доказательство. Если можно — с примером.

Редактировалось 1 раз(а). Последний 31.01.2011 19:58.

26.01.2011 11:59
Дата регистрации:
14 лет назад
Посты: 3 155

1. Граф является двудольным тогда и только тогда, когда он не содержит цикла нечётной длины.
2. В дереве нет как четных, так и нечетных циклов.

26.01.2011 12:20
Дата регистрации:
15 лет назад
можно и конструктивно ��

Подвесим дерево за какую-нибудь вершину. Скажем, что это первый этаж. Все вершины, которые смежны с ней, образуют второй этаж. Все нерассмотренные вершины, которые смежны с вершинами второго этажа, поселим на третий этаж и т.д.

А потом вершины с нечетных этажей в одну долю, с четных — в другую.

26.01.2011 12:30
Дата регистрации:
12 лет назад

«Граф является двудольным тогда и только тогда, когда он не содержит цикла нечётной длины.»
Доказательство этого я нашёл.

«В дереве нет как четных, так и нечетных циклов.»
А есть како-либо доказательство этого? Или так и записывается в ответе к заданию?

Прошу прощения, если туплю, но я просто вообще ничего не смыслю в Теории графов.

Деревья и двудольные графы

В двудольном граф циклы, если они есть, имеют чётную длину. Дерево – это связный двудольный граф (без циклов, естественно) Если доли вершин двудольного графа перемешаны, то можно по рисунку графа эти доли определить. Надо взять любую вершину и пометить её, как принадлежащую к первой доле (буквой А, например). Тогда все смежные к этой вершине вершины будут из второй доли (буква Б), и, в свою очередь, смежные к вершинам второй доли вершины будут из первой доли, и так далее. Таким же способом можно определять и «двудольность» произвольного графа. Если вершины одной доли смежны, то это не двудольный граф. Любое дерево может быть задано его двоичным кодом. Код дерева имеет длину 2mи состоит изmнулей иmединиц. Для любого начального отрезка кода дерева число единиц в нём не больше числа нулей. Код дерева всегда начинается с 0 и заканчивается 1. Код дерева зависит от того, какую вершину мы выберем в качестве корня. Дерево с одним ребром и двумя вершинами имеет код 01. Каждое ребро дерева имеет в коде свой ноль и свою единицу, причем единица всегда находится в коде далее нуля. Код получается в результат обхода дерева. Обход начинается и заканчивается в корне дерева. Если ребро дерева встречается при обходе первый раз, то в коде появляется 0 этого ребра, а если второй (и последний), то в коде появляется 1 этого ребра. Например, цепочка из 5 вершин (C) является простейшим деревом и имеет код 00001111. Колесо с nвершинами (W) имеет одну вершину степениn-1 в центре (ось колеса) иn-1 вершину степени три по окружности колеса. У колеса есть спицы (рёбра, выходящие из оси колеса)..W=K, например, (тетраэдр). Число Каталана – это число бинарных деревьев с nвершинами. Бинарное дерево сn=0 – это пустое дерево, а сn>0 вершинами – это тройка Д=(Л, К, П), где К – вершина, называемая корнем дерева, Л – левое поддерево с Л вершинами и П – правое поддерево с П вершинами иn=Л+1+П. С— число различных бинарных деревьев сkвершинами (число Каталана).C=C=1 и если 0Cразличных бинарных деревьев вида (s, К,k-1-s). s принимает значения от 0 доk-1, и, значит, С=CС+CС+ . . . + СCиk>0. С помощью производящей функции получается, что С=C/(k+1). Остовное дерево связного графа содержит все его вершины и некоторые рёбра. Для получения остовного дерева в графе находят цикл и убирают из него произвольное ребро. Затем опять находят цикл и убирают ребро, пока циклов в графе не останется. Остовных деревьев может быть несколько. Цикломатическое число графа – это число рёбер, которые надо удалить из графа, чтобы превратить граф в лес (в дерево, если граф связен).=p+m-n. Цикломатическое число леса (и дерева) равно нулю.

Задания по деревьям и двудольным графам

М.	Определить число попарно различных двудольных графов с а) n=6 m=8; б) n=5 m=9; в) n1=3 n2=4 m=9. n=n1+n2

И.	Доказать, что существует ровно 6 неизоморфных деревьев с 6 вершинами и 11 – с 7 вершинами.

А.	Доказать, что во всяком дереве с n>1 вершинами содержится не менее 2 висячих вершин.
Б.	Пусть n1 – число висячих вершин n-вершинного дерева, не содержащего вершин степени 2. Доказать, что n1>n/2.
В.	Индукцией по n доказать, что каждое дерево с n>1 вершинами является двудольным графом. Какие деревья являются полными двудольными графами?
Г.	Изобразить все попарно неизоморфные деревья: а) с 6 рёбрами и 3 висячими вершинами; б) с 6 рёбрами и 4 висячими вершинами; в) с 7 рёбрами и 3 висячими вершинами; г) с 8 рёбрами и 3 вершинами степени 3.
Д.	Подсчитать число попарно неизоморфных 7-вершинных деревьев, у которых сумма квадратов степеней вершин меньше 27.
Е.	Существуют ли двудольные кубические (регулярные, степени 3) графы? Нарисовать, если да. Может ли быть различным число вершин в долях в регулярном двудольном графе?
П.	Если графы G и H (без петель и кратных рёбер) изоморфны, то для каждого d>-1 число вершин степени d в графах G и H одинаково. Показать, что а) это условие (подчёркнуто выше) является достаточным для изоморфизма графов с 4 и менее вершинами; б) условие не является достаточным для изоморфизма графов с 5 и более вершинами, причём, если число вершин не менее 6, то даже для деревьев.

Р.	Описать и нарисовать все графы, являющиеся деревьями вместе со своими дополнениями.
Ж.	Построить все попарно неизоморфные растущие деревья (в них существует источник с полустепенью захода, равной нулю) с а) 4 вершинами; б) 5 вершинами; в) 6 вершинами, не содержащие ориентированных цепей длины, превосходящей 3.
З.	Доказать, что слабо связный орграф является растущим деревом (в нём существует источник с полустепенью захода, равной нулю) тогда и только тогда, когда лишь одна его вершина имеет нулевую полустепень захода, а полустепень захода любой из остальных вершин равна 1.
Т.	Построить дерево по его коду: а) 0010100111; б) 00110101000111; в) 0000010011011111; г) 01001000110111; д) 00100010110111; е) 00010111010000101111.
У.	По вектору установить, является ли он кодом дерева (если да, то построить дерево): а) 001011; б) 110 0110; в) 001001; г) 010011; д) 00111001; е) 0001100111.
Ф.	Множество векторов разбить на классы так, чтобы каждый класс состоял из кодов попарно изоморфных деревьев: а) ; б) ; в) .

Х.	Доказать по индукции, что для каждого дерева в его коде число нулей совпадает с числом единиц, и число единиц среди первых k координат кода (km) не превосходит числа нулей среди тех же координат. Длина кода дерева равна 2m, где m – число рёбер в дереве.
Ц.	Длина кода дерева равна 2m, где m – число рёбер в дереве. В коде дерева m нулей и m единиц, код начинается с нуля и заканчивается единицей. Пусть f(m) – количество различных кодов деревьев с m рёбрами. Доказать: а) f(m)+1; б)f(m)+1; в) f(m)+1.
Ч.	Длина кода дерева равна 2m, где m – число рёбер в дереве. В коде дерева m нулей и m единиц, код начинается с нуля и заканчивается единицей. Пусть f(m) – количество различных кодов деревьев с m рёбрами. Доказать: f(m)=. f(0)=f(1)=1 (Число Каталана)
Ъ.	Вершина корневого дерева называется висячей, если она отлична от корня и имеет степень, равную 1. а) у дерева k висячих вершин и нет вершин степени 2, отличных от корня. Доказать, что при k>1 nk+1; б) пусть степени всех n вершин, кроме корня, не превышают 3, а степень корня не превышает 2. Доказать, что число висячих вершин не больше n/2.

S.	Диаметр дерева – длина максимальной простой цепи в нём. Доказать, что в дереве с нечётным диаметром любые две простые цепи максимальной длины имеют хотя бы общее ребро. А с чётным?
Я.	Доказать, что некорневое дерево однозначно с точностью до изоморфизма восстанавливается, если заданы все попарные расстояния между его висячими вершинами.
Ю.	Расстояние между вершинами – это длина кратчайшей цепи, соединяющей их. Диаметр графа – это max расстояний в нём. а) для каждого d>2 указать граф, диаметр которого равен d, а диаметр любого его связного остовного (содержащего все вершины графа) дерева равен 2d.
Ы.	Вычислить цикломатическое число а) полного графа с n вершинами (K); б) полного двудольного графа сn1 и n2 вершинами в долях (K); в) пустого графа сn вершинами (n изолированных вершин — N); г) колеса сn вершинами (W); д) платоновых графов: тетраэдра (K), куба, октаэдра, додекаэдра; е) графа Петерсена; ж) любого связного регулярного степениr (степени всех вершин равны r) графа с n вершинами.

Ь.	Остовное дерево графа содержит все вершины графа и некоторые его рёбра. Найти остовное дерево: а) полного графа с 5 вершинами (K); б) полного двудольного графа с тремя вершинами в каждой из долей (K); в) колеса с 5 вершинами (W); г) циклического графа с 6 вершинами (C); д) графа Петерсена; е) платоновых графов: тетраэдра (K), куба, октаэдра, додекаэдра.
Э.	Остовное дерево графа содержит все вершины графа и некоторые его рёбра. Пусть T1 и T2 – остовные деревья графа G. Доказать, что для каждого ребра e из T1 существует ребро f из T2, и если в T1 заменить e на f, то получим опять остовное дерево графа G. Доказать, что T1 можно перевести в T2 , меняя по очереди рёбра из T1 на рёбра из T2.
К.	Приведите примеры (когда это возможно) а) регулярного (степени всех вершин равны) двудольного графа; б) двудольного платонова графа (тетраэдр (K), куб, октаэдра, додекаэдр); в) бесконечного двудольного графа.
Л.	Что можно сказать о дополнении полного двудольного графа? Дополнение графа – это граф с те ми же вершинами и с рёбрами, которых нет в самом графе. Опишите матрицу смежности двудольного графа. Что можно сказать о матрицах смежности двудольного графа и его дополнения?

О.	Люди – это вершины, а знакомых людей связывает ребро. Доказать, что среди 6 человек всегда найдутся 3 таких, которые либо все знают друг друга (цикл длины 3), либо ни один из них не знает двух других.
Н.	G – двудольный граф с наибольшей степенью вершин d. Покажите, что существует двудольный граф G1(v1,v2), в котором v1 и v2 содержат одинаковое число вершин и G1 — регулярный граф степени d, причём G – это подграф G1. Показать алгоритм построения G1 из G.
G.	Расстояние между вершинами – это длина кратчайшей цепи, соединяющей их. Диаметр графа – это max расстояний в нём. Диаметр дерева – длина максимальной простой цепи в нём. Доказать, что для каждого связного графа существует его остовное дерево, диаметр которого не более чем в два раза превосходит диаметр графа.
С.	Построить коды деревьев:

Двудольные графы

Работа Куприяновой Елизаветы посвящена изучению темы «Двудольные графы». Данная тема актуальна с практической точки зрения. Умение решать нестандартные задачи необходимо для успешного выступления на олимпиадах различного уровня и ЕГЭ, В своей работе ученица рассматривает всевозможную теорию по данной теме, различные подходы к решению олимпиадных задач. Реферативная часть выполнена на высоком уровне и представляет серьезную работу. Материал изложен последовательно и четко.

Скачать:

Вложение	Размер
dvudolnye_grafy.docx	116.2 КБ

Предварительный просмотр:

Муниципальное автономное образовательное учреждение лицей №14 имени Заслуженного учителя Российской Федерации А.М. Кузьмина

Индивидуальный проект по теме:

ученица 10 класса А

Неверовская Светлана Владимировна

1. общее понятие 4

3. теорема кенига 10

ВВЕДЕНИЕ

Среди жителей Кёнигсберга была распространена такая практическая головоломка: можно ли пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды? В 1736 году выдающийся математик Леонард Эйлер заинтересовался задачей и в письме другу привел строгое доказательство того, что сделать это невозможно. В том же году он доказал замечательную формулу, которая связывает число вершин, граней и ребер многогранника в трехмерном пространстве. Формула таинственным образом верна и для графов, которые называются «планарными». Эти два результата заложили основу теории графов и неплохо иллюстрируют направление ее развития по сей день. Граф как математический объект оказался полезным во многих теоретических и практических задачах. Наверное, дело в том, что сложность его структуры хорошо отвечает возможностям нашего мозга: это структура наглядная и понятно устроенная, но, с другой стороны, достаточно богатая, чтобы улавливать многие нетривиальные явления.

Побывав в зимней математической школе при МФТИ, я узнала о небольшой, но в то же время сложной олимпиадной теме. Речь идет о теме “Двудольные графы”. Времени на нее уделялось относительно немного, и я решила изучить ее более подробно самостоятельно.

Актуальность. Данная тема актуальна, так как такие задачи могут встретиться в олимпиадах различного уровня. Но, к сожалению, школьная математика не предусматривает решения задач на двудольные графы. Некоторые дети заинтересованы в том, чтобы поступить в университеты с помощью олимпиад, таким образом, я попыталась собрать всю информацию по данной теме в своем проекте. Стоит заметить, что решение задач на эту тему, развивает логику.

Объектом исследования является процесс изучения темы “Двудольные графы”.

Предмет исследования – возможность применения полученных знаний.

Цель исследования – рассмотреть и овладеть знаниями о теме “Двудольные графы”.

В процессе работы я поставила перед собой следующие задачи :

• Разобрать всевозможную теорию по теме “Двудольные графы”;
• Собрать в своем проекте различные задачи на данную тему.

ОСНОВНАЯ ЧАСТЬ

общее понятие

Двудольный граф – граф, вершины которого можно разбить на два множества так, что каждое ребро соединяет вершины из разных множеств.

Все вершины графа можно покрасить в два цвета так, что ребра соединяют только разноцветные вершины.

Полный двудольный граф – двудольный граф, у которого все вершины в разных долях соединены ребрами.

Любое дерево – двудольный граф(в дереве отсутствуют любые циклы, в том числе и нечетные).

– двудольный граф тогда и только тогда, когда все его простые циклы имеют четную длину.

• Доказательство в одну сторону(“ ”):

1. Раскрасим вершины графа в два цвета.
2. Возьмем какой-то простой цикл.
3. Все вершины разбились на пары.
4. Следовательно, граф четной длины.

• Доказательство в обратную сторону(» ”):

1. Пусть — некоторая вершина.
2. Будем считать, что граф – связанный. Т.е. если взять какую-то одну компоненту, раскрасить ее в два цвета, взять следующую компоненту, снова раскрасить ее в два цвета. Поскольку между компонентами ребер никаких нет, можно красить любым способом, лишь бы в компонентах проблем не возникало.
3. Берем некоторую вершину. Поскольку мы живем в одной компоненте связанности, все вершины как-то связаны с вершиной . Мы можем рассматривать самые короткие пути, которые ведут в эту вершину.
4. Рассмотрим кратчайшие пути из в остальные вершины. Покрасим в белый цвет. Если путь из в — четный, то красим в белый цвет, а если путь – нечетный, то красим в черный цвет.
5. Докажем, что нет ребер между одноцветными вершинами. От противного . У нас есть две доли, в какой-то доле внутри нашлось ребро, соединяющее вершины этой доли. И где-то здесь у нас живет вершина . Тогда у нас есть какой-то путь в . Давайте поймем, что найдется простой цикл нечетной длины, ведь просто цикл нечетной длины уже нашелся ( ). Давайте сделаем цикл простым. Пойдем путями и , если эти пути никогда не пересекутся, то мы уже нашли простой цикл. Пусть эти пути пересеклись, — точка пересечения, тогда путь из в по разным маршрутам имеет одну и ту же длину, потому что у нас путь из в был кратчайшим. Путь из в по — кратчайший, а путь из в по — тоже кратчайший, следовательно, у них одна и та же длина. Получается, что имеет нечетную длину, а следовательно, цикл простой.

Следствие: всякое дерево, содержащее более одной вершины, является двудольным графом.

Паросочетание – набор ребер, такой что любая вершина – конец ровно одного из них.

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

Очевидно, что всякое совершенное паросочетание максимально. Обратное неверно.

лемма холла

Данная лемма также известная как лемма о свадьбах или лемма о девушках.

Имеется n юношей и n девушек, которые как-то между собой знакомы, и известно, что любые k юношей вместе знакомы хотя бы с k девушками. Тогда их можно переженить таким образом, что в каждой паре будут знакомые.

Мы берем любой набор юношей, тогда смотрим девушек, которые с ними знакомы. Тогда девушек будет не меньше, чем юношей.

Доказательство по индукции:

Понятно, что условие не только достаточное, но и необходимое.

База : очевидна (если есть 1 юноша, то есть девушка, которая с ним знакома)

1. Есть группа из юношей, которая знакома ровно с девушками. Тогда, во-первых, понятно, что по предположению индукции с этой группой мы можем разобраться, потому что , ежели такая группа найдется, то в этой группе по предположению индукции мы так можем переженить. Если мы сейчас проверим, что в дополнение к этой группе требуемое условие выполнено, то задача будет выполнена. Проверим, что дополнение к этой группе тоже удовлетворяет условию леммы Холла. Мы берем этих самых юношей, выкидываем девушек, которые с ними знакомы, забываем про них, потому что их мы можем разбить на пары. Остается юношей и девушек(C). Эти оставшиеся юноши и девушки тоже должны удовлетворять условию леммы Холла. Давайте в этом убедимся. Пусть группа юношей – A, группа девушек – B, группа оставшихся юношей и девушек, о которых говорилось выше, — С. Тогда возьмем m юношей из группы С. Рассмотрим группу , у нас получается юношей. Эти юноши знакомы с девушек. Давайте посмотрим, что будет, если отсюда выкинуть А. знакомы с (некая добавка D). Что будет, если мы отсюда выкинем А? Из группы надо будет стереть всех знакомых с А. Тогда все остальные девушки должны быть знакомы с . А как выглядят все знакомые с ? Это как раз и есть группа . Поэтому мы получили, что те юноши, которые составляют группу , знакомы с девушками из группы (в группе у нас человек, тогда в группе получается человек). Выходит, что те юношей знакомы с девушками. Таким образом, оставшиеся юношей и оставшиеся девушек тоже удовлетворяют условию леммы Холла. Следовательно, про предположению индукции, их мы можем разбить на пары, а, соответственно, тех, что выкинули, мы тоже может разбить на пары.
2. Если такая группа не найдется, то любых юношей сторого больше, чем знакомых девушек, то есть мы имеем хотя бы знакомых девушек. Тогда у нас есть юноша и девушка. Мы берем их этого набора любого юношу. Он знаком с какой-то девушкой, так как по условию леммы Холла в группе из одного юноши тоже есть хотя бы одна знакомая девушка. Тогда у нас останется юношей и девушек. НО! Если мы возьмем теперь юношей, то сколько у нас будет знакомых девушек? Вместе с той одной получается хотя бы , а без той – хотя бы . А когда мы выкинем тех девушку и юношу, у нас останется набор из юношей и девушек, которые удовлетворяют условию леммы Холла. А значит, по предположению индукции, мы можем разбить их на пары.

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

Переформулировка на языке графов:

Имеется двудольный граф, у которого по вершин в каждой доле, и он обладает следующим условием. – доли графа, тогда верно, что для любого подмножества доли количество смежных с ней вершин меньше, чем количество вершин в доле . Тогда в графе существуют паросочетания.

Несложно заметить, что эта та же самая теорема.

Пусть доля — юноши, а доля – девушки, тогда знакомства – это наличие ребра в графе.

Условие: для любого количество вершин, смежных с (количества элементов в области ).

Мы берем какое-то количество юношей. И тогда девушки, которые с ними знакомы, их количество не меньше, чем количество юношей. Ну а паросочетание – это и будет разбиение юношей и девушек на пары.

Переформулировка на языке теории множеств:

У нас есть множества , и для любого набора этих множеств (набора индексов) количество элементов в объединении множеств( ) хотя бы k ( ).

практика

Подсчитать количество совершенных паросочетаний у дерева на n вершинах.

Дерево может либо иметь лишь одно совершенное паросочетание, либо не иметь таких паросочетанй вообще. Докажем это по индукции.

Дерево (определенное на 2 вершинах) имеет единственное совершенное паросочетание, а дерево (определенное на 1 вершине) совершенного паросочетания не имеет. Рассмотрим теперь дерево на вершинах и какой-то лист в нем. Совершенное паросочетание должно покрывать вершину . Следовательно, оно должно включать в себя ребро , где — единственная смежная с вершина дерева . При этом все другие ребра, инцидентные , в строящееся паросочетание включать уже нельзя. Удаляя тогда вершины , мы получаем в общем случае лес, состоящий из нескольких деревьев. По индукционному предположению, у каждого из этих деревьев имеется либо одно, либо ни одного совершенного паросочетания. Предположим, что в каждом из этих деревьев имеется совершенное паросочетание. В этом случае, добавляя к ребрам этих паросочетаний ребро , мы получаем единственное паросочетание в исходном дереве . В противном случае, в дереве совершенные паросочетания отсутствуют.

Найти количество совершенных паросочетаний в полном графе на 2n вершинах.

Таких паросочетаний в полном графе ровно штук. Действительно, вершину мы можем соединить ребром с любой другой вершиной полного графа. Следовательно, имеется способ выбрать ребро, соединяющее вершину с любой другой, отличной от нее вершиной полного графа. В оставшемся графе возьмем любую пока еще не покрытую паросочетанием вершину . Ее мы можем соединить ребром с любой из оставшихся вершин, не покрытых строящимся паросочетанием. Продолжая далее, мы получим, что количество совершенных паросочетаний равно .

В каждой строке и в каждом столбце шахматной доски стоят по три ладьи. Докажите, что можно выбрать 8 ладей, не бьющих друг друга.

Пусть столбцы – юноши, а строки – девушки. Выбрать 8 ладей, не бьющих друг друга, – выбрать 8 пар строк и столбцов таких, что все строки и столбцы разные, т.е. переженить 8 юношей и девушек. Докажем от противного.

Пусть существуют k юношей, которые знакомы с меньше, чем k девушками. Пусть они знакомы с n девушками.

Тогда от доли юношей будет отходить 3k ребер, при этом знакомы юноши только с n девушками. А от доли девушек выходит 3n ребер, которые приходят ко всем юношам. Тогда получаем, что . Но по условию , а значит . Противоречие. Следовательно, k юношей знакомы не менее, чем с k девушками, тогда мы можем составить k пар. Значит, можем выбрать 8 ладей, не бьющих друг друга.

Задачи для тренировки:

1. Из шахматной доски вырезали 7 клеток. Докажите, что на оставшиеся клетки можно поставить 8 не бьющих друг друга ладей.
2. Лист бумаги с обеих сторон разбит на 2016 многоугольников равной площади. Докажите, что его можно проткнуть в 2016 местах, чтобы каждый многоугольник оказался проткнутым ровно по одному разу.
3. На улице болтунов живут по n юношей и n девушек, причем каждый юноша знаком ровно с k девушками., а каждая девушка – ровно с k юношами.

• Докажите, что все юноши и девушки могут одновременно говорить со своими знакомыми по телефону.
• Докажите, что юноши и девушки могут звонить друг другу по телефону так, чтобы за k часов каждый поговорил с каждым из своих знакомых по часу.

теорема кенига

Рассмотрим бесконечную шахматную доску. На этой доске стоит какое-то количество ладей(конечное). Из этого количества всегда можно выбрать какой-то набор, не бьющих друг друга ладей. Например, снять все ладьи кроме одной. В частности можно выбрать такой набор из максимального количества ладей. Рассмотрим максимальное количество не бьющих друг друга ладей, которые можно оставить, выкидывая с доски некоторые из них.

Рассмотрим две величины:

1. Максимальное количество не бьющих друг друга ладей, которые можно оставить( ).
2. Наименьшее количество линий, которыми можно накрыть все ладьи( ). Будем линией называть либо строку, либо столбец. Мы можем брать линию и накрывать ее.

• – очевидно, т.к. если у нас есть линии, накрывающие всю картинку, то в каждой линии стоит не больше одной ладьи, т.к. ладья бьет всю линию). Значит в каждой линии не больше одной ладьи, следовательно, всего ладей не больше, чем всего линий.
• (количество ладей больше, либо равно количеству линий). Пусть все накрывается строками и столбцами. Тогда . Всю расстановку ладей мы накрыли . Если мы будем менять местами строки, то ничего не изменится. Мы сможем добиться следующей картинки:

Больше ладей нигде не стоит, их всех запихнули сюда.

Рассмотрим отдельно первый кусок и докажем, что в нем можно поставить ладей, не бьющих друг друга. Аналогично со вторым куском, где можно поставить ладей. Так как кусочки разные и друг друга бить не могут, то получится ладей.

Считаем, что в каждой строке и столбце стоит ладья. Проверим, удовлетворяет ли первый прямоугольник условию леммы Холла, т.е. что-то у нас будет юношами, а что-то – девушками. Пусть строки – юноши, а столбцы – девушки. Тогда у нас есть юношей и хотя бы девушек(т.е. если есть какая-то строка, такая что на этой части нет ни одной ладьи, то эту строку можно было выкинуть сразу, т.к. все ладьи в области 3 накрыты столбцами. А в области 1 хотя бы одна строка есть, следовательно, у каждого юноши хотя бы одна знакомая девушка.

Рассмотрим только столбец из первого прямоугольника. У нас есть строк и сколько-то столбцов. Возьмем несколько строк. На этих частях строк ладьи стоят хотя бы в . Почему это так? Предположим, что ладьи стоят меньше, чем в столбцах. Мы можем стереть эти строк. Ладьи, которые стоят в области 3, нас не волнуют, так как они все равно накрыты столбцами. А строк мы можем заменить на новые меньше, чем столбцов, так как ладьи стоят меньше, чем в столбцов. Мы получим, что покрытие меньше, чем линиями. Следовательно, у каждого юноши найдется набор столбцов хотя бы в штук, получается, что у каждого юноши хотя бы девушек. По лемме Холла мы можем разбить строки и столбцы в области 1 на пары(знакомство – наличие ладьи на пересечении). Мы можем этим строкам в области 1 выбрать столбцов в пары, т.е. есть какая-то строка, есть какой-то столбец, если мы выбрали пару, значит есть какая-то ладья на пересечении и т.д. Таким образом, мы соберем ладей, потому что мы образовали пар. Аналогичные рассуждения проведем с областью 2, только строки заменятся столбцами. Таким образом, выберем здесь ладей, а остальные выкинем. Из области 3 мы выкинем вообще все ладьи. Итак, мы сумеем выбрать хотя бы не бьющих друг друга ладей.

Переформулировка на языке теории графов:

У нас — двудольный граф.

В этом графе мы рассмотри две вещи:

• Максимальное паросочетание, которое покрывает наибольшее количество вершин (мы берем максимальное возможное количество ребер, которые не умеют общих концов).
• Наименьшее количество вершин в графе таких, что все ребра выходят из этих вершин.

Эти величины равны между собой.

Давайте поймем, что это та же самая теорема.

Пусть одна доля графа – это строки, а другая – столбцы. Один элемент из одной доли соединен с элементом из другой доли, если на пересечении строки и столбца стоит ладья. Максимальное паросочетание – максимальное количество ладей, которые можно оставить, чтобы они не били друг друга. Наименьшее количество вершин таких, что все ребра из них выходят, — наименьшее количество линий, которые покрывают все ладьи.

практика

В компании юношей и девушек не менее n человек. Оказалось, что среди них нельзя составить брак по знакомству. Докажите, что тогда можно выбрать n людей так, что из любой пары знакомых один выбран.

Так как из компании n юношей и девушек нельзя выбрать n+1 брак по знакомству. То, переходя на язык теории графов, минимальное вершинное покрытие двудольного графа равно n. По теореме Кенига, минимальное вершинное покрытие равно максимальному паросочетанию в двудольном графе, откуда получаем, что максимальное вершинное покрытие нашего графа равно n. А значит, можно выбрать n людей так, что из любой пары знакомых один выбран.

Докажите, что из 51 числа, не большего 100, можно выбрать 6 чисел, любая пара которых отличается в обоих разрядах.

Пусть десятки – юноши, а единицы – девушки. Тогда от каждого юноши может выходить по 9 ребер, а от каждой девушки – по 10 ребер, где ребро – это знакомство юноши и девушки или по ,условию задачи, число. Тогда минимум у нас может быть 6 чисел. Получается, что минимальное вершинное покрытие в двудольном графе равно 6, откуда следует, что максимальное паросочетание тоже равно 6. Значит, можно выбрать 6 чисел, любая пара которых отличается в обоих разрядах.

Задача для тренировки:

В каждой клетке доски написано неотрицательное вещественное число таким образом, что суммы в каждой горизонтали и вертикали равны 1. Докажите, что можно расставить n не бьющих друг друга ладей так, что стоящие под ними числа будут не нулевые.

ЗАДАЧИ

1. На кружке 20 ученикам было предложено 20 задач. Каждый ученик решил две задачи, и каждую задачу решили ровно двое из них. Докажите, что можно так организовать разбор задач, чтобы каждый ученик объяснил одну задачу, и все задачи были разобраны.
2. На шахматной доске стоят 8k ладей по k ладей в каждой горизонтали и вертикали. Докажите, что на доске можно выбрать 8 ладей, не бьющих друг друга.
3. На дискотеке каждый юноша знаком не менее, чем с M девушками, а каждая девушка – не более, чем с M юношами. Доказать, что каждый юноша может пригласить на танец знакомую девушку.
4. В классе каждый мальчик дружит с тремя девочками, а каждая девочка – с пятью мальчиками. Семнадцать из них любят играть в математическое домино. Всего в классе пятнадцать парт. Сколько детей учится в классе?
5. В строку выписано одиннадцать целых чисел. Для любой группы подряд идущих чисел подсчитана ее сумма(группы из одного числа тоже учитываются). Какое наибольшее количество сумм могло оказаться нечетными?
6. Саша записал в клетки шахматной доски числа от 1 до 64 в неизвестном порядке и сказал Ване сумму чисел в каждом прямоугольнике из двух клеток, добавив, что числа 1 и 64 лежат в одной диагонали. Докажите, что благодаря этой информации Ваня может определить, где какое число записано.
7. В лагерь приехало некоторое количество детей, причем каждый ребенок имеет от 50 до 100 знакомых среди остальных. Доказать, что вожатый Максим сможет раздать им майки 1331 цветов так, чтобы у каждого ребенка среди его знакомых было не менее 20 различных цветов.
8. Квадрат со стороной 1 разбит двумя способами на n равновеликих многоугольников. Доказать, что можно выбрать в квадрате n точек так, что в каждом многоугольнике любого из этих разбиений будет по выбранной точке.
9. Имеется граф, все вершины которого имеют четную степень. Доказать, что из него можно выкинуть некоторое количество ребер, чтобы в оставшемся графе степень каждой вершины была равна двум.
10. Дворец в форме треугольника со стороной 50 метров разбит на 100 треугольников комнат со сторонами 5 метров. В каждой стенке между комнатами есть дверь. Какое наибольшее число комнат сможет обойти человек, не заходя ни в какую комнату более одного раза?
11. Сможет ли конь обойти шахматную доску 7*7 так, чтобы побывать на каждом поле ровно по одному разу и вернуться последним ходом на исходное поле?
12. Можно ли в клетки шахматной доски расставить натуральные числа так, чтобы для любых клеток с общей стороной одно из чисел делилось на другое, а для всех остальных пар клеток такого не было?
13. Пусть в таблице n*n записаны неотрицательные числа, и суммы чисел в каждой строке и в каждом столбце равны 1. Доказать, что можно выбрать n клеток таблицы, из которых никакие две не стоят в одном и том же столбце и в одной и той же строке, и при этом в каждой выбранной клетке число будет положительным.
14. Клетчатый прямоугольник покрыт доминошками так, что каждую клетку покрывают ровно 2 доминошки. Докажите, что доминошки можно разбить на две группы так, что каждая группа полностью покрывает прямоугольник в один слой.
15. В одной стране из каждого города выходит по три железные дороги. Две компании хотят их все приватизировать. Однако антимонопольный комитет требует, чтобы из каждого города выходили дороги обеих компаний. Докажите, что компании могут договориться, чтобы это требование было выполнено.

ЗАКЛЮЧЕНИЕ

Работая над проектом, я выполнила поставленную перед собой цель, т.е. освоила и научилась применять полученные знания по теме “Двудольные графы”. Работая с различными сборниками задач и статьями в математических журналах, считаю нужным отметить отрывочность рассмотрения этой темы.

Для достижения этой цели я изучила теорию по данной теме и связала ее воедино.

Знания, полученные в ходе выполнения проекта, позволяют разнообразить методы решения олимпиадных задач. Эти знания могут пригодиться также и в дальнейшем, например, для участия в олимпиадах.

СПИСОК ЛИТЕРАТУРЫ

1. http://www.zaba.ru/cgi-bin/tasks.cgi?tour=books.sms700.dvudol
2. http://foxford.ru/wiki
3. http://logic.pdmi.ras.ru/~dvk/graphs_dk.pdf
4. http://www.rkarasev.ru/common/upload/taskprob.pdf
5. http://www.alenn.ru/attachments/article/327/О.%20Нечаева.%20Применение%20леммы%20Холла.pdf

Докажите что дерево это двудольный граф

Доказать, что
а) из связного графа можно выкинуть несколько рёбер так, чтобы осталось дерево;
б) в дереве с n вершинами ровно n – 1 ребро;
в) в дереве не меньше двух висячих вершин;
г) в связном графа из n вершин не меньше n – 1 ребра;
д) если в связном графе n вершин и n – 1 ребро, то он – дерево.

Решение

а) Если граф – не дерево, то в нём есть простой цикл. Любое ребро из этого цикла можно выкинуть без нарушения связности. Этот процесс остановится, когда граф станет деревом.

б) У дерева есть висячая вершина (см. задачу 30786). Удалим её вместе с ребром, которое из нее выходит. Оставшийся граф также является деревом. Поэтому у него есть висячая вершина, которую мы также удалим вместе с выходящим из нее ребром. Проделав эту операцию n – 1 раз, мы получим граф, состоящий из одной вершины (в котором, конечно, нет рёбер). Поскольку каждый раз удалялось ровно одно ребро, то сначала их было n – 1.

в) Выйдем из висячей вершины и пойдём по графу как в задаче 30786. Так же как и там этот путь закончится в другой висячей вершине.

г) Удалим из графа несколько вершин, превратив его в дерево. В полученном дереве n – 1 вершина, а в иcходном – не меньше.

д) Если это не так, то, превратив его в дерево, мы получим противоречие с п. б).

Источники и прецеденты использования

книга
Автор	Иванов С.В.
Название	Математический кружок
глава
Номер	5
Название	Графы
Тема	Теория графов
задача
Номер	30

Проект осуществляется при поддержке и .