Основное определение

Решение прикладных задач на основе теории графов

Часть 1

Способы описания, характеристики и основные операции

Новокузнецк
2001

Министерство образования Российской Федерации

Сибирский государственный индустриальный
университет

Кафедра информационных технологий в металлургии

Решение прикладных задач

На основе теории графов.

ЧАСТЬ 1. СПОСОБЫ ОПИСАНИЯ, ХАРАКТЕРИСТИКИ И ОСНОВНЫЕ ОПЕРАЦИИ

Методические указания к выполнению практических

работ по курсам “Дискретная математика”,

“Теория информационных процессов и систем”

Специальность “Информационные системы и технологии” (071900).

Новокузнецк
2001

УДК 517.9

Рецензент:
кафедра систем автоматизации (зав. каф. С.М. Кулаков)

Решение прикладных задач на основе теории графов. Часть 1. Способы описания, характеристики и основные операции.: Метод. указ. / Сост.: С.Н. Калашников, С.П. Мочалов, А.А. Ланцев: СибГИУ. ‑ Новокузнецк, 2001. ‑ 31 с., ил.

Рассмотрены основные понятия теории графов, их характеристики, основные операции над графами, различные способы задания графов.

Практические задания ориентированы на усвоение навыков работы с различными характеристиками графов и с различными операциями над графами.

Предназначены для студентов специальности “Информационные системы и технологии” (071900).

Введение

В настоящее время теория графов привлекает все большее внимание специалистов самых разных областей науки и техники. Теория графов является эффективным аппаратом формализации современных инженерных задач, связанных с дискретными объектами. Такие задачи возникают при проектировании интегральных схем и систем управления, при исследовании автоматов и логических цепей, при системном анализе, автоматизированном управлении производством, в теории расписаний и дискретной оптимизации. Обширное применение теория графов нашла в современной вычислительной технике и кибернетике: в теоретическом программировании, при проектировании ЭВМ и сетей ЭВМ, баз данных, систем логического управления. Особый интерес приобретает теория графов у инженеров-конструкторов и системотехников в связи с ее широким использованием при проектировании. В предлагаемых методических указаниях дано изложение основных понятий теории графов, их характеристик и основных операций над графами.

Теоретическая часть

Определения графов

Основное определение

Графом G (V, E) называется совокупность двух множеств — непустого множества V (множества вершин) и множества Е неупорядоченных пар различных элемен­тов множества V (Е — множество ребер).

, , , .

Число вершин графа G обозначим р, а число ребер — q:

, .

Обычно граф изображают диаграммой: вершины — точками (или кружками), ребра — линиями.

Пример. На рис. 1 приведен пример диаграммы графа, имеющего четыре вершины и пять ребер. В этом графе вершины v ₁ и v ₂, v ₂ и v ₃, v ₃ и v ₄, v ₄ и v ₁, v ₂ и v ₄ смежные, а вершины v ₁ и v ₃ не смежные. Смежные ребра: е ₁ и е ₂, е ₂ и е ₃, е ₃ и е ₄, е ₄ и е ₁, e ₁ и е ₅, е ₂ и е ₅, е ₃ и е ₅, е ₄ и е ₅. Несмежные ребра: е ₁ и е ₃, е ₂ и е ₄.

Рис. 1. Диаграмма графа