Введение в теорию графов

Введение в теорию графов

Рекомендовано редакционно-издательским советом университета

в качестве учебно-методического пособия

Кострома

КГТУ

УДК 519.1 (075)

Чередникова, А.В. Введение в теорию графов / А.В. Чередникова,

И.В. Землякова. – Кострома: Изд-во Костром. гос. технол. ун-та, 2012. – 25 с.

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

Пособие предназначено для студентов 1 курса бакалавриата по направлению подготовки 090900 «Информационная безопасность» и студентов 2 курса бакалавриата по направлениям подготовки 230100 «Информатика и вычислительная техника», 230400 «Информационные системы и технологии».

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

Рецензент: В.Н. Шведенко, д-р техн. наук, профессор,

зав. кафедрой информационных технологий КГТУ

© Костромской государственный технологический университет, 2012

ОГЛАВЛЕНИЕ

Введение. 4

§1. Основные понятия и определения. 4

§2. Способы задания графов. 7

§3. Изоморфные графы.. 9

§4. Взвешенные графы.. 10

§5. Подграф. 10

§6. Операции над графами. 12

§7. Маршруты, цепи, циклы.. 13

§8. Связность. Компоненты связности. 14

§9. Метрические характеристики графа. 17

§10. Деревья и их свойства. Лес. 18

§11. Эйлеровы цепи и циклы.. 20

§12. Гамильтоновы цепи и циклы.. 21

§13. Планарные графы.. 22

§14. Раскраска графов. Хроматические графы.. 24

Список литературы.. 25