М еталлургический факультет

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

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

Часть 1

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

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

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

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

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

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

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

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

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

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

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

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

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

УДК 517.9

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

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

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

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

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

Введение

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

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

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

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

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

, , , .

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

, .

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

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

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

1.2Другие определения

Часто рассматриваются следующие родственные графам объекты.

1. Если элементами множества Е являются упорядоченные пары, то граф назы­вается ориентированным (или орграфом). В этом случае элементы множества V называются узлами, а элементы множества Е — дугами. На рис.2а приведена диаграмма орграфа с четырьмя вершинами и пятью дугами.

2. Если элементом множества Е может быть пара одинаковых (не различных) элементов V, то такой элемент множества Е называется петлей, а граф назы­вается графом с петлями (или псевдографом). На рис.2б приведена диаграмма псевдографа с пятью ребрами и двумя петлями.

3. Если Е является не множеством, а набором, содержащим несколько одинако­вых элементов, то эти элементы называются кратными ребрами, а граф назы­вается мулътиграфом. На рис.2в приведена диаграмма мулътиграфа с четырьмя ребрами и тремя кратными ребрами.

4. Если элементами множества Е являются не обязательно двухэлементные, а любые подмножества множества V, то такие элементы множества Е называ­ются гипердугами, а граф называется гиперграфом. На рис.2г приведена диаграмма гиперграфа с четырьмя вершинами и тремя гипердугами.

5. Если задана функция и/или , то множество М называ­ется множеством пометок, а граф называется помеченным (или нагруженным). В качестве множества пометок обычно используются буквы или целые числа.

а) орграф б) псевдограф

в) мультиграф г) гиперграф

Рис. 2. Примеры диаграмм различных типов графов

Далее под графом G(V, E) будем понимать неориентированный непомеченный граф без петель и кратных ребер.