Методические указания к курсу «Элементы дискретной математики и биоинформатики» (стр. 2 из 8)

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

Краткое содержание раздела:

Высказывания. Примеры. Логические связки. Формулы логики высказываний. Примеры. Логическая эквивалентность. Свойства логических операций. Тавтологии или законы логики высказываний. Логический вывод. Доказательство теорем.

Литература: [16] гл. 3, стр. 61-81, [5] стр. 65-85.

Задачи: [6] №№ 601 (1,4,7,10,13,16), 602 (1,3), 604 (1,3,5), 612 (1,3,4).

Пример решения задач:

В одной местности расположены два города И и Л. Жители И всегда говорят правду, а жители Л всегда лгут. Как, попав в один из этих городов, узнать у первого встречного название города?

Решение. Поскольку ответ встречного зависит от его правдивости, обозначим х=«Ты правдив». Нас интересует название города, поэтому обозначим у=«Это город И». Теперь из высказываний х и у сконструируем высказывание р так, что услышав от встречного ответ «Да» на вопрос «Верно ли, что р=И?» мы поймем, что находимся в И. Составим для р следующую таблицу истинности:

		Слышимый ответ	Понимаемый ответ	Р
Л	Л	нет	да	И
Л	И	да	нет	Л
И	Л	нет	нет	Л
И	И	да	Да	И

Таким образом,

. В переводе на русский язык соответсвующий вопрос таков: «Верно ли, что ты лжец и это Л или ты правдив и это И?». Проще его можно сформулировать так: «Ты житель этого города?».

4. Теория графов.

Лекции 5-15.

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

Цель данного раздела – представить основное, устоявшееся ядро современной теории графов, акцентируя внимание на биологических приложениях. Для более полного охвата разделов современной теории графов, некоторые факты приводятся без доказательств (например, критерий планарности графа – теорема Понтрягина-Куратовского или теорема Хивуда о 5-раскрашиваемости планарного графа).

Краткое содержание раздела:

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

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

Ориентированные графы. Турниры. Ормаршруты, орцепи, орциклы (контуры). Орлемма о рукопожатиях.

Матрицы, ассоциированные с графами: матрица смежности, матрица инцидентности. Их свойства.

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

Эйлеровы графы, их свойства.

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

Укладки графов. Планарные графы. Укладка графа в трехмерном пространстве. Эквивалентность планарности и укладываемости графа на сфере. Формула Эйлера для плоских графов. Связь числа вершин, ребер и граней выпуклых многогранников в трехмерном евклидовом пространстве. Непланарность графов К_3,3 и К₅. Теорема Понтрягина-Куратовского.

Раскраски графов. Хроматические числа. Теорема Кенига о 2-хроматичности обыкновенного графа. Теорема Хивуда о 5-раскрашиваемости любого планарного графа.

Литература: [1] гл. 1-3, 5-6, [7].

Задачи: [12] №№ 1, 4, 17, 18, 19, 37, 38, 39, 46, 54, 55, 56, 58, 59, 60, 63, 64, 74, 77, 94, 95.

Пример решения задач:

5.1. В соревновании по круговой системе с двенадцатью участниками провели все встречи. Сколько встреч было сыграно?

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

. Таким образом, было сыграно 66 встреч.

5.2. Рассмотрим граф

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

Степенью (валентностью) вершины

неориентированного графа называется число ребер , инцидентных данной вершине. Таблица степеней вершин данного графа имеет вид:

	3	3	3	4	2	3	2

Матрицей смежности

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

Матрица смежности для данного графа имеет вид:

.

Матрицей инцидентности

неориентированного графа с вершинами и ребрами называется матрица размерности , элементы которой определяются следующим образом:

В графе

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