Читать онлайн «Лекции по теории графов»

Лекции по ТЕОРИИ ГРАфОВ Допущено Государственным комитетом СССР по народному образованию в качестве учебного пособия для студентов, обучаюгцихся по специальностям «Maiематика» и «Прикладная математика» ш у, МОСКВА «НАУКА» ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ 1990 ББК 22. 174, Л43 УДК 519. 17(075. 8) Автор ы: В. А. ЕМЕЛИЧЕВ, О. И. МЕЛЬНИКОВ, В. И. САРВАНОВ, Р. И. ТЫШКЕВИЧ Лекции по теории графов/Б м е л и ч е в В. А. , Мельников О. И. , СарвановВ. И. , Тышкевич Р. И,—М. : Наука. Гл. ред. физ. -мат. лит. , 1990 — 384 с-ISBN 5-02-013992-0. Излагаются основы теории графов, обсуждаются некоторые известные проблемы. Приводятся примеры сведения прикладных задач к задачам теории графов и использования аппарата это» теории. Отдельная глава посвящена комбинаторным алгоритмам, связанным с поиском структурных и числовых характеристик графов Каждая глава сопровождается упражнениями. Для студентов вузов, обучающихся по специальностям «Математики» и «Прикладная математика». Табл. 1. Ил. 211. Бнблпогр. 32 назв. Рецензенты: 1. Кафедра математических методов исследования операций Воронежского государственного университета. 2. Кафедра теории исследования операций Ленинградского государственного университета. 1602100000—110 35 053 (02)-90 (6) «Нвуь-™. х—' Фшшат. Тит, I 990- ISBN 5-02-013992-0 Посвящается Дмитрию Алексеевичу СУПРУНЕНКО Предисловие В основу настоящего учебного пособия положены курсы лекций, которые читались авторами в Белорусском государственном университете им. В. И. Ленина для студентов-математиков и в Белорусском политехническом институте для студентов, обучающихся по специальности «Прикладная математика». Изложение материала в книге ставит своей целью дать в руки студентов орудие, применимое как к паукам о поведении (кибернетика, теория информации, теория систем, теория игр), так и к теории множеств, теории матриц, теории групп и к другим чисто абстрактным дисциплинам. Основной задачей этого учебного пособия является ознакомление студентов с теоретическими основами теории графов. Вместе с тем большое внимание уделяется вопросам применения теории графов к решению прикладных задач и в связи с этим,— построению эффективных алгоритмов. Книга состоит из двенадцати г . . чаи. В главе I даны основные понятия теории графов. Обсуждается гипотеза К е. тли — У лама о реконструируемо- сти, вводятся регулярные, двудольные и реберные графы, изучается группа автоморфизмов графа. Глава заканчивается результатами, характеризующими свойства графов при большом, числе вершин. Эти свойства отражают в некотором смысле типичный случай и потому формулируются в терминах «почти всех» графов. Глава II посвящена деревьям и остовам. Она содор- жит матричную теорему Кирхгофа о деревьях и теорему Кэ-ли о число помеченных деревьев. В этой же главе излагаются и обосновываются алгоритмы Краскала и Прима для решения задачи об остове минимального веса. Глава III содержит элементарное замкнутое изложение основ теории матроидов и трансверсалей, специально приспособленное к нуждам теории графов.