2-е издание: Учеб. пособие. – Саратов: Изд-во «Научная книга», 2009. – 76 с.
ISBN 978-5-9758-0905-6Настоящее учебное пособие содержит теоретический материал и практические задания к курсу «Введение в теорию графов», читаемому в Саратовском государственном университете.
Для студентов и преподавателей математических факультетов университетов и технических вузов.Теория графов – важный раздел современной математики с большим прикладным значением. Данное учебное пособие содержит необходимые теоретические сведения и ряд заданий, предназначенных для сопровождения теоретического курса «Теория графов». По сравнению с первым изданием увеличено количество заданий с 9 до 13 и расширен теоретический материал. В пособии предлагается 13 заданий, которые включают теоретические задания (№ 1-11), практическое (№ 12) и аналитическое задание (№ 13). В начале каждого раздела приводится реферативное изложение теоретического материала, необходимого для решения заданий. Первые задания (№ 1-4) связаны с основными свойствами неориентированных графов: нахождение группы автоморфизмов графа, подобных вершин, минимальных расширений, построение реализаций вектора степеней и степенного множества. Вторая группа заданий (№ 5, 6) связана с деревьями: нахождение центра и центроида, кодирование и визуализация деревьев. В третьей группе заданий (№ 7) необходимо по заданной колоде реконструировать граф. В четвертой группе заданий (№ 7, 8) рассматриваются ориентированные графы: требуется построить факторграф по заданной эквивалентности, конденсацию, базу орграфа и минимальный проверяющий тест. Пятая группа содержит дополнительные задания. Задание № 12 – практическое задание, выполняя которое необходимо написать программу на любом современном языке программирования. Заключительное задание №13 содержит утверждения, которые необходимо доказать или опровергнуть.Содержание:Основные свойства графов.
Характеристики графов. Изоморфизмы и вложения графов. Степенной вектор. Степенное множество.
Деревья.
Свойства деревьев. Кодирование деревьев.
Реконструируемость.
Факторграфы. Диагностика.
Алгоритмы на графах.
Минимальные остовы. Кратчайшие пути.
Литература.
