- •Содержание
- •Введение
- •Часть 1. Элементы теории множеств и отношений § 1. Понятие множества. Операции над множествами
- •Примеры
- •Операции над множествами
- •Основные тождества алгебры множеств
- •Упражнения
- •§ 2. Декартово произведение двух или нескольких множеств. Понятие отношения. Бинарные отношения
- •Упражнения
- •§ 3. Специальные бинарные отношения. Отношения эквивалентности
- •Упражнения
- •§ 4. Отношения порядка
- •Упражнения
- •§ 5. Функциональные отношения (отображения). Виды отображений
- •Виды отображений:
- •Упражнения
- •Часть 2. Теория графов
- •§ 1. Основные понятия теории графов
- •Способы задания графов. Матричное задание графов.
- •Свойства матриц смежности и инцидентности
- •Упражнения
- •§ Б 2. Булевы матрицы
- •Дизъюнкция (конъюкция)
- •§ 3. Связность графа. Компоненты связности. Матрица связности
- •Выделение компонент связности
- •Алгоритм выделения компонент сильной связности
- •Упражнения
- •§ 4. Полные графы. Двудольные графы. Однородные и реберные графы
- •Упражнения
- •§ 5. Поиск путей (маршрутов) с минимальным числом дуг (ребер)
- •Упражнения
- •§ 6. Расстояние в графах
- •Упражнения
- •§ 7. Нагруженные графы. Расстояния в нагруженном графе
- •Нахождение минимального пути в нагруженном орграфе
- •Алгоритм Форда-Беллмана нахождения минимального пути в нагруженном орграфе из v1 в vi1 (i1≠1)
- •Упражнения
- •§ 8. Эйлеровы цепи и циклы в графах. Эйлеровы графы. Гамильтоновы цепи и циклы в графах. Гамильтоновы графы
- •Упражнения
- •§ 9. Деревья. Остов графа. Цикловой базис графа
- •Алгоритм нахождения кратчайшего остова в нагруженном графе
- •Упражнения
- •§ 10. Раскраска графов. Планарные графы Раскраска вершин графа
- •Одноцветные классы образуют независимые множества вершин.
- •Существуют и приближенные алгоритмы раскрашивания:
- •Упражнения
- •Варианты контрольных работ Часть 1. Элементы теории множеств и отношений Вариант № 1.
- •Вариант № 2.
- •Вариант № 3.
- •Вариант № 4.
- •Вариант № 5.
- •Вариант № 6.
- •Часть 2. Теория графов Вариант № 1.
- •Вариант № 2.
- •Вариант № 3.
- •Вариант № 4.
- •Вариант № 5.
- •Вариант № 6.
- •Ответы Часть 1
- •Часть 2
- •Тест по теории множеств и отношений
- •Тест по теории графов
- •Библиографический список
- •Любовь Васильевна Архипова Елена Сергеевна Дернович
- •Дискретная математика
Тест по теории графов
1. Дан граф G:
Цикломатическое число графа G равно
а) 2; |
б) 3; |
в) 0; |
г) 4. |
2. Степень каждой вершины графа Е4 равна:
а) 4; |
б) 3; |
в) 16; |
г) 8; |
3. В полном графе К8 диаметр и радиус равны:
а) 1; |
б) 2; |
в) 8; |
г) 4. |
4. Для того, чтобы граф обладал эйлеровым циклом, необходимо и достаточно, чтобы:
а) степени всех вершин были нечетными
б) степени ровно двух вершин были четными
в) степени всех вершин были четными
г) степени ровно двух вершин были нечетными
5. Матрица смежности реберного графа вычисляется по формуле:
а) А(GР)=Вт(G)´В(G) – sE; б) А(GР)=В(G)´Вт(G) – sE; |
в) А(GР)=В(G)´Вт(G) – 2E; г) А(GР)=Вт(G)´В(G) – 2E. |
6. Если в алгоритме фронта волны vjÎFWk(vi) (k£n-1, n – количество вершин орграфа), то
а) вершина vj достижима из вершины vi
б) вершина vj не достижима из вершины vi
в) вершина vi достижима из вершины vj
г) вершина vi не достижима из вершины vj
7. У графа К7 хроматическое число c(К7) равно:
а) 1; |
б) 3; |
в) 4; |
г) 7; |
8. Дан граф G:
Количество компонент связности графа G
а) 2; |
б) 1; |
в) 4; |
г) 5; |
9. Матрица достижимости орграфа D обозначается:
а) T(D); |
б) S(D); |
в) B(D); |
г) D(D). |
10. Формула Эйлера для планарного графа имеет вид:
а) n + m - г = 2; |
б) n - m + г = 2; |
в) n + m + г = 2; |
г) n - m - г = 2; |
11. Длина минимального пути в нагруженном орграфе среди всех путей из v1 в v6, содержащих не более 4 дуг, обозначается:
а) ; |
б) l6,4; |
в) ; |
г) l4,6. |
12. Количество циклов в любом дереве D:
а) 1; |
б) 0; |
в) 2; |
г) 3; |
13. Однородный граф G имеет 15 ребер, степень каждой вершины равна 5, тогда количество вершин графа G:
а) 15 |
б) 6 |
в) 20 |
г) 10 |
14. Число полных трехвершинных подграфов в полном двудольном графе К6,7 равно
а) 6; |
б) 7; |
в) 13; |
г) 0. |
15. Дан граф:
Степень вершины 1 равна
а) 1; |
б) 2; |
в) 3; |
г) 4; |
16. Цикломатическое число графа равно
а) количеству компонент связности
б) размерности пространства базисов циклов графа
в) количеству циклов в графе
г) количеству ребер в цикле
Библиографический список
-
Акимов О. Е. Дискретная математика / О. Е. Акимов. – М, 2001.
-
Березина Л. Ю. Графы и их применение / Л. Ю. Березина. – М., 1979.
-
Гладкий А. В. Математическая логика / А. В. Гладкий. – М.,1998.
-
Гаврилов Г. П. Сборник задач по дискретной математике / Г. П. Гаврилов, А. А. Сапоженко. – М., 1977.
-
Евстегнеев В. А. Теория графов. Алгоритмы обработки деревьев / В. А. Евстегнеев. – Новосибирск, 1994.
-
Ершов Ю. Л. Математическая логика / Ю. Л. Ершов, Е. А. Палютин. – М., 1973.
-
Калужнин Л. А. Элементы теории множеств и математической логики в школьном курсе математики / Л. А. Калужнин. – М., 1978 .
-
Кузнецов О. П. Дискретная математика для инженера / О. П. Кузнецов. – М., 1988.
-
Лавров И. А. Задачи по теории множеств, математической логике и теории алгоритмов / И. А. Лавров, Л. Л. Максимова. – М.,1984.
-
Москинова Г. И. Дискретная математика / Г. И. Москинова. – М., 2000.
-
Нефедов В. Н. Курс дискретной математики / В. Н. Нефедов, В. А. Осипова. – М., 1992.
-
Новиков Ф. А. Дискретная математика для программистов / Ф. А. Новиков. – СПб.: Питер, 2000.
-
Оре О. Теория графов / О. Оре. – М., 1980.
-
Столяр А. А. Логическое введение в математику / А. А. Столяр. – Минск, 1971.
-
Судоплатов С. В. Элементы дискретной математики / С. В. Судоплатов, Е. В. Овчинникова. – М., 2002.
-
Эдельман С. Л. Математическая логика / С. Л. Эдельман. – М., 1975.
-
Яблонский С. В. Введение в дискретную математику / С. В. Яблонский. – М., 2002.
Учебное издание