Для студентов ГУУ по предмету ДругиеО правильных раскрасках графовО правильных раскрасках графов
2024-07-172024-07-17СтудИзба
Курсовая работа: О правильных раскрасках графов
Описание
Содержание
В своей статье [1] Карпов исследует правильные рёберные 3-раскраски кубических графов (все рёбра покрашены в три цвета, из каждой вершины выходит три ребра, эти три ребра попарно разноцветные). Последняя теорема в ней посвящена оценке количества правильных рёберных 3-раскрасок мультиграфа G, обозначаемого как χ′3(G): утверждается, что для любого связного кубического мультиграфа G с 2n вершинами (нечётным число вершин быть не может, так как иначе сумма степеней окажется нечётной) выполнено χ′3(G) 6 3 · 2N, а если в G не более одной пары кратных рёбер, то χ′3(G) 6 9 · 2N−2. Отмечается, что первая оценка точна, однако пример содержит n пар кратных рёбер; вторая же оценка, вероятно, не точна.
В этой работе мы дополним результаты статьи [1]: а именно, докажем, что для выполнения равенства в первой оценке достаточно всего лишь двух пар кратных рёбер; улучшим вторую оценку и докажем, что в связном кубическом графе G на 2n вершинах χ′3(G) 6 2N + 8 при чётном n и χ′3(G) 6 2N+ 4 при нечётном n, причём при n > 3 эти оценки достигаются ровно на одном графе.
Отметим, что мы будем использовать термин граф лишь в случ ае, если отсут-ствуют кратные рёбра и петли. Если они разрешены, вместо этого мы будем говорить мультиграф. Для удобства мы будем правильные рёберные 3- раскраски называть просто раскрасками.
Определение 2.1. Пусть n ∈ N.
n-лента граф на множестве вершин{AI}I∈{1,2,...,N} ∪ {BI}I∈{1,2,...,N} с 3n − 2рёб- рами: путями A1A2 . . . AN и B1B2 . . . BN, а также паросочетанием A1B1, A2B2, . . . ,
ANBN.
n-цилиндр это n-лента, к которой добавили рёбра ANA1, BNB1. Другими сло-вами, это два цикла A1A2 . . . AN и B1B2, . . . BN, в котором соответствующие вершины соединены паросочетанием.
n-лента Мёбиуса это n-лента, к которой добавили рёбра ANB1 и BNA1. Дру-гими словами, это гамильтонов цикл A1A2 . . . ANB1B2 . . . BN, в котором провели все
Следующее утверждение очевидно и даже не нуждается в доказательстве.
| 1. | Введение | 3 | |
| 2. | Лента, цилиндр, лента Мёбиуса | 3 | |
| 3. | Точная оценка | 8 | |
| 3.1. | Вспомогательныеутверждения. . . . . . . . . . . . . . . . . . . . . . . | 8 | |
| 3.2. | Основнойрезультат ............................. | 9 | |
| Приложение A. База индукции | 17 | ||
| Приложение B. Точность основной теоремы | 20 | ||
| Список литературы | 21 | ||
| §1. Введение | 3 |
- Введение
В своей статье [1] Карпов исследует правильные рёберные 3-раскраски кубических графов (все рёбра покрашены в три цвета, из каждой вершины выходит три ребра, эти три ребра попарно разноцветные). Последняя теорема в ней посвящена оценке количества правильных рёберных 3-раскрасок мультиграфа G, обозначаемого как χ′3(G): утверждается, что для любого связного кубического мультиграфа G с 2n вершинами (нечётным число вершин быть не может, так как иначе сумма степеней окажется нечётной) выполнено χ′3(G) 6 3 · 2N, а если в G не более одной пары кратных рёбер, то χ′3(G) 6 9 · 2N−2. Отмечается, что первая оценка точна, однако пример содержит n пар кратных рёбер; вторая же оценка, вероятно, не точна.
В этой работе мы дополним результаты статьи [1]: а именно, докажем, что для выполнения равенства в первой оценке достаточно всего лишь двух пар кратных рёбер; улучшим вторую оценку и докажем, что в связном кубическом графе G на 2n вершинах χ′3(G) 6 2N + 8 при чётном n и χ′3(G) 6 2N+ 4 при нечётном n, причём при n > 3 эти оценки достигаются ровно на одном графе.
Отметим, что мы будем использовать термин граф лишь в случ ае, если отсут-ствуют кратные рёбра и петли. Если они разрешены, вместо этого мы будем говорить мультиграф. Для удобства мы будем правильные рёберные 3- раскраски называть просто раскрасками.
- Лента, цилиндр, лента Мёбиуса
Определение 2.1. Пусть n ∈ N.
n-лента граф на множестве вершин{AI}I∈{1,2,...,N} ∪ {BI}I∈{1,2,...,N} с 3n − 2рёб- рами: путями A1A2 . . . AN и B1B2 . . . BN, а также паросочетанием A1B1, A2B2, . . . ,
ANBN.
n-цилиндр это n-лента, к которой добавили рёбра ANA1, BNB1. Другими сло-вами, это два цикла A1A2 . . . AN и B1B2, . . . BN, в котором соответствующие вершины соединены паросочетанием.
n-лента Мёбиуса это n-лента, к которой добавили рёбра ANB1 и BNA1. Дру-гими словами, это гамильтонов цикл A1A2 . . . ANB1B2 . . . BN, в котором провели все
- главных диагоналей AIBI.
Следующее утверждение очевидно и даже не нуждается в доказательстве.
Характеристики курсовой работы
ГУУСписок файлов
О правильных раскрасках графов.doc
Tortuga
17 июля 2024 в 20:43
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
