- •Часть 1
- •Часть 1. Способы описания, характеристики и основные операции
- •Введение
- •Теоретическая часть
- •1Определения графов
- •1.1Основное определение
- •1.2Другие определения
- •1.3Смежность вершин и ребер
- •1.4Изоморфизм графов
- •1.5Способы задания графов
- •2Элементы графов
- •2.1Подграфы
- •2.2Валентность вершин
- •2.3Маршруты, цепи, циклы
- •2.4Метрические характеристики графов
- •2.5Связность графов
- •3Виды графов
- •3.1Тривиальные и полные графы
- •3.2Двудольные графы
- •3.3Планарные и плоские графы
- •3.4Направленные орграфы и сети
- •4Операции над графами
- •5Представление графов с помощью матриц
- •5.1Матрица смежности
- •5.2Матрица инцидентности
- •5.3Матрица Кирхгофа
- •6Пример выполнения задания практического занятия
- •7Варианты заданий практических занятий
- •Часть 1. Способы описания, характеристики и основные операции
М еталлургический факультет
Кафедра информационных технологий в металлургии
Решение прикладных задач на основе теории графов
Часть 1
Способы описания, характеристики и основные операции
Новокузнецк 2001
Министерство образования Российской Федерации
Сибирский государственный индустриальный университет
Кафедра информационных технологий в металлургии
Решение прикладных задач
на основе теории графов.
Часть 1. Способы описания, характеристики и основные операции
Методические указания к выполнению практических
работ по курсам “Дискретная математика”,
“Теория информационных процессов и систем”
Специальность “Информационные системы и технологии” (071900).
Новокузнецк 2001
УДК 517.9
Рецензент: кафедра систем автоматизации (зав. каф. С.М. Кулаков)
Решение прикладных задач на основе теории графов. Часть 1. Способы описания, характеристики и основные операции.: Метод. указ. / Сост.: С.Н. Калашников, С.П. Мочалов, А.А. Ланцев: СибГИУ. ‑ Новокузнецк, 2001. ‑ 31 с., ил.
Рассмотрены основные понятия теории графов, их характеристики, основные операции над графами, различные способы задания графов.
Практические задания ориентированы на усвоение навыков работы с различными характеристиками графов и с различными операциями над графами.
Предназначены для студентов специальности “Информационные системы и технологии” (071900).
Введение
В настоящее время теория графов привлекает все большее внимание специалистов самых разных областей науки и техники. Теория графов является эффективным аппаратом формализации современных инженерных задач, связанных с дискретными объектами. Такие задачи возникают при проектировании интегральных схем и систем управления, при исследовании автоматов и логических цепей, при системном анализе, автоматизированном управлении производством, в теории расписаний и дискретной оптимизации. Обширное применение теория графов нашла в современной вычислительной технике и кибернетике: в теоретическом программировании, при проектировании ЭВМ и сетей ЭВМ, баз данных, систем логического управления. Особый интерес приобретает теория графов у инженеров-конструкторов и системотехников в связи с ее широким использованием при проектировании. В предлагаемых методических указаниях дано изложение основных понятий теории графов, их характеристик и основных операций над графами.
Теоретическая часть
1Определения графов
1.1Основное определение
Графом G(V, E) называется совокупность двух множеств — непустого множества V (множества вершин) и множества Е неупорядоченных пар различных элементов множества V (Е — множество ребер).
, , , .
Число вершин графа G обозначим р, а число ребер — q:
, .
Обычно граф изображают диаграммой: вершины — точками (или кружками), ребра — линиями.
Пример. На рис. 1 приведен пример диаграммы графа, имеющего четыре вершины и пять ребер. В этом графе вершины v1 и v2, v2 и v3, v3 и v4, v4 и v1, v2 и v4 смежные, а вершины v1 и v3 не смежные. Смежные ребра: е1 и е2, е2 и е3, е3 и е4, е4 и е1, e1 и е5, е2 и е5, е3 и е5, е4 и е5. Несмежные ребра: е1 и е3, е2 и е4.
Рис. 1. Диаграмма графа
1.2Другие определения
Часто рассматриваются следующие родственные графам объекты.
Если элементами множества Е являются упорядоченные пары, то граф называется ориентированным (или орграфом). В этом случае элементы множества V называются узлами, а элементы множества Е — дугами. На рис.2а приведена диаграмма орграфа с четырьмя вершинами и пятью дугами.
Если элементом множества Е может быть пара одинаковых (не различных) элементов V, то такой элемент множества Е называется петлей, а граф называется графом с петлями (или псевдографом). На рис.2б приведена диаграмма псевдографа с пятью ребрами и двумя петлями.
Если Е является не множеством, а набором, содержащим несколько одинаковых элементов, то эти элементы называются кратными ребрами, а граф называется мулътиграфом. На рис.2в приведена диаграмма мулътиграфа с четырьмя ребрами и тремя кратными ребрами.
Если элементами множества Е являются не обязательно двухэлементные, а любые подмножества множества V, то такие элементы множества Е называются гипердугами, а граф называется гиперграфом. На рис.2г приведена диаграмма гиперграфа с четырьмя вершинами и тремя гипердугами.
Если задана функция и/или , то множество М называется множеством пометок, а граф называется помеченным (или нагруженным). В качестве множества пометок обычно используются буквы или целые числа.
а) орграф б) псевдограф
в) мультиграф г) гиперграф
Рис. 2. Примеры диаграмм различных типов графов
Далее под графом G(V, E) будем понимать неориентированный непомеченный граф без петель и кратных ребер.