Задача по темам контрольной работы (допускаются освобождения от этой задачи, если вы получили не менее 4,5 за контрольную)



Скачать 58.39 Kb.
Дата30.12.2012
Размер58.39 Kb.
ТипЗадача

15.05.2008

Уважаемые студенты!
Высылаю список вопросов к экзамену по теории графов и

давно обещанную историю проблемы 4 красок (все в одном файле).

На экзамене (если ваши лекции окажутся пригодными для изучения

курса теории графов) вам нужно будет ответить на 3 вопроса билета,

1 из которых - теория (один из 36 неподчеркнутых вопросов из 43

вопросов прилагаемого списка),

2-й - задача по темам контрольной работы (допускаются освобождения

от этой задачи, если вы получили не менее 4,5 за контрольную),

3-й - другая задача (планарные графы, раскраска графов, орграфы и алгоритмы

на графах. В последнем случае указывается один из 7 подчеркнутых вопросов списка).

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

ваше умение решать задачи с применением этих алгоритмов, а не зазубривание

теории.
Желаю успешно сдать сессию!
И.С. Павлов

ВОПРОСЫ К ЭКЗАМЕНУ ПО ТЕОРИИ ГРАФОВ (РФ, 2-й семестр)


  1. Краткие сведения из истории возникновения теории графов. Области применения теории графов.

  2. Определение графа. Виды неориентированных графов.

  3. Способы задания неориентированных графов.

  4. Дополнение к графу. Подграфы и их виды. Операции над графами.

  5. Маршруты, цепи и циклы в графе. Цикломатическое число. Свойства маршрутов и циклов.

  6. Степени вершин. Основная теорема теории графов и ее следствие.

  7. Связность графов. Матрица связности (достижимости). Критерии связности графа.

  8. Теорема об оценке числа ребер графа через число вершин и число компонент связности.

  9. Мосты и разделяющие вершины. Признаки моста. Вершинная и реберная связности. N-связные графы. Следствие из теоремы об оценке числа ребер графа через число вершин и число компонент связности.

  10. Расстояния в графе. Диаметр, радиус и центр графа.

  11. Изоморфизм графов. Алгоритм решения задач на определение изоморфных графов.

  12. Теоремы о количестве графов с р вершинами и с р вершинами и q ребрами.

  13. Теоремы о количестве ребер в связных графах с циклами и без циклов.

  14. Неориентированные (свободные) деревья. Кодирование деревьев.

  15. Основные свойства свободных деревьев.

  16. Двудольные графы. Критерий двудольности графа. k-дольные графы.

  17. Эйлеровы и полуэйлеровы графы. Критерий существования в графе эйлеровой цепи.

  18. Леммы для доказательства теоремы Эйлера об эйлеровых графах (критерия эйлеровости графа).

  19. Теорема Эйлера об эйлеровых графах (критерий эйлеровости графа). Решение задачи о кенигсбергских мостах.

  20. Теорема об оценке числа эйлеровых графов.

  21. Гамильтоновы графы.
    Теорема об оценке числа гамильтоновых графов (без доказательства). Задача коммивояжера. Сравнение задач отыскания эйлеровых и гамильтоновых циклов.

  22. Теорема Дирака (достаточное условие гамильтоновости графа).

  23. Планарные графы. Гомеоморфизм графов. Теорема Понтрягина-Куратовского (без доказательства). Теорема об оценке числа планарных графов (без доказательства).

  24. Теорема о количестве граней связного планарного графа.

  25. Следствия из теоремы о количестве граней связного планарного графа.

  26. Вершинная и реберная раскраски графов. Хроматическое число и хроматический индекс, их оценки.

  27. Проблема четырех красок. История ее возникновения и решения.

  28. Теорема о 5 красках.

  29. Ориентированные графы. Виды ориентированных графов. Связь с бинарными отношениями.

  30. Способы задания ориентированных графов.

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

  32. Критерий существования контура в орграфе.

  33. Компоненты сильной связности орграфа и их свойства. Конденсация орграфа. Теорема о вычислении матриц достижимости и сильной связности (без доказательства).

  34. Алгоритм выделения компонент сильной связности в орграфе.

  35. Ориентированные, упорядоченные и бинарные деревья. Их сравнительный анализ и области применения.

  36. Свойства ориентированных деревьев.

  37. Алгоритм построения покрывающего остова в ненагруженном графе.

  38. Алгоритм Тэрри поиска маршрута в связном графе, соединяющего 2 заданные вершины.

  39. Алгоритм выделения эйлерова цикла в связном мультиграфе с четными степенями вершин и его модификация на случай выделения эйлеровой цепи в связном мультиграфе с двумя нечетными степенями вершин.

  40. Алгоритмы поиска в ширину и глубину. Алгоритм поиска минимального маршрута в ненагруженном графе.

  41. Обход графа. Теорема о поисках в ширину и глубину.

  42. Задача о нахождении минимального маршрута в нагруженном орграфе. Алгоритм Форда-Беллмана.

  43. Построение остова минимального веса. Алгоритмы Дейкстры и Краскала.



Исторически раскрасочная терминология пришла в теорию графов из задачи о раскраске стран на карте: “Сколько цветов требуется для раскраски различных стран на карте так, чтобы каждые 2 смежные страны были окрашены по-разному?” Эта задача сводится к проблеме определения максимального хроматического числа плоских графов. По одним сведениям, об этой задаче знал еще в 1840 г. немецкий математик Мёбиус. По другим же данным она возникла в 1852 г., когда некий Франсис Гатри спросил своего брата Фредерика, в то время студента-математика в Кембридже, верно ли, что каждую карту можно окрасить в четыре цвета так, чтобы смежные страны имели разные цвета. Эта задача, получившая название проблемы (гипотезы) четырех красок, была впервые предложена вниманию общественности в выступлении Кэли на заседании Лондонского математического общества в 1878 г.

Теорема о 4 красках. Всякий плоский граф можно раскрасить четырьмя красками.

Годом позже Кемпе опубликовал неправильное доказательство, которое было в 1890 г. переделано Хивудом в доказательство теоремы о пяти красках.

Теорема о пяти красках. Всякий плоский граф можно раскрасить пятью красками.

В 1880 г. Тейт анонсировал “дальнейшие доказательства” гипотезы четырех красок, которые так и остались нематериализованными.

В 1941 г. Брукс улучшил оценку для хроматического числа некоторых графов.

Теорема Брукса. Если связный граф G не является ни полным графом, ни нечетным циклом, то .

В середине ХХ века при попытке решить проблему 4 красок были доказаны следующие теоремы.

Теорема Татта (1956 г.). Каждый 4-связный планарный граф имеет гамильтонов цикл.

Теорема Грёцша (1959 г.). Каждый плоский граф, не содержащий треугольника, можно раскрасить тремя красками.

Тем не менее доказать теорему о 4 красках не могли в течение 125 лет после ее первоначальной формулировки и в течение 99 лет после ее формулировки для научной общественности.

Первое общепризнанное доказательство теоремы о четырех красках было опубликовано Аппелем и Хакеном в 1977 г. Доказательство основано на идеях, восходящих еще к статье Кемпе и далеко продвинутых Биркгофом и Хеешем. Говоря очень приблизительно, доказательство сводится, во-первых, к утверждению, что каждая плоская триангуляция (т.е. плоский связный граф, каждая грань которого, включая и внешнюю, ограничена циклом длины 3) должна содержать, по крайней мере, одну из 1482 «неизбежных конфигураций» (конфигурация – это связный подграф плоского графа; более подробно см. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженеров. М.: Энергоатомиздат, 1988. 2-е изд.). На втором этапе с помощью компьютера показывается, что каждая из этих конфигураций «редуцируема», т.е. что любая плоская триангуляция, содержащая такую конфигурацию, может быть 4-раскрашена, исходя из 4-раскрасок меньших триангуляций. Вместе взятые эти два шага составляют индуктивное доказательство того, что все плоские триангуляции, а следовательно, и все плоские графы можно раскрасить в четыре цвета.

Доказательство Аппеля и Хакена не было обойдено критикой, и не только из-за использования ими компьютера. Авторы ответили 741-страничной алгоритмической версией доказательства, которая учитывает различные критические замечания и исправляет множество ошибок (например, ими добавлено еще 450 конфигураций к «неизбежному» списку): Appel K., Hakeп W. Every Planar Map is Four Colorable. Providence: Amer. Math. Soc. 1989. (Contemporary Mathematics; 98). В результате, компьютер, проработав 1500 часов, показал, что из 1932 конфигураций 1931 редуцируема. Последнюю конфигурацию исследовали вручную, применив более тонкие методы редукции, не заложенные в программу. Проверка показала, что и эта конфигурация редуцируема. Так проблема четырех красок была решена.

Гораздо более короткое доказательство, которое основано на тех же идеях (и, в частности, использует компьютер таким же образом), но более доступно проверке как в текстовой, так и в компьютерной части, дано в статье: Robertson N., Sanders D., Seymour P.D., Thomas H. The four-colour theorem // J. Combin. Theory. Ser. B. 1997. V. 70. P. 2-44.

Похожие:

Задача по темам контрольной работы (допускаются освобождения от этой задачи, если вы получили не менее 4,5 за контрольную) iconОбщие методические указания по выполнению контрольных работ контрольные работы должны быть представлены до экзаменационной сессии. Номера задач, которые студент должен включить в свою контрольную работу, определяются по таблицам
Приведены задачи по физике по темам «Электростатика» и «Постоянный ток». Задания предназначены для обеспечения самостоятельной работы...
Задача по темам контрольной работы (допускаются освобождения от этой задачи, если вы получили не менее 4,5 за контрольную) iconРуководство к выполнению контрольной работы по дисциплине «Современный русский язык: Словообразование» для студентов заочного обучения
В осеннем семестре 2007-2008 учебного года студент должен выполнить 1 контрольную работу по словообразованию
Задача по темам контрольной работы (допускаются освобождения от этой задачи, если вы получили не менее 4,5 за контрольную) iconЗадания для защиты контрольной работы по темам: «Комплексные числа»
Исходя из определения равенства множеств и операций над множествами, доказать тождество
Задача по темам контрольной работы (допускаются освобождения от этой задачи, если вы получили не менее 4,5 за контрольную) iconА. В. Хейло, с. Старомарьевка, Ставропольский кр
В следующие контрольные работы по темам я включил и задания с кратким ответом, и задания с развёрнутым ответом. Результаты выполнения...
Задача по темам контрольной работы (допускаются освобождения от этой задачи, если вы получили не менее 4,5 за контрольную) iconКонтрольная работа №2 по дисциплине «Цифровые системы автоматического управления» Вариант №14 Студент гр. 511-1
Для выполнения этой контрольной работы необходимо решить четыре задачи, посвященные прохождения сигнала через линейную дискретную...
Задача по темам контрольной работы (допускаются освобождения от этой задачи, если вы получили не менее 4,5 за контрольную) iconЗадача заочной математической олимпиады «Авангард» Разные задачи. Мои собственные задачи Комбинаторика и русский язык
«Правило умножения для комбинаторных задач». Мне очень понравилось решать задачи на перебор вариантов. На занятиях кружка по этой...
Задача по темам контрольной работы (допускаются освобождения от этой задачи, если вы получили не менее 4,5 за контрольную) iconСтуденты выполняют одну контрольную работу по аналитической химии (количественный анализ). Выбор номера варианта контрольных заданий в контрольной работе осуществляется по последней цифре в номере зачетной книжки
Например, если номер в зачетной книжке 2178, то вам следует выполнять задания под номерами 8, 18, 28 и т д
Задача по темам контрольной работы (допускаются освобождения от этой задачи, если вы получили не менее 4,5 за контрольную) iconЗадания для защиты контрольной работы по темам: «Ряды», «Криволинейные и поверхностные интегралы», «Элементы теории векторных полей»
Проверить, является ли векторное поле потенциальным. В случае потенциальности поля найти его потенциал
Задача по темам контрольной работы (допускаются освобождения от этой задачи, если вы получили не менее 4,5 за контрольную) iconЗадания контрольной работы №1 по предмету Линейная алгебра
Для допуска к экзамену каждый студент должен успешно выполнить свой вариант контрольной работы
Задача по темам контрольной работы (допускаются освобождения от этой задачи, если вы получили не менее 4,5 за контрольную) iconКонтрольная работа №1. 2 Задание 2 Решение 2 Задача №1 2 Задача №2. 3 Задача №3. 5 Контрольная работа №2. 10 Задани
Необходимо выполнить контрольную работу, состоящую из трех задач. Тематика ее связана с решением конкретных производственных задач,...
Разместите кнопку на своём сайте:
ru.convdocs.org


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