Рабочая программа учебной дисциплины

РАБОЧАЯ ПРОГРАММА УЧЕБНОЙ ДИСЦИПЛИНЫ (РПУД)

Направление подготовки 011200.68 – Физика,

ОП – методология физики

Форма подготовки - очная

• 
  научить культуре графового моделирования с помощью простых помеченных графов
  
• 
  научить перечислять разнообразные совокупности древовидных графов и орграфов;
  
• 
  сформировать общие представления о перечислении конфигураций, строящихся путем наложения одних объектов на другие;
  
• 
  научить выполнять компьютерные изображения графовых построений
  

1. 
   Структура и содержание теоретической части курса
   

1. 
   Число способов, которыми можно пометить граф.
   
2. 
   Связанные графы.
   
3. 
   Блоки.
   
4. 
   Эйлеровы графы.
   
5. 
   Число k-раскрашенных графов.
   
6. 
   Ациклические орграфы.
   
7. 
   Деревья.
   
8. 
   Эйлеровы контуры в орграфах.
   
9. 
   1-Деревья.
   
10. 
    Корневые деревья.
    
11. 
    Некорневые деревья.
    
12. 
    Деревья со специальными свойствами.
    
13. 
    Древовидные графы.
    
14. 
    2-деревья.
    
15. 
    Графы.
    
16. 
    Связные графы.
    
17. 
    2-раскрашенные графы.
    
18. 
    Корневые графы.
    
19. 
    Надграфы и раскрашенные графы.
    
20. 
    Булевы функции.
    
21. 
    Эйлеровы графы.
    
22. 
    Орграфы.
    
23. 
    Турниры.
    
24. 
    Ориентация графа.
    
25. 
    Смешанные графы.
    
26. 
    Графы с данными числами вершин и ребер.
    
27. 
    Связные графы и блоки.
    

4. 
   тематика и перечень курсовых работ и рефератов
   

1. 
   Перечисление с помощью теоремы большого количества разнообразных совокупностей деревьев.
   
2. 
   Доказательство теоремы Пойа.
   
3. 
   Лемма Бернсайда.
   
4. 
   Теорема Пойа.
   
5. 
   Ряд 1+х – специальный ряд для фигур.
   
6. 
   Взаимно-однозначные функции
   
7. 
   Различные виды графов и орграфов.
   
8. 
   Применение теоремы Пойа.
   
9. 
   Задачи перечисления таких конфигураций, которые могут быть построены путем наложения одних объектов на другие.
   
10. 
    Задача перечисления неразложимых графов, так называемых блоков.
    
11. 
    Обобщение леммы Редфилда. Теорема декомпозиции Редфилда.
    
12. 
    Графы и орграфы. 
    
13. 
    Обобщение теоремы перечисления Редфилда.
    
14. 
    Общие графы
    
15. 
    Доказательство теоремы перечисления степенной группы.
    
16. 
    Теорема перечисления степенной группы.
    
17. 
    Самодополнительные графы.
    
18. 
    Взвешенные функции.
    
19. 
    Графы с раскрашенными ребрами.
    
20. 
    Конечные автоматы.
    
21. 
    Самообратные орграфы.
    

4. 
   Учебно-методическое обеспечение дисциплины
   

1. 
   Домнин Л.Н. Элементы теории графов: Учебное пособие. - Пенза: Изд-во ПГУ, 2007. - 144 с. - http://window.edu.ru/resource/360/60360
   
2. 
   Берзин Е.А. Элементарные решения неэлементарных задач на графах: Учебное пособие / Под ред. А.Н. Кудинова. - Тверь: ТГТУ, 2005. - 136 с. - http://window.edu.ru/resource/614/58614
   
3. 
   Алексеев В.Е., Захарова Д.В. Теория графов. Электронное учебно-методическое пособие. - Нижний Новгород: Нижегородский госуниверситет, 2012. - 57 с. - http://window.edu.ru/resource/211/79211
   
4. 
   Diestel R. Graph Theory - Springer, 2005 - 410 pages.
   
5. 
   Харари Ф. Теория графов / Пер.с англ. и предисл. В. П. Козырева. Под ред. Г. П. Гаврилова. Изд. 2-е. - М.: Едиториал УРСС, 2003. - 296 с.
   
6. 
   Звонкин А.К., Ландо С.К. Графы на поверхностях и их приложения Издательство МЦНМО, М.: 2010, -457 c. http://www.twirpx.com/file/1094946/
   
7. 
   Мельников О.И. Незнайка в стране графов: Пособие для учащихся. Изд. 3-е, стереотипное. М.: КомКнига, 2007. — 160 с.
   

1. 
   Оре О. Теория графов.— 2-е изд.— М.: Наука, Главная редакция физико-математической литературы, 1980, 336 с. http://www.twirpx.com/file/98130/
   
2. 
   Свами М., Тхуласираман К. Графы, сети и алгоритмы: Пер. с англ. - М.:Мир, 1984, 456 с. http://www.twirpx.com/file/539885/
   
3. 
   Beineke L.W., Moon J.W. Several proofs of the number of labeled 2-dimensional trees. In a Book Proof Techniques in Graph Theory (Ed. Harary F.) Acad. Press, New York, 1969 pp.11-20.
   
4. 
   Донец Г.А. О нижней границе числа вершин плоских критических графов. Кибернетика, 4, 1971. С. 76-85.
   
5. 
   Ф. Харари, Э. Палмер. Перечисление графов, пер. с англ. Г.П. Гаврилова. Мир. М.: 1977. – 324 с.
   
6. 
   Нефедов В. Н., Осипова В.А. Курс дискретной математики / МАИ. М., 1992.
   
7. 
   Лихтарникова Л.М., Сукачева Т.Г. Математическая логика. Курс лекций. Задачник-практикум и решения. СПб, 1988.
   
8. 
   Мамонтова Н.П. и др. Методические указания к практическим занятиям по теории сетей связи / ЛЭИС. Л., 1978.
   
9. 
   Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.
   
10. 
    Уилсон Р. Введение в теорию графов. М.: Мир, 1977.
    
11. 
    Robinson R.W. Enumeration of euler graphs. In a Book Proof Techniques in Graph Theory (ed. Harary F.) Acad. Press, New York, 1969 pp.147-153.
    
12. 
    Handbook of
    
13. 
    Алексеев В.В., Гаврилов Г.П., Сапоженко А.А. (ред.) Теория графов. Покрытия, укладки, турниры. Сборник переводов - М. : Мир, 1974.— 224 с.
    
14. 
    Асельдеров З.М., Донец Г.А. Представление и восстановление графов - К.:Наукова Думка, 1991, 96 стр.
    
15. 
    Березина Л. Ю. Графы и их применение: Пособие для учителей. — М.: Просвещение, 1979. — 143 с. с ил. 
    
16. 
    Донец Г.А., Шор Н.3. Алгебраический подход к проблеме раскраски плоских графов - К.: Наукова думка, 1982. — 144 с.
    
17. 
    Зыков А.А. Основы теории графов. - М.:Наука, 1987, 384 с.
    
18. 
    Калмыков Г. И. Древесная классификация помеченных графов. - М.: ФИЗМАТЛИТ, 2003. - 192 с.
    
19. 
    Камерон П., ван Линт Дж. Теория графов, теория кодирования и блок-схемы - М.:Наука, 1980, 140 стр.
    
20. 
    Кристофидес Н. Теория графов. Алгоритмический подход. Пер. с анг. - М.:Мир, 1978, 432 с.
    
21. 
    Майника Э. Алгоритмы оптимизации на сетях и графах. Пер. с англ. - М.:Мир,1981, 328 с.
    
22. 
    Мелихов А.Н., Берштейн Л.С., Курейчик В.М. Применение графов для проектирования дискретных устройств - М.:Наука, 1974, 304 с.
    
23. 
    Мельников О.И. Теория графов в занимательных задачах. Изд.3, испр. и доп. 2009. 232 с.
    
24. 
    Татт У. Теория графов. Пер. с англ. - М.:Мир, 1988, 424 с.
    
25. 
    Уилсон Р. Введение в теорию графов. Пер. с анг. 1977. 208 с.