Сборник тем курсовых работ по математике (алгебра, математическая логика, дискретная математика). Молчанов В.А - 37 стр.

UptoLike

ВУЗ: 

ОГУ | Оренбург

Составители: 

Рубрика: 

2 Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. – М.: ВШ,
1976.
3 Липский В. Комбинаторика для программистов. – М.: Мир, 1988.
4 Комбинаторный анализ. Задачи и упражнения. – М.: Наука, 1982.
Тема 61. Теорема Пойа и перечисление графов
Решение многих задач перечисления графов сводится к подсчету числа
классов эквивалентностей. Эффективный метод решения таких задач
базируется на известной теореме Пойа. Цель курсовой работы – изучить
основные свойства групп подстановок и метод решения комбинаторных задач
теории графов с помощью теоремы Пойа. Рекомендуется следующий план
работы.
1 Изучить такие основополагающие понятия теории графов и теории
групп, как граф, группа подстановок и ее цикловой индекс (/2/, с. 9-18; 239-243;
/3/, с. 21-26, 194; /4/, с. 50-63).
2 Рассмотреть определение эквивалентности, порождаемой группой
подстановок, и доказать лемму Бернсайда о числе классов такой
эквивалентности (/2/, с. 245-248; /4/, с. 81-85).
3 Разобрать определение перечня конфигурации и доказать теорему
Пойа (/2/, с. 248-259; /3/, с. 211-216).
4 Рассмотреть задачу о перечислении графов и метод ее решения с
помощью теоремы Пойа (/2/, с. 262-270; /3/, с. 216-224).
Разобрать все примеры из указанных выше литературных источников и
решить задачи 10a, 10c из /1/, 15.1, 15.2 из /3/ и 2.100-2.102, 2.120 из /5/.
Литература, рекомендуемая для изучения темы
1 Уилсон Р. Введение в теорию графов. – М.: Мир, 1977.
2 Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. – М.: ВШ,
1976.
3 Харари Ф. Теория графов. – М.: Мир, 1973.
4 Калужнин Л.А., Сущанский В.И. Преобразования и перестановки. –
М.: Наука, 1985.
5 Комбинаторный анализ. Задачи и упражнения. – М.: Наука, 1982.
Тема 62. Графы на двумерных поверхностях
Алгебраические методы теории графов позволяют исследовать такие
важные инварианты двумерных поверхностей, как эйлерова характеристика и
группы гомологий. В курсовой работе необходимо изучить основные свойства
графов на двумерных поверхностях и проанализировать известную взаимосвязь
групп цепей графов с топологическими инвариантами соответствующих
поверхностей. Рекомендуется следующий план работы. 
        2 Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. – М.: ВШ,
1976.
        3 Липский В. Комбинаторика для программистов. – М.: Мир, 1988.
        4 Комбинаторный анализ. Задачи и упражнения. – М.: Наука, 1982.

        Тема 61. Теорема Пойа и перечисление графов

         Решение многих задач перечисления графов сводится к подсчету числа
классов эквивалентностей. Эффективный метод решения таких задач
базируется на известной теореме Пойа. Цель курсовой работы – изучить
основные свойства групп подстановок и метод решения комбинаторных задач
теории графов с помощью теоремы Пойа. Рекомендуется следующий план
работы.
         1 Изучить такие основополагающие понятия теории графов и теории
групп, как граф, группа подстановок и ее цикловой индекс (/2/, с. 9-18; 239-243;
/3/, с. 21-26, 194; /4/, с. 50-63).
         2 Рассмотреть определение эквивалентности, порождаемой группой
подстановок, и доказать лемму Бернсайда о числе классов такой
эквивалентности (/2/, с. 245-248; /4/, с. 81-85).
         3 Разобрать определение перечня конфигурации и доказать теорему
Пойа (/2/, с. 248-259; /3/, с. 211-216).
         4 Рассмотреть задачу о перечислении графов и метод ее решения с
помощью теоремы Пойа (/2/, с. 262-270; /3/, с. 216-224).

      Разобрать все примеры из указанных выше литературных источников и
решить задачи 10a, 10c из /1/, 15.1, 15.2 из /3/ и 2.100-2.102, 2.120 из /5/.

        Литература, рекомендуемая для изучения темы
         1 Уилсон Р. Введение в теорию графов. – М.: Мир, 1977.
         2 Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. – М.: ВШ,
1976.
      3 Харари Ф. Теория графов. – М.: Мир, 1973.
      4 Калужнин Л.А., Сущанский В.И. Преобразования и перестановки. –
М.: Наука, 1985.
      5 Комбинаторный анализ. Задачи и упражнения. – М.: Наука, 1982.

        Тема 62. Графы на двумерных поверхностях

      Алгебраические методы теории графов позволяют исследовать такие
важные инварианты двумерных поверхностей, как эйлерова характеристика и
группы гомологий. В курсовой работе необходимо изучить основные свойства
графов на двумерных поверхностях и проанализировать известную взаимосвязь
групп цепей графов с топологическими инвариантами соответствующих
поверхностей. Рекомендуется следующий план работы.

Страницы