О реберно-регулярных графах с b 1 =5 и k=10. Выпускная квалификационная работа. - презентация

1 О реберно-регулярных графах с b 1 =5 и k=10. Выпускная квалификационная работа.

2 Актуальность Преимущества теории графов: -широкий круг применения -высокая наглядность решения задач -граф-модель реальных объектов Наука -подробное описание класса реберно-регулярных графов с различными параметрами. Образование -внедрение теории графов в школьный курс математики. -более доступная интерпретация теории графов.

3 Цель Изучение почти хороших пар в реберно-регулярных графах с k=10 и b 1 =5. Разработка дополнительной образовательной программы для учащихся 9 класса.

4 Объект. Предмет. Гипотеза. Объект исследования Реберно- регулярный граф с параметрами k=10 и b 1 =5 Предмет исследования Свойства почти хороших пар реберно- регулярного графа Гипотеза исследования: граф с параметрами k=10 и b1=5 является 6 х 6 решеткой или реберным графом регулярного графа без треугольников, имеющего степень 6 и диаметр больше 2.

5 Поставленные задачи: Изучить реберно-регулярный граф с параметрами k=10 и b 1 =5 в частности, рассмотреть свойства хороших пар и попытаться найти связь его с уже известными графами. Разработать ДОП «Вопросы теории графов»

6 Теория графов. (Л. Эйлер; 1736 г.) Примеры различных графов Обозначение исследуемых графов Г(v, k, λ, μ). Где v – количество вершин графа; k - степень регулярности; λ – количество треугольников в которых лежит ребро; μ – количество треугольников в которых лежит ко ребро.

7 Результаты полученные ранее описывают графы с k3b 1 -2, где b 1 =k-λ-1 Теорема о классификации реберно-регулярных графов с k>3b 1 -3: Для любой вершины u верно |Г 2 (u)|(k-2b 1 +2)kb 1 и либо Г является реберным графом тривалентного графа без треугольников и диаметр графа >2, либо Г является n-угольником, n>4, или графом икосаэдра. Для любой вершины u верно |Г 2 (u)|(k-2b 1 +2)=kb 1 и Г является полным многодольным графом с долями порядка 2, 3 х 3 решеткой, треугольным графом Т(m) (m<8), графом Клебша или графом Шлефли.

8 Основной результат работы описывает вполне регулярные графы с k=10 и b 1 =5 Результат выражается в следующей теореме Теорема. Пусть Г – вполне регулярный граф с параметрами (v, k, λ, μ), где k=10 и b 1 =5. Тогда Г является 6 х 6 решеткой или реберным графом регулярного графа степени 6 без треугольников.

9 Доказательство основной теоремы. Диаметр графа Г Диаметр равен 2 Г есть 6 х 6 решетка Диаметр больше двух μ=1 Г – реберный граф Регулярного графа степени 6 без треугольников

10 Дополнительная образовательная программа «Вопросы теории графов» Классы: 9 Образовательная область: «Информатика», «Математика». Цель курса: познакомить школьников с основами теории графов и ее применении; Задачи: - сформировать у учащихся чувство значимости теории графов; - вооружить учащихся теоретическими знаниями в необходимом объеме; - сформировать практические умения аппарата графов.

11 Тематическое планирование п/п Название разделов, тем.Всего часов. Теории.Практики.Форма. Образовательный продукт. 1. Основные вопросы теории графов Определение графа.11-Лекция, практикум. Конспект, решения задач. 1.2Валентность. Регулярные графы. 11-Лекция.Конспект. 1.3Элементы графов.321Лекция, практикум. Конспект. Практические работы. 1.4Диаметр графа.211Лекция, практикум. Конспект, решения задач. 1.5Виды графов.11-Лекция.Конспект. Примеры разных графов. 2. Практическое применение теории графов Представление графов в ЭВМ. 211Лекция. Лабораторная работа. Конспект. Результаты лабораторной работы. 2.2Решение практических задач. 1-1Практикум.Решения конкретных практических задач.

12 Теория графов: научно- популярная лекция. Аудитория: 9 класс и старше; Цель: мотивация выбора профиля и набора элективных курсов. Содержание: 1) История возникновения теории графов; 2) Основные моменты теории графов; 3) Задачи на применение теории графов.

13 Теория графов: научно- популярная лекция.

14 Электронное пособие.

15

16

17 Задачный материал Тема 1. Определение графа. Диаграмма графа. 1. Постройте несколько диаграмм графа G. a) E{1,2,3,4} V{(1,2),(2,3),(3,1),(4,1)} b) E{a,b,c,d,e} V{(a,d), (a,c), (a,e), (c,d), (b,d)} c) E{w,x,y,z} V{(w,z), (w,x), (w,y)} d) E{1,2,3,4,5,6} V{(1,4), (1,5), (1,6), (2,3), (3,4), (4,6)} 2. Дана диаграмма графа. Запишите граф в виде G Самостоятельно обозначьте вершины. a) b)b) c) c) d)d) Рис Постройте диаграмму графа G в котором ребра есть только между вершинами с четными номерами и между вершинами с нечетными номера. Если известно количество вершин. a) 4 b)8 c)5 d)7 e)11 f)6