Сетевые модели представления информации и сети.
Тема 2.4. Алгоритмы на графах
Основные понятия теории графов.
Теория графов – один из универсальных и наглядных языков: графический, который применяется во многих областях науки и техники.
Теория графов дает исключительно удобный аппарат для моделирования структурных свойств различных систем и отношений между объектами разной природы, в том числе программных моделей.
Графом G = (W, X) называется пара двух конечных множеств: множество точек и множество линий, соединяющих некоторые пары точек
Граф - множество линий X, соединяющее пары точек множества W. Точки называются вершинами (узлами) графа, линии - ребрами графа.
Если задан граф G = (W, X), тоW - конечное непустое множество его вершин, X – множествоего ребер.
Ребро называется инцидентным по отношению к тем вершинам, которые оно соединяет.
Две вершины графа называются смежными,если существует инцидентное им ребро.
Два ребра называются смежными,если они имеют общую вершину.
Графназывается ориентированным (направленным), если он состоит из упорядоченных пар вершин (кортежи длины 2). Такой граф еще называется орграфом.
В направленном графе ребра изображаются стрелками, идущими от первой компоненты (начало ребра) кортежа ко второй (конец ребра). См рисунок.
Маршрутом называется последовательность попарно инцидентных вершин V1, V2, ..., Vi неориентированного графа, т.е. последовательность ребер неориентированного графа, в которой вторая вершина предыдущего ребра совпадает с первой вершиной следующего.
Длиной маршрута называется число ребер этого маршрута.
Для одних и тех же вершин может оказаться несколько маршрутов разной или одинаковой длины, среди которых выбирается наиболее оптимальный маршрут, как правило – наименьший маршрут.
Маршрут принято задавать как последовательность ребер, поскольку это более удобно при наличии кратных ребер.
Маршрут называется замкнутым или циклом, если начальная вершина маршрута совпадает с конечной,
Расстояниеммежду двумя вершинами называется минимальная длина из всех возможных маршрутов между этими вершинами при условии, что существует хотя бы один такой маршрут.
Расстояние можно обозначать символами: d(A;B)= min|A;B|=k, где вершины A и B начало и конец маршрута, k – число, равное наименьшей длине маршрута.
Поскольку рассматриваются конечные графы, минимум можно найти всегда.
Одна из задач теории графов есть нахождение кратчайших путей в графе. На данный момент есть различные методы решения такой задачи, некоторые из которых будут рассмотрены в этом разделе.
В орграфе маршрут является ориентированным и называется путем.На путь сразу налагаются важные требования, являющиеся частью определения:
• направление каждой дуги должно совпадать с направлением пути;
• ни одно ребро пути не должно встречаться дважды.
Поэтому путь - упорядоченная последовательность ребер ориентированного графа, в которой конец предыдущего ребра совпадает с началом следующего и все ребра единственны.
В графе цепь, путь и цикл называются простыми,если они проходят через любую из вершин не более одного раза.
Неориентированный граф называется связным,если между любыми двумя его вершинами есть маршрут.В противном случае он называется - несвязным.
Две вершины называются связными,если существует маршрут между ними.
Граф G можно разбить на непересекающиеся подмножества (графы)по признаку связности, которые называются подграфами.
Вершины одного множества являются связными между собой, а вершины различных множеств - несвязны.
Ребро связного графа G называется мостом,если после его удаления G станет несвязным и распадется на два связных графа G' и G".
Способы задания графа:
Графы могут задаваться следующими способами:
1. Геометрическим способом - рисунки, схемы, диаграммы,
2. Алгебраическим способом - перечислением вершин и ребер,
3. Табличным способом. 4. Матричным способом.
Человеку удобно работать с графом-рисунком, так как он может легко установить связь между вершинами в наглядном виде с помощью ребер, изображаемых непрерывными линиями. Такое геометрическое представление плоского графа называется его реализацией.
Для машинной обработки удобнее задать граф в алгебраической форме - перечислением (списком) вершин или ребер.
Основным способом задания графа является перечисление всех его вершин и ребер. Но такое представление, во-первых, несимметрично (с ним трудно работать, особенно ЭВМ), во-вторых, для указания каждого ребра нужно еще раз выписывать соответствующие вершины, что плохо с точки зрения сжатия и хранения информации.
При задании графа таблицейсоставляется таблица,состоящей из п строк (вершины) и т столбцов (ребра). На пересечении строк и столбцов пишутся соответствующие знаки, которые показывают отношение (инцидентность) вершины и ребра. Это может быть знаки "+" и "-", числа 0,1,-1 и др.
Главным во всех способах задания графа (диаграммой, матрицей, таблицей) является указание соответствия между множествами п вершин Vt к т ребер X-t.
Пусть дан граф G(V, X),где V= {V1, V2 …Vn} - вершины, а Х= {Х1, Х2 .,., Хm} – ребра, среди которых могут и кратные ребра (есть вершины, которые соединяет несколько ребер).
Матрицей инцидентностиданного графа будет таблица, состоящая из n строк (вершины) и т столбцов (ребра).
При рассмотрении неориентированного графа на пересечении строк и столбцов ставится число 1, если соответствующие вершина и ребро инцидентны и ставится число 0, они не инцидентны.
При рассмотрении ориентированного графа на пересечении строк и столбцов ставится число 1, если из вершины выходит соответствующее ее ребро. Если в вершину входит ребро, то ставят число -1. Если вершина не инцидентна ребру и, то ставится число 0
Очевидно, что в каждом столбце матрицы инцидентности должно быть только два ненулевых числа, так как ребро инцидентно двум вершинам. Число ненулевых элементов каждой строки - степень соответствующей вершины.
Матрицы инцидентности прямоугольные, если число строк и столбцов различно. Если число вершин и ребер в графе одинаковое, то получается квадратная матрица.
Матрицу можно сделать квадратной для любого графа без кратных ребер. В таких случаях строки и столбцы изображают вершины. На пересечении строк и столбцов ставится число 1, если соответствующие вершины соединены ребром и ставится число 0, если вершины не соединены.
Для неориентированного графа ребраодновременно принадлежат или не принадлежат графу, так как символизируют одно и то же ребро. Матрица смежности неориентированного графа является симметрической и не меняется при транспонировании.
Хотя формально каждая вершина всегда смежная сама с собой, в матрице смежности мы будем ставить 0, если у нее нет петли, и 1, если есть одна петля.
Если граф имеет матрицу смежности и не имеет петель, на главной диагонали у него всегда стоят нули.
Задание.Составить таблицу и матрицу инцидентности для орграфа, изображенного на рисунке, который имеет 3вершины и 4 ребра.
Ответ.
|
| Вершины | Ребра | |||
| s | t | г | и | |
| V1 | -1 | |||
| V2 | -1 | |||
| V3 | -1 | -1 |
Задание.Для графа, изображенного на рисунке записать таблицу и матрицу смежности
Ответ
| Таблица смежности | ||||
| Вершины | A | B | C | D |
| A | 0 | 1 | 0 | 1 |
| B | 1 | 0 | 1 | 1 |
| C | 0 | 1 | 0 | 0 |
| D | 1 | 1 | 0 | 0 |
Матрица смежности
Граф с кратными ребрами (особенно орграф) сложно задать с помощью матрицы смежности. Для ориентированного графа данное определение графа без кратных ребер является частным случаем графа с кратными ребрами при кратности любого ребра, равной 1 или 0.
Применения графов и сетей
Сетевые модели представления информации и сети.
Граф называется взвешеннымили сетью,если каждому его ребру поставлено в соответствие некоторое число (вес). Взвешенными графами могут быть схемы в электронике, электрические схемы, карты автомобильных и железных дорог и др. Например, на картах автодорог вершины являются населенными пунктами, ребра - дорогами, а весом - числа, равные расстоянию между населенными пунктами.
В строительстве сетевые графы применяются для наглядного изображения некоторого комплекса работ или производственных процессов. Ребрам графа могут соответствовать числа, означающие длину, уклон, запланированное время и другие характеристики.
Например, последовательность работ для монтажа каркаса здания изображена в виде графа, изображенного на рисунке
Числами обозначены технологические операции:
1 - рытье котлована; 2 - монтаж фундамента; 3 - завоз металлоконструкций;
4 - монтаж подъемного крана; 5 - монтаж каркаса здания.
На следующем рисунке изображен сетевой граф некоторого комплекса работ в виде взвешенного графа с указанием времени, затраченного на выполнение этой работы (в минутах).
В основе процесса планирования лежит некоторый сценарий, представляющий собой сеть, состоящую из вершин - пошагового описания действий и дуг - отношений между ними. Такой граф дает возможность, сравнивая альтернативы, планировать действия для достижения поставленной цели.
Сети широко используются в качестве моделей для представления знаний в интеллектуальных системах. Сетевая модель представления информации основана на том, что любые знания можно рассматривать как множества объектов (понятий) и связи между ними (отношения).
Понятия-объекты и другие элементы предметной области могут быть графически изображены в виде вершин, а отношения между ними - в виде дуг, связывающих эти вершины. Такое графическое представление информации (знаний) в интеллектуальных системах носит название семантических сетей.Они являются универсальным средством для представления знаний в интеллектуальных системах.
Понятия, входящие в сети, можно описать с помощью фрейма.
Фреймом называется минимально возможное описание сущности некоторого явления, объекта, события или процесса. Состоит фрейм из набора стандартных единиц - слотов, содержащих определенный минимум информации о его содержании и назначении.
Семантическая сеть в виде некоторой совокупности фреймов нуждается в указании отношения между ее вершинами, что тоже возможно осуществить в виде слота.
Семантические сети широко применяются в информатике, например, для операций поиска по образцу,где в виде сетей представляется база данных. Результат такого поиска можно изобразить графом. Используются сети и для графической иллюстрации системы отношений базы данных.
Широко применяются сети для графического изображения различных логических схем в теории автоматов, например схемы с памятью, у которых каждый узел - функция алгебры логики
Для формального описания совокупности процессов, протекающих одновременно, используют сети Петри.Они представляют собой ориентированные графы, состоящие из вершин двух видов: некоторых позиций и переходов, причем позиции изображают кружочками, а переходы - «планками»
Сети Петри предназначены для описания действия дискретных процессов во времени. Такие сети дают возможность моделировать ситуации протекания параллельных процессов, прослеживать возможные варианты их взаимодействия, выявлять нежелательные ситуации. Также в виде сетей изображаются схемы устройств, например радиоприемника или телевизора.
Сети получили широкое практическое применение потому, что они являются естественным и удобным способом изображения и дальнейшего анализа различных сложных систем.
С помощью графов-деревьев решают задачи планирования (дерево целей, дерево переборов вариантов).
Графы используют также для иллюстрации классификаций в различных областях знаний при построении иерархическихструктур сложных систем. Такие графы часто называют блок-схемами.
Примеры блок схем
Так как иерархические структуры представляют собой подчиненные отношения (подмножества), то графически их можно изобразить либо в виде графа-дерева, либо с помощью кругов Эйлера
Аналогично устроена любая административно-территориальная структура: республика, области, районы, населенные пункты. По путям этих деревьев движутся информационные потоки: сверху вниз - распоряжения, руководящие указания, снизу вверх - отчеты о работе, оперативная информация. Так как путь от листа к корню единственный, то его можно использовать для опознания компонентов системы.
Например, почтовый адрес представляет собой «путь в дереве», аналогичный административно-территориальному. В разделе "Кому" указывается страна, республика, область, район, населенный пункт, улица, дом, квартира.
Аналогично классифицируют объекты в любой науке. Получаемая классификация служит примером иерархической структуры.Например, в биологии: класс, отряд, семейство, род, вид.
Соответствующий граф содержит элементы разных уровней, корень - класс, а листья - отдельные виды животных.
Иногда связи между объектами образуют не дерево, но все же их можно представить в виде графа. Это бывает в тех случаях, когда, например, происходит подчинение не одному, а нескольким независимым службам (соподчинение между собой).
В информатике иерархические структуры применяют при описании базы данных, вычислительных сетей, сетей связи, организационных систем. С помощью графа можно графически изображать родословные (генеалогическое дерево или древо).
Задание.Изобразить с помощью блок-схемы иерархическое представление видов вычислительных машин. Вычислительные машины делятся на аналоговые, цифровые, комбинированные. Цифровые машины делятся смешанные, оптоэлектрические, механические, электронные