Учебное пособие. Новосибирск: СибГУТИ, 2008. – 107 с.
Изложен основной теоретический материал, необходимый для изучения дискретной математики, а именно, входящего в нее раздела «Теория графов». Предназначено для использования в учебном процессе преподавателями и студентами технических специальностей.Содержание.
Предисловие.
Основные определения.
Способы задания графа.
Операции на графах.
Изоморфизм графов.
Представление сетей радиосвязи графами.
Связность.
Алгоритм выделения компонент сильной связности.
Деревья.
Обходы.
Поиск в глубину.
Поиск в ширину.
Эйлеров цикл.
Кратчайшие остовы в нагруженном графе.
Алгоритм Краскала построения остова минимального веса (жадный алгоритм).
Алгоритм Прима построения остова минимального веса (алгоритм ближайшего соседа).
Кратчайшие пути в нагруженном графе.
Алгоритм Дейкстры поиска кратчайшего пути в нагруженном графе.
Алгоритм Форда-Беллмана поиска кратчайших путей между всеми парами вершин в нагруженном графе.
Паросочетания.
Алгоритм построения наибольшего паросочетания в двудольном графе.
Алгоритм построения совершенного паросочетания минимального веса в двудольном нагруженном графе.
Раскраска графа.
Жадный алгоритм раскрашивания.
Алгоритм последовательного раскрашивания.
Список литературы.
