Слайд 2 Аннотация
Объектом исследования в данной работе является особый класс графов – Цепочки.
![Аннотация Объектом исследования в данной работе является особый класс графов – Цепочки.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/890085/slide-1.jpg)
Вводятся в рассмотрение 2 новых подкласса Цепочек:
граф Гусеница и Цепочка Петерсена, звеньями которых служат цикл с концами в смежных вершинах и Граф Петерсена с концами в несмежных вершинах соответственно.
Находится число минимальных вершинных покрытий указанных классов графов.
Слайд 4 Цель работы – Найти вершинные характеристики Звеньев, основой
которых служат цикл
![Цель работы – Найти вершинные характеристики Звеньев, основой которых служат цикл с](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/890085/slide-3.jpg)
с концами в смежных вершинах и
Граф Петерсена с концами в несмежных вершинах
– Определить число минимальных вершинных
покрытий Графа Гусеницы и Цепочки Петерсена.
Слайд 10Глава 2. Цепочки.
Основной результат
![Глава 2. Цепочки. Основной результат](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/890085/slide-9.jpg)
Слайд 19 Цепочка Петерсена
Определение 4.1 Пусть G(5,2) – граф Петерсена.
Цепочку Ch(n,
![Цепочка Петерсена Определение 4.1 Пусть G(5,2) – граф Петерсена. Цепочку Ch(n, G(5,2),](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/890085/slide-18.jpg)
G(5,2), A,B), где A,B – несмежные вершины G(5,2),
назовём Цепочкой Петерсена и будем обозначать Ch(n, G(5,2)).
Слайд 22 Заключение
В данной работе нами были исследованы два ярких представителя Цепочек: Граф
![Заключение В данной работе нами были исследованы два ярких представителя Цепочек: Граф](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/890085/slide-21.jpg)
Гусеница и Цепочка Петерсена.
В Главе 1 приведены понятия Звена графа и его вершинных характеристик, а также даны определения хорошей, О-почти хорошей и
АВ-почти хорошей раскрасок графа. Ключевым является утверждение, доказанное в Теореме 1.2: количество хороших раскрасок графа в точности совпадает с числом его минимальных вершинных покрытий.
В Главе 2 содержится основной результат по Цепочкам – формула для нахождения числа минимальных вершинных покрытий Цепочки (Теорема 2.1).
Коэффициенты данной формулы зависят от вершинных характеристик Звеньев. Указанный результат был получен ранее в [2].
Слайд 23
Заключение
В Главах 3-4 найдены точные значения вершинных характеристик Звеньев, основой которых
![Заключение В Главах 3-4 найдены точные значения вершинных характеристик Звеньев, основой которых](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/890085/slide-22.jpg)
выступает цикл с концами в смежных вершинах (Теорема 3.2) и
граф Петерсена с концами в несмежных вершинах (Теорема 4.1).
В Главах 3-4 также установлены рекуррентные формулы для нахождения числа минимальных вершинных покрытий графа Гусеницы (Теорема 3.3) и
Цепочки Петерсена (Теорема 4.2).
Слайд 25Направления исследования
1. Нахождение числа минимальных вершинных покрытий Цепочек второго рода, получаемых путём
![Направления исследования 1. Нахождение числа минимальных вершинных покрытий Цепочек второго рода, получаемых](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/890085/slide-24.jpg)
замыкания Цепочек в цикл;
2. Расширение подклассов Цепочек за счёт изучения новых видов Звеньев.
Слайд 26Источники
1. Задача 13 «Окрестностные множества в графах» // РТЮМ-2018.
2. Листопадов М.В., Пасмурцев
![Источники 1. Задача 13 «Окрестностные множества в графах» // РТЮМ-2018. 2. Листопадов](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/890085/slide-25.jpg)
Е.С., Калугин П.Д. Вершинные покрытия графов // Доклад на XXV республиканском конкурсе работ исследовательского характера учащихся.
3.https://ru.wikipedia.org/wiki/%D0%93%D1%80%D0%B0%D1%84_%D0%9F%D0%B5%D1%82%D0%B5%D1%80%D1%81%D0%B5%D0%BD%D0%B0