@BMinhoj

Существует ли граф на 9 вершинах, степени которых равны 1, 1, 1, 1, 1, 2, 4, 5, 6?

Правильно ли мое доказательство? Что делать для больших последовательностей? Какой алгоритм док-ва таких задач?
Доказываю следующим образом.
Допустим, что у всех вершин степень равна 0
0 0 0 0 0 0 0 0 0
Тогда чтобы получить вершину со степенью 6 нам нужно добавить ребра
0 0 1 1 1 1 1 1 6
Здесь я соединил последнюю вершину с 3,4,5,6,7,8 вершинами, и у них степень увеличилась на 1
Теперь нам нужно получить вершину со степенью 5
1 1 1 1 1 2 2 5 6
Дальше нам нужно получить вершину со степенью 4
1 1 1 1 2 3 4 5 6
Противоречие
  • Вопрос задан
  • 1893 просмотра
Пригласить эксперта
Ответы на вопрос 2
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Теорема Эрдёша — Галлаи
1. 8 ≥ 6 ≥ 5 ≥ 4 ≥ 2 ≥ 1 ≥ 1 ≥ 1 ≥ 1 ≥ 1
2. 6 + 5 + 4 + 2 + 1 + 1 + 1 + 1 + 1 = 22
Данная последовательность является правильной.
k = 1, 6 ≤ (0 + 8), выполняется,
k = 2, 11 ≤ (2 + 9), выполняется,
k = 3, 15 ≤ (6 + 7), не выполняется.
Значит данная последовательность не является графической, по ней нельзя построить простой граф.
Ответ написан
Alexandroppolus
@Alexandroppolus
кодир
конкретно здесь можно измыслить так:
вершины 4, 5, 6, даже если соединены друг с другом попарно (на что уйдет 6 степеней), всё равно имеют 9 свободных степеней, которые не накрываются остальными вершинами.

но это при условии, что нет кратных ребер (когда ребра А и Б соединены более чем одной вершиной), и петель (ребер А-А). У тебя ведь именно такой кейс?
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы