Элементы теории графов

Купить бумажную книгу и читать

Автор: Носов В.И.

Название: Элементы теории графов

Издательство: Новосибирск: Сибирский государственный университет телекоммуникаций и информатики

Год: 2008

Формат: pdf

Размер: 2 mb

Для сайта:

В данном учебном пособии изложен основной теоретический материал, необходимый для изучения дискретной математики, а именно, входящего в нее раздела "Теория графов".

Оглавление.

Предисловие.

Основные определения.

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

Операции на графах.

Изоморфизм графов.

Представление сетей радиосвязи графами.

Связность.

Алгоритм выделения компонент сильной связности.

Деревья.

Обходы.

Поиск в глубину.

Поиск в ширину.

Эйлеров цикл.

Кратчайшие остовы в нагруженном графе.

Алгоритм Краскала построения остова минимального веса (жадный алгоритм).

Алгоритм Прима построения остова минимального веса (алгоритм ближайшего соседа).

Кратчайшие пути в нагруженном графе.

Алгоритм Дейкстры поиска кратчайшего пути в нагруженном графе.

Алгоритм Форда-Беллмана поиска кратчайших путей между всеми парами вершин в нагруженном графе.

Паросочетания.

Алгоритм построения наибольшего паросочетания в двудольном графе.

Алгоритм построения совершенного паросочетания минимального веса в двудольном нагруженном графе.

Раскраска графа.

Жадный алгоритм раскрашивания.

Алгоритм последовательного раскрашивания.