Сетевые модели представления информации и сети.

Тема 2.4. Алгоритмы на графах

Основные понятия теории графов.

Теория графов – один из универсальных и нагляд­ных языков: графический, который применяется во многих облас­тях науки и техники.

Теория графов дает исключительно удобный аппарат для моделирования структурных свойств различ­ных систем и отношений между объектами разной природы, в том числе программных моделей.

Графом G = ( W, X) называется пара двух конечных множеств: множество точек и множество линий, соединяющих некоторые пары точек

Граф - множество линий X, соединяющее пары точек множества W. Точки называются вершинами (узлами) графа, линии - ребрами графа.

Если задан граф G = ( W, X), тоW - конечное непустое множество его вершин, X – множествоего ребер.

Ребро называется инцидентным по отношению к тем вершинам, которые оно соединяет.

Две вершины графа на­зываются смежными, если существует инцидентное им ребро.

Два ребра называются смежными, если они имеют общую вершину.

Графназывается ориентированным (направленным), если он состоит из упорядоченных пар вершин (кортежи длины 2). Такой граф еще называется орграфом.

В направленном графе ребра изображаются стрелками, идущими от первой компоненты (начало ребра) кортежа ко второй (конец ребра). См рисунок.

Маршрутом называется последовательность попарно инцидентных вершин V₁, V₂,..., V_i неориентированного графа, т.е. последовательность ребер не­ориентированного графа, в которой вторая вершина предыдуще­го ребра совпадает с первой вершиной следующего.

Длиной маршрута называется число ребер этого маршрута.

Для одних и тех же вершин может оказаться несколько маршрутов разной или одинаковой длины, среди которых выбирается наиболее оптимальный маршрут, как правило – наименьший маршрут.

Маршрут принято задавать как последователь­ность ребер, поскольку это более удобно при наличии кратных ребер.

Маршрут называется замкнутым или циклом, если начальная вершина маршрута совпадает с конечной,

Расстоянием между двумя вершинами называется минималь­ная длина из всех возможных маршрутов между этими вершина­ми при условии, что существует хотя бы один такой маршрут.

Расстояние можно обозначать символами: d(A;B)= min|A;B|=k, где вершины A и B начало и конец маршрута, k – число, равное наименьшей длине маршрута.

Поскольку рассматриваются конечные графы, минимум мож­но найти всегда.

Одна из задач теории графов есть нахождение кратчайших путей в графе. На данный момент есть различные методы решения такой задачи, некоторые из которых будут рассмотрены в этом разделе.

В орграфе маршрут является ориентированным и называется путем. На путь сразу налагаются важные требования, являющиеся частью определения:

• направление каждой дуги должно совпадать с направлением пути;

• ни одно ребро пути не должно встречаться дважды.

Поэтому путь - упорядоченная последовательность ребер ориентированного графа, в которой конец предыдущего ребра совпадает с началом следующего и все ребра единственны.

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

Неориен­тированный граф называется связным, если между любыми дву­мя его вершинами есть маршрут.В противном случае он называется - несвязным.

Две вершины называются связными, если существует маршрут между ними.

Граф G можно разбить на непересекающиеся подмножества (графы)по признаку связности, которые называются подграфами.

Вершины одного множества являются связ­ными между собой, а вершины различных множеств - несвязны.

Ребро связного графа G на­зывается мостом, если после его удале­ния G станет несвязным и распадется на два связных графа G' и G".

Способы задания графа:

Графы могут задаваться следующими способами:

1. Геометрическим способом - рисунки, схемы, диаграммы,

2. Алгебраическим способом - перечислением вершин и ребер,

3. Табличным способом. 4. Матричным способом.

Человеку удобно работать с графом-рисунком, так как он может легко установить связь между вершинами в на­глядном виде с помощью ребер, изображаемых непрерывными линиями. Такое геометрическое представление плоского графа на­зывается его реализацией.

Для машинной обработки удобнее за­дать граф в алгебраической форме - перечислением (списком) вершин или ребер.

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

При задании графа таблицей составляется таблица, состоящей из п строк (вершины) и т столбцов (ребра). На пересечении строк и столбцов пишутся соответствующие знаки, которые показывают отношение (инцидентность) вершины и ребра. Это может быть знаки "+" и "-", числа 0,1,-1 и др.

Главным во всех способах задания графа (диаграммой, матрицей, таблицей) является указание соответствия между множествами п вершин V_t к т ребер X-_t.

Пусть дан граф G(V, X),где V= {V₁, V₂ …V_n} - вершины, а Х= {Х₁, Х₂.,., Х_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 - монтаж каркаса здания.

На следующем рисунке изображен сетевой граф некоторого комплекса работ в виде взвешенного графа с указанием времени, затраченного на выполнение этой работы (в минутах).

В основе процесса планирования лежит некоторый сценарий, представляющий собой сеть, состоящую из вершин - пошагово­го описания действий и дуг - отношений между ними. Такой граф дает возможность, сравнивая альтернативы, планировать действия для достижения поставленной цели.

Сети широко используются в качестве моделей для представ­ления знаний в интеллектуальных системах. Сетевая модель пред­ставления информации основана на том, что любые знания мож­но рассматривать как множества объектов (понятий) и связи между ними (отношения).

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

Понятия, входящие в сети, можно описать с помощью фрейма.

Фреймом называется минимально возможное описание сущности некоторого явления, объекта, события или процесса. Состоит фрейм из набора стандартных единиц - сло­тов, содержащих определенный минимум информации о его со­держании и назначении.

Семантическая сеть в виде некоторой совокупности фреймов нуждает­ся в указании отношения меж­ду ее вершинами, что тоже воз­можно осуществить в виде сло­та.

Семантические сети широко применяются в информатике, например, для операций поис­ка по образцу, где в виде сетей представляется база данных. Ре­зультат такого поиска можно изобразить графом. Используют­ся сети и для графической ил­люстрации системы отношений базы данных.

Широко применяются сети для графического изображения различных логических схем в тео­рии автоматов, например схемы с памятью, у которых каждый узел - функция алгебры логики

Для формального описания совокупности процессов, протека­ющих одновременно, используют сети Петри. Они представляют собой ориентированные графы, состоящие из вершин двух видов: некоторых позиций и переходов, причем позиции изображают кружочками, а переходы - «планками»

Сети Петри предназначены для описания действия дискретных процессов во времени. Такие сети дают возможность моделировать ситуации протекания параллельных процессов, прослеживать возможные варианты их взаимодействия, выявлять нежелательные ситуации. Также в виде сетей изображаются схемы устройств, например ра­диоприемника или телевизора.

Сети получили широкое практическое применение потому, что они являются естественным и удобным способом изображе­ния и дальнейшего анализа различных сложных систем.

С помощью графов-деревьев решают задачи планирования (де­рево целей, дерево переборов вариантов).

Графы используют так­же для иллюстрации классификаций в различных областях зна­ний при построении иерархическихструктур сложных систем. Такие графы часто называют блок-схемами.

Примеры блок схем

Так как иерархические струк­туры представляют собой подчи­ненные отношения (подмножества), то графически их можно изоб­разить либо в виде графа-дерева, либо с помощью кругов Эйлера

Аналогично устроена лю­бая административно-территориальная структура: республика, области, районы, населенные пункты. По путям этих деревьев дви­жутся информационные потоки: сверху вниз - распоряжения, руководящие указания, снизу вверх - отчеты о работе, оператив­ная информация. Так как путь от листа к корню единственный, то его можно использовать для опознания компонентов системы.

Например, почтовый адрес представляет собой «путь в дереве», аналогичный административно-территориальному. В разделе "Кому" указывается страна, республика, область, район, населенный пункт, улица, дом, квартира.

Аналогично классифицируют объекты в любой науке. Получаемая классификация служит примером иерар­хической структуры. Например, в биологии: класс, отряд, семей­ство, род, вид.

Соответствующий граф содержит элементы разных уровней, корень - класс, а листья - отдельные виды животных.

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

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

Задание. Изобразить с помощью блок-схемы иерархическое представление видов вычислительных машин. Вычислительные машины делятся на аналоговые, цифровые, комбинированные. Цифровые машины делятся смешанные, оптоэлектрические, механические, электронные