Теория графов и ее приложения



Скачать 19.64 Kb.
Дата08.10.2012
Размер19.64 Kb.
ТипДокументы

ТЕОРИЯ ГРАФОВ И ЕЕ ПРИЛОЖЕНИЯ


проф. О.М. Касим-Заде

1/2 года

1. Основные понятия. Графы неориентированные и ориентированные. Способы задания графов. Матрицы смежности и инцидентности графа. Понятие изоморфизма графов. Понятия пути, цепи и цикла в графе. Связность графов. Компоненты связности графа.

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

3. Задача о построении кратчайшего остовного дерева в связном графе со взвешенными ребрами. Алгоритм построения кратчайших остовных деревьев.

4. Основные свойства матриц смежности и инцидентности графа. Связь между матрицами смежности и инцидентности. Матричная теорема о деревьях.

5. Число остовных деревьев графа. Подсчет числа деревьев на n нумерованных вершинах. Формула Кэли.

6. Вершинные раскраски графов. Хроматическое число. Бихроматические (двудольные) графы и их характеризация.

7. Простейшая оценка хроматического числа графа (хроматическое число не превосходит наибольшей из степеней вершин графа, увеличенной на единицу). Теорема Нордхауза-Гаддума.

8. Теорема Брукса.

9. Планарные графы. Формула Эйлера для плоских графов. Неравенства между числом вершин и ребер планарного графа. Непланарность графов и . Теорема о существовании в планарном графе по меньшей мере двух вершин степени не выше 5. 

10. Вершинные раскраски планарных графов. Проблема четырех красок. Теорема о пяти красках для планарных графов.

11. Проблема Заранкевича. Числа Заранкевича (для графов) и (для двудольных графов и булевых матриц). Верхняя оценка числа . Нижняя оценка числа Заранкевича на основе конструкции конечной аффинной плоскости над полем классов вычетов по простому модулю. Оценки числа .

12. Вентильные схемы. Матрица проводимости вентильной схемы. Сложность вентильной схемы. Теорема о минимальных вентильных схемах, реализующих булевы матрицы без "единичных" подматриц размера (2,2). Нижняя оценка вида для сложности вентильных схем, реализующих булевы матрицы, связанные с конечной аффинной плоскостью.

Литература


1.
 Берж К. Теория графов и ее применения. М., ИЛ, 1962. 


2. Зыков А.А. Теория конечных графов, I. Новосибирск, Наука, 1969. 

3. Кристофидес К. Теория графов (алгоритмический подход). М., Мир, 1978. 

4. Оре О. Теория графов. М., Наука, 1968. 

5. Свами М., Тхуласираман К. Графы, цепи и алгоритмы. М., Мир, 1984. 

6. Харари Ф. Теория графов. М., Мир, 1973. 

7. Эрдеш П., Спенсер Дж. Вероятностные методы в комбинаторике. М., Мир, 1976. 

8. Уилсон Р. Введение в теорию графов. М., Мир, 1977. 

9. Нечипорук Э.И. Об одной булевской матрице. В сб.: “Проблемы кибернетики”, вып. 21. С. 237-240. М., Наука, 1969. 

Похожие:

Теория графов и ее приложения iconПрограмма дисциплины «теория графов»
Таким образом, теория графов стала существенной частью математического аппарата кибернетики, языком дискретной математики. В значительной...
Теория графов и ее приложения iconПрограмма наименование дисциплины: Теория конечных графов
Основной целью освоения дисциплины является изучение классической теории конечных графов, а также применение методов теории конечных...
Теория графов и ее приложения iconРабочая программа дисциплины (модуля) Теория графов Направление подготовки
Целями освоения дисциплины (модуля) «Теория графов» являются получение теоретических знаний по основам теории графов
Теория графов и ее приложения iconПрограмма наименование дисциплины: Теория конечных графов
Цели и задачи дисциплины: Основной целью освоения дисциплины является изучение классической теории конечных графов, а также применение...
Теория графов и ее приложения iconРабочая программа дисциплины "Теория конечных графов и ее приложения" Направление подготовки 010300. 62 «фиит»
Графы ориентированные и неориентированные. Изоморфизм графов. Маршруты, цепи, циклы. Деревья. Помеченные графы. Плоские и планарные...
Теория графов и ее приложения iconНаучная работа по теме: 1 глава 1 4 теория графов 4 Эйлеровы графы 7 Задача о мостах, Леонард Эйлер и теория графов 8
Как это сделать? Я стала искать пути решения, и оказалось, что это можно сделать с помощью графов. Раньше понятием «граф» я встречалась...
Теория графов и ее приложения iconДисциплины "Теория конечных графов и ее приложения"
Цели и задачи дисциплины: формирование навыков логического мышления; ознакомление с основами теоретических знаний по графам и их...
Теория графов и ее приложения iconП78 П78 Программные системы: теория и приложения
П78 Программные системы: теория и приложения. Труды международной конференции «Программные системы: теория и приложения», ипс ран,...
Теория графов и ее приложения iconПрограмма наименование дисциплины: Теория графов Рекомендуется для направления (ий) подготовки (специальности (ей))
Курс «Теория графов» является дисциплиной по выбору в бакалаврской программе направления «Прикладная математика и информатика». Курс...
Теория графов и ее приложения iconБилеты по Дискретной математике «Теория Графов»
Понятие графа (орграфа). Смежность и инцидентность в графе. Классы (типы) графов
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org