Решение некоторых экстремальных задач с использованием графов специального вида
Введение
Первые научные результаты по теории графов были получены Леонардом Эйлером, и касались решения некоторых прикладных задач. Они появились в 1736 году. Вначале теория графов казалась незначительным разделом математики, однако дальнейшее развитие науки и, особенно, ее приложений дало сильный толчок развитию теории графов.В начале XX века графы рассматривались, как подраздел топологии, поскольку они обладают некоторыми свойствами, которыми обладают и некоторые топологические пространства. Позже выявились связи теории графов с другими разделами современной математики (например, алгебра и комбинаторика), а различные приложения теории графов к широкому кругу проблем сегодня даже трудно перечислить: это, например, исследования операций и управления, задачи экономики, теории информации, социологии и т.д.
Содержание
Введение
Глава 1. Основные понятия, связанные с графом
Основные определения
Некоторые результаты, связанные с нахождением экстремумов
Виды графов
Глава 2. Виды графов, связанные с ними понятия для решения некоторых экстремальных задач
Двудольный подграф
Вершинное покрытие для графа без треугольников
Граф без четных циклов
Глава 3. Экстремальные графы
Наследственное свойство
Задача о запрещенном подграфе
Теорема Турана
Графы без Km,n: оценка
Проективная плоскость и графы без K2,2
Корни из единицы в Fq и графы без K2,n+1
Заключение
Список литературы
Список литературы
Bollobas. B. Extremal Graph Theory – London: Academic Press, 1978. – 488 с.
Баранов В. И., Стечкин Б. С. Экстремальные комбинаторные задачи и их приложения/ В. И. Баранов, Б. С. Стечкин – М: Наука, 2004. – 240 с.
Берлов С. Л., Карпов Д. В. Факторизация проективной плоскости и экстремальные графы без полного двудольного подграфа K2,n.Моделирование и Анализ Информационных систем / С. Л. Берлов, Д. В. Карпов – т.8, вып. 2, Изд. Ярославского Университета, 2001 – стр. 10-12.
Карпов Д. В. Теория графов / Д. В. Карпов - учеб. пособие. СПб государственный университет. – СПб.: 2017. – 525 с.
Мерзляков А.С. Основы теории графов: учебно-методическое пособие. – Ижевск: ФГБОУ ВПО "Удмуртский государственный университет", 2013. – 24 с.
Райгородский А. М. Экстремальные задачи теории графов и Интернет: Учебное пособие / A.M. Райгородский – Долгопрудный: Издательский Дом «Интеллект», 2012. — 104 с.
Свами М., Тхуласираман К. К. Графы, сети и алгоритмы / М. Свами, К. К. Тхуласираман – М.: Мир, 1984. – 455 c.
Харари Ф. Теория графов / Ф. Харари – М.: Мир, 1973. – 300 с. (Перевод с английского. F.Harary, Graph theory, Addison-Wesley, 1969.)
Двудольный граф – это граф, хроматическое число которого равно двум. Иными словами, множество вершин двудольного графа можно разбить на две части («доли») таким образом, чтобы любое ребро этого графа имело концы на разных частях. Граф называется полным двудольным. Если в нем каждая вершина из первой доли соединена ребром с каждой вершиной из второй доли. Полный двудольный граф, имеющий n вершин в одной доле и m вершин в другой, обозначается . Классическая задача о двудольном графе – это задача о супружеских парах. Есть молодых людей и девушек, причем i-й молодой человек знает представительниц прекрасного пола. Спрашивается, можно ли составить супружеские пары, так, чтобы молодые люди перед браком были знакомы. Очевидна теоретико-графовая интерпретация задачи: одну долю графа составляем из ребят, к другой относим девушек, ребрами соединяем вершины первой и второй долей, если соответствующие люди знают друг друга. Более того, максимальное количество возникающих пар – это размер наибольшего паросочетания в описанном двудольном графе.Еще одна похожая постановка вопроса, задача о назначениях. Есть некоторое количество специалистов, каждый из которых обладает определенным набором навыков. Скажем, специалистов n, а общее число навыков – m. Как определить между специалистами задания, чтобы каждый работал над своей проблемой и притом обладал изначальным навыком работы над ней? Так же берем двудольный граф, в одной доле которого «расположены» специалисты, а в другой – навыки; соединяем специалиста с навыком ребром, если он обладает этим навыком, и ищем наибольшее паросочетание.