Задачки по теории графов

forester_200

Народ,
Подскажите, пожалуйста, идеи решения следующих задач:
1 типа
В связном неориентированном графе 19 вершин, а его хроматическое число равно 2. Сколько ребер может быть в таком графе? Дайте точную верхнюю и точную нижнюю оценку.
В связном неориентированном графе 21 вершина, а его хроматическое число равно 3. Сколько ребер может быть в таком графе? Дайте точную верхнюю и точную нижнюю оценку.
В неориентированном графе 30 вершин, а его хроматическое число равно 2. Сколько ребер может быть в таком графе? Дайте точную верхнюю и точную нижнюю оценку.
2 типа
Докажите или опровергните следующее утверждение. Существует простой гамильтонов граф из n вершин такой, что его дополнение эйлерово. а) n=30, б) n=31.
Докажите или опровергните следующее утверждение. Существует простой эйлеров граф из n вершин такой, что его дополнение эйлерово. а) n=15, б) n=16.
Докажите или опровергните следующее утверждение. Существует простой гамильтонов граф из n вершин такой, что его дополнение гамильтоново. а) n=4, б) n=6.

stm8853410

В задачах первого типа верхняя оценка получается с помощью теоремы Турана, а нижняя тривиальна (ну например, в пунктах 1 и 3 подходит дерево).
В задачах второго типа ответы да, да, да, нет (чётность нет (не хватает вершин да.
HINT: гамильтонов граф лушче начать строить с цикла (потом можно ещё рёбер добавить а эйлеровость достигается, если есть чётность степеней вершин и связность.

antonata

ну например, в пунктах 1 и 3 подходит дерево
В пункте 3 связности не требуется, так что правильная нижняя оценка там 1. Если ребер меньше - то хроматическое число будет 1, а любой граф из 30 вершин и одного ребра подходит.

gr_nik

В первых трёх задачах:
Про нижние оценки уже написали.
Верхние: понятно, что в раскраске в $k$ цветов между вершинами одного цвета не может быть проведено рёбер. Зато между вершинами разных цветов можно проводить какие угодно рёбра.
Таким образом, в первой задаче имеем двудольный граф, в первой доле $l$ вершин, во второй доле $19-l$ вершин, можно провести между ними все $l(19-l)$ рёбер. Аналогично во второй задаче, только с тремя долями.

forester_200

Ребята, всем большое спасибо. Со всеми задачками разобрался :)
Оставить комментарий
Имя или ник:
Комментарий: