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

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ        3

Глава 1. Теоретический раздел        5

1.        Основные понятия        5

2.        Паросочетания. Теорема Кёнига-Эгервари        8

Глава 2. Практическая часть        18

1.        Формула подсчета ребер в двудольном графе        18

2.        Паросочетание в двудольном графе        21

3.        Теория игр        22

ЗАКЛЮЧЕНИЕ        26

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

ВВЕДЕНИЕ

        Теория графов представляет собой один из самых больших, интересных и иногда сложных разделов математики. Она имеет популярность применения в экономических задачах, в программировании, химии, изучении электрических цепей, психологии, социологии и других областях знаний. Теория графов подробно и последовательно изучает графы и их свойства, о которых можно сказать, что они состоят из множеств точек и множеств линий, отображающих связи между этими точками. Основателем теории графов считается Леонард Эйлер (1707-1882), решивший в 1736 году известную в то время задачу о кёнигсбергских мостах.

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

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

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

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

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

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

• Дать определение двудольных графов;
• Рассмотреть свойства двудольных графов;
• Рассмотреть алгоритм двудольности графов;
• Дать определение паросочетанию в двудольном графе;
• Доказать теорему Холла и Кёнига – Эгервари;
• Собрать различные задачи на данную тему.

Глава 1. Теоретический раздел

1. Основные понятия

Определение 1. Граф называется двудольным, если его вершины можно разбить на две группы так, что каждое ребро в этом графе соединяет вершины, принадлежащие разным группам.

[pic 1]

Рис. 1

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

[pic 2]

Рис. 2

Лемма 1 (о необходимых и достаточных условиях разбиения множества вершин графа на два независимых подмножества). Граф является двудольным < = > он не содержит циклов нечетной длины.

Доказательство:

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

Достаточность. Пусть наш граф G – связный и докажем утверждение отдельно для каждой компоненты. Выделим в связном графе G остовное дерево Н. Легко видеть, что вершины дерева Н можно правильным образом покрасить в два цвета, например, выделим любую вершину a и покрасим в цвет 1 вершины на нечетном расстоянии от a, а во второй цвет — саму a и вершины на четном расстоянии от a.