4.7. Упражнения Свойства графов
Все графы предполагаются простыми. Графы называются изоморфными,
если существует биекция fмежду множествами их вершин, такая что
{u,v}ребро{f(u),f(v)}– ребро.
1. Доказать, что граф имеет четное число вершин с нечетными степенями.
2. При встрече студентов состоялось 15 рукопожатий, трое человек сделали по 4 рукопожатия, а другие – по 3. Сколько было студентов.
3. Может ли существовать группа из 23 человек, каждый из которых знаком с пятью другими?
4. В соревнованиях по шахматам по круговой системе участвуют 5 человек. Все, кроме Иванова и Петрова, сыграли различное число партий. Сколько партий сыграли Иванов и Петров?
5. Можно ли нарисовать без отрыва карандаша граф K6, у которого удалено одно ребро.
6. Найти число попарно неизоморфных графов, у которых 2 вершины имеют степень 2, 2 вершины имеют степень 3, и 2 вершины имеют степень 4. Остальные вершины имеют степень 0.
7. Найти число попарно неизоморфных графов, у которых 3 вершины имеют степень 2, 3 вершины имеют степень 3, и 3 вершины имеют степень 4. Остальные вершины имеют степень 0.
8. Доказать, что в простом графе, имеющем не меньше двух вершин, всегда найдутся две вершины одинаковой степени.
9. Какие из графов, приведенных на рис. 4.12 , изоморфны?
Рис. 4.12. Примеры графов
10. Какие из графов, приведенных на рис. 4.13 , изоморфны?
Рис. 4.13. Примеры графов
11. Найти число всех попарно неизоморфных графов, имеющих 4 вершины. Нарисовать эти графы.
Ответ: существует 11 неизоморфных графов (рис.4.14).
Рис. 4.14. Графы, имеющие 4 вершины
12. Кратчайший путь, соединяющий вершины uиvв графе, называетсягеодезическим путеммежду вершинами. Его длина обозначаетсяd(u,v). ДиаметромD()графа называется длина самого длинного геодезического пути в этом графе, т.е.D()=max{d(u,v) :u,v V}. Найти диаметр графа, приведенного на рис. 4.15. Найти диаметр графаK5.
Рис. 4.15. Пример графа
13. Матрица смежности состоит из коэффициентов aij=1вершиныiиjсмежны.
(1) Построить матрицы смежности для графов K3иK4;
(2) Доказать, что сумма коэффициентов i-й строки матрицы смежности равна степениi-й вершины;
(3) Построить матрицу смежности графа, состоящего из вершин и ребер куба.
(4) С помощью матрицы смежности построить матрицу, коэффициентами которой является количества путей длины 2 из вершины iв вершинуj.
(5) Как связаны след матрицы A3с числом треугольников в графе?
14. Циклы {z1, z2, , zn}называютсянезависимыми, если z1z2 zn Доказать, что у связного графа максимальное число независимых циклов равноq-p+1.
15. Сколько компонент связности имеет лес, содержащий 76 вершин и 53 ребра?
16. Доказать, что среди 6 человек найдется тройка знакомых, или тройка незнакомых людей.
17. В компании, состоящей из пяти студентов, среди любых трех найдутся два знакомых и два незнакомых. Доказать, что компанию можно рассадить за круглым столом таким образом, что любые два соседа будут знакомы.
- А.А. Хусаинов н.Н. Михайлова дискретная математика
- Введение
- 1. Множества и отношения
- 1.1. Способы задания множеств
- 1.2. Операции и их свойства
- Предложение. Пусть u – множество. Тогда для любых его подмножеств a, b и c верны равенства:
- 1.3. Решение уравнений с неизвестным множеством
- 1.4. Перечисление подмножеств
- 1.5. Отношения и функции
- Операции над бинарными отношениями. Бинарным отношением между элементами множеств a и b называется произвольное подмножество r ab. Запись aRb (при a a, b b ) означает, что (a,b) r .
- Обозначим IdA через Id. Легко видеть, что имеет место следующее
- Нижняя грань обозначается через . Двойственно, как наименьший элемент множества , определяетсяверхняя грань .
- Лемма 1. Если конечное частично упорядоченное множество (X,) является нижней полурешеткой и имеет наибольший элемент, то оно будет решеткой.
- Теорема 1. Пусть X – конечное множество. Множество отношений эквивалентности на X с отношением включения является решеткой.
- 1.7. Математическое моделирование баз данных
- Определение 1. (1nf) Файл находится в первой нормальной форме, если для него задано некоторое положительное целое число n и последовательность множеств (a1, , An) таких, что
- Определение 2.
- Определение 3. (2nf) Файл с первичным ключом находится во второй нормальной форме, если он находится в первой нормальной форме, и для любого атрибут Ak функционально полно зависит от атрибутов .
- Третья нормальная форма
- 2. Комбинаторика
- 2.1. Размещения
- 2.2. Сочетания
- Теорема 2. Число сочетаний из n по k равно .
- Пример 2. Число неубывающих сюръекций n 1 равно .
- Лемма 1. Пусть - число сочетаний с повторениями изn по k. Тогда равно числу неубывающих функций{1,2, , n-1} {0,1,2, , n}
- Теорема 7. .
- Следствие 1. Равно числу неубывающих функций
- Формула включения и исключения Перечисление элементов объединения подмножеств. Обобщим формулу
- Теорема 1. (Формула включения-исключения)
- Теорема 2.
- 2.4. Разбиения
- Лемма 1. .
- Теорема 1.
- Пример 2. Число s(4,2) равно 7, ибо все разбиения множества {1,2,3,4, 5, 6, 7} на два блока исчерпываются следующими:
- Теорема 2. Имеют место следующие свойства чисел Стирлинга второго рода:
- Теорема 3. ,n 0 .
- 2.5. Упражнения
- Упорядоченные разбиения
- Формула включения и исключения
- Неупорядоченные разбиения
- 3. Производящие функции
- 3.1. Свойства производящих функций
- 3.2. Разбиения чисел
- Лемма 1. Число разбиений p(n) равно количеству решений
- Замечание. Частное от деления любых двух многочленов является производящей функцией некоторой возвратной последовательности, порядок которой равен степени знаменателя.
- Получаем . Следующий шаг – разложение знаменателяK(X) в произведение (1 1x) (1 2x). В данном случае это можно сделать с помощью формулы Виеты. Поскольку имеют место равенства
- 3.5. Упражнения Свойства производящих функций
- Решение рекуррентных уравнений
- 4.1. Эйлеровы графы
- Теорема 1. Граф является эйлеровым тогда и только тогда, когда нечетную степень имеют не более двух вершин.
- 4.2. Простые графы и их свойства
- Замечание. Теорема Эйлера имеет место и для графов, не являющихся простыми.
- 4.3. Хроматическое число и хроматическая функция графа
- Теорема 1. Следующие свойства графа равносильны
- Теорема 3. Хроматическая функция f (q) конечного графа с n вершинами является многочленом степени не более, чем n.
- Число последовательностей из n-2чисел принадлежащих множеству{1, 2, ∙ ∙ ∙, n}равноnn-2, значит число нумерованных деревьев равноnn-2.
- Для всякого элемента aa слово a есть терм;
- В нормальной форме Бэкуса-Наура определение будет следующим:
- Теорема 1. Числа Каталана равны .
- 4.6. Плоские графы Эйлерова характеристика. Двумерной клеткой мы будем называть часть поверхности, ограниченную некоторым криволинейным многоугольником.
- Графы Куратовского. Далее мы рассмотрим следующие две задачи.
- Следствие 1. Граф k5 не плоский.
- Следствие 2. Граф k3,3 не плоский.
- Лемма 2. Пусть (V,e) – плоский конечный граф. Тогда существует вершина VV такая, что d(V) 5. Здесь d(V) – степень вершины V.
- Теорема 4. Для плоского связного графа существует правильная раскраска вершин в 5 цветов.
- Теорема 5. Пусть p – число вершин, q – число ребер, r – число граней правильного многогранника. Тогда возможен один из следующих случаев, рассмотренных в таблице 4.1.
- 4.7. Упражнения Свойства графов
- Хроматическое число и хроматическая функция графа
- 20.Найти хроматическую функцию графа An , приведенного на рис. 4.16.
- Деревья
- 5. Конечные частично упорядоченные множества
- 5.1. Диаграмма Хассе частично упорядоченного множества
- Пример 1. На рис. 5.1 показана диаграмма Хассе множества p({0,1,2}) подмножеств множества {0,1,2}, упорядоченное отношением .
- 5.2. Функция Мебиуса
- Определение 1. Функцией Мебиуса : XXz называется функция, определенная по формуле
- 5.3. Формула обращения
- 5.5. Упражнения Диаграмма Хассе
- Функция Мебиуса
- Расчетно-графическое задание
- Пример решения задачи 1
- Контрольная работа
- Варианты заданий
- Примеры решения задачи 1
- Варианты заданий
- Пример решения задачи 2
- Варианты заданий
- Пример решения задачи 3
- Варианты заданий
- Пример решения задачи 4
- Варианты заданий
- Пример решения задачи 5
- Варианты заданий
- Пример решения задачи 6
- Варианты заданий
- Пример решения задачи 7
- Экзаменационные вопросы и задачи Вопросы
- Литература
- Содержание