Читать онлайн «Графы и сети: учебное пособие для студентов экономических специальностей»

Е. В. Харитонова ГРАФЫ И СЕТИ Ульяновск 2006  ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение высшего профессионального образования Ульяновский государственный технический университет Е. В. Харитонова ГРАФЫ И СЕТИ Учебное пособие для студентов экономических специальностей Ульяновск 2006 УДК 512. 5+333 (075) ББК 22. 17я7 Х20 Рецензенты: Кафедра общенаучных дисциплин ИАТУ УлГТУ (зав. кафедрой канд. хим. наук М. В. Бебякова, доцент А. Г. Карасева); канд. физ. -мат. наук кафедры экономико-математических методов и информационных технологий Института экономики и бизнеса УлГУ А. Е. Эткин Утверждено редакционно-издательским советом университета в качестве учебного пособия. Харитонова, Е. В. Х 20 Графы и сети : учебное пособие / Е. В. Харитонова. – Ульяновск : УлГТУ, 2006. – 92 с. ISBN 5-89146-878-6 В учебном пособии изложены основы теории графов и сетей. Материал каждого раздела проиллюстрирован примерами и сопровождается подборкой задач для практических занятий, имеются контрольные задания. Содержание пособия соответствует государственному образовательному стандарту высшего образования для экономических специальностей. Пособие рекомендовано для специальностей 080109 «Бухгалтерский учет, анализ и аудит», 080507 «Менеджмент организации» и может использоваться студентами и преподавателями при подготовке к занятиям. УДК 512. 5+333 (075) ББК 22. 17я7 Учебное издание ХАРИТОНОВА Елена Викторовна ГРАФЫ И СЕТИ Учебное пособие Редактор А. В. Власова Подписано в печать 03. 06. 2006. Формат 60×84/16. Бумага офсетная. Печать трафаретная. Усл. печ. л. 5,29. Тираж 100 экз. Заказ . Ульяновский государственный технический университет 432027, г. Ульяновск, ул. Сев. Венец, 32 Типография УлГТУ, 432027, г. Ульяновск, ул. Сев. Венец, 32 ISBN 5-89146-878-6 © Харитонова Е. В. © Оформление. УлГТУ, 2006  ОГЛАВЛЕНИЕ ВВЕДЕНИЕ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 4 1. ГРАФЫ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 5 1. 1. Основные понятия и определения ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 5 1. 2 Ориентированные графы... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 10 1. 3 Пути и циклы Эйлера ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 14 1. 4 Планарные графы... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 15 1. 5 Пути и циклы Гамильтона ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 17 1. 6 Алгоритм поиска кратчайшего пути... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 19 УПРАЖНЕНИЯ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 23 2.