logo
лекции по МОТС / ДИСКРЕТНАЯ МАТЕМАТИКА Графы

Иркутский государственный технический университет

Факультет Кибернетики

Кафедра Автоматизированных систем

Носырева Л.Л.

ДИСКРЕТНАЯ МАТЕМАТИКА

Конспективный материал к лекциям

(рабочий вариант)

Для специальностей АСУ, МЭИ, ИП, АСОК

Часть 4

Графы

Иркутск 2006

Введение.

Теория графов, как раздел дискретной математики, имеет многочисленные предметные интерпретации. Среди дисциплин и методов дискретной математики теория, графов и особенно алгоритмы на графах находят наиболее широкое примене­ние в программировании. Как показано в разделе 7.5, между понятием графа и понятием отношения, рассмотренным в главе 1, имеется глубокая связь — в сущности это равнообъемные понятия. Возникает естественный вопрос, почему же тогда графам оказывается столь явное предпочтение? Дело в том, что тео­рия графов предоставляет очень удобный язык для описания программных (да и многих других) моделей. Этот тезис можно пояснить следующей аналогией. Понятие отношения также можно полностью выразить через понятие множества (см. замечание в подразделе 1.5.1 и далее). Однако независимое определение понятия отношения удобнее — введение специальных терминов и обозначений упрощает изложение теории и делает ее более понятной. То же относится и к теории графов. Стройная система специальных терминов и обозначений тео­рии графов позволяют просто и доступно описывать сложные и тонкие вещи. Особенно важно наличие наглядной графической интерпретации понятия графа (подраздел 7.1.4). Само название «граф» подразумевает наличие графической ин­терпретации. Картинки позволяют сразу «усмотреть» суть дела на интуитивном уровне, дополняя и украшая утомительные рациональные текстовые доказатель­ства и сложные формулы.

Эта глава практически полностью посвящена описанию языка теории графов.

Yandex.RTB R-A-252273-3
Yandex.RTB R-A-252273-4