Представление графов в оперативной памяти

Существуют два способа представления графа G = (V, E) - в виде набора списков смежных вершин и в виде матрицы смежности.

Первый способ предпочтительней для разреженных графов, когда |E| много меньше |V|². Представление с помощью матрицы смежности удобнее использовать для насыщенных графов, когда |E| сравнимо |V|².

Представление графа G = (V, E) в виде списков смежности использует массив Adj из |V| списков, по одному для каждой вершины. Для каждой вершины список смежных вершин Adj [u] содержит в произвольном порядке все смежные с ней вершины v, для которых существует ребро (u, v) E. Граф, представленный с помощью списков смежности, называется L - графом.

Неориентированный граф в форме L- графа:

 

Ориентированный граф в форме L- графа:

 

Для неориентированного графа сумма длин всех списков равна удвоенному числу ребер, так как ребро (u, v) порождает элементы в списках вершины u и вершины v. Для орграфа сумма длин списков равна числу ребер. В обоих случаях количество памяти для представления графа оценивается как O(V + E).

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

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

Этого можно избежать в представлении с помощью матрицы смежности. Эта форма представления графа называется M- графом.

Неориентированный граф в форме M- графа:

 

Ориентированный граф в форме M- графа:

 

Элемент матрицы a_ij =1, если есть ребро или дуга (i, j) E и a_ij = 0 в противном случае.

Для орграфа и неориентированного графа матрицы требует O(V²) памяти.

Для неориентированного графа матрица смежности симметрична относительно главной диагонали. Поэтому достаточно хранить только элементы от главной диагонали и выше.

В матрице смежности вместо 0 и 1 можно хранить веса ребер w(u, v). Для отсутствующих ребер можно использовать специальное значение nil (0 или ).

Матрица смежности удобнее для небольших графов. Если не нужно хранить веса, то для элементов матрицы сме

Для взвешенного графа в структуру списков смежности или матрицы смежности заносятся веса ребер (весовая функция):

 

22) Графом (G, X) называется совокупность двух конечных множеств: множества точек, которые называются вершинами (X = {Х₁,...,Х_n}), и множества связей в парах вершин, которые называются дугами, или ребрами ((Х_i, Х_j) О G) в зависимости от наличия или отсутствия направленности связи.

Ребром называются две встречные дуги (Х_i, Х_j) и (Х_j, Х_i). На графе они изображаются одной линией без стрелки. Ребро, или дуга, конечные вершины которого совпадают, называется петлей.

Если на каждом ребре задается направление, то граф (G, Х) называется ориентированным. В противном случае граф называется неориентированным.

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

Матрицей инцидентности называется прямоугольная матрица с числом строк, равным числу вершин графа, и с числом столбцов, равным количеству ребер (дуг) графа. Элементы матрицы а задаются следующим образом: “1” ставится в случае если вершина v_i, инцидентна ребру u_j; “0” - в противном случае.

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

Путь из начальной вершины х_н к конечной вершине х_к - последовательность дуг, начинающаяся в вершине х_н О Х, заканчивающаяся в вершине х_к ОХ, и такая, что конец очередной дуги является началом следующей:

(х_н, х_i1)(х_i1, х_i2)(х_i2… х_ik)(х_ik, x_k) = (x_н, х_к).

 

Элементарный путь – путь, в котором вершины не повторяются.

Простой путь - путь, в котором дуги не повторяются.

Маршрут - последовательность ребер, составляющих, как и путь, цепочку.

Длина пути взвешенного графа определяется как сумма весов - его дуг. Если граф не взвешен, то можно считать веса дуг равными 1.

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

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

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

Пример:

Далее они встречаются все чаще и чаще, но само определение графа не дается. А жаль! Я думаю, детям интересно было бы познакомиться с этим понятием, научиться применять графы для решения задач. Конечно, каждый учитель может самостоятельно рассказать ребятам об Эйлере, о его исследованиях в области теории граф, да и сами учащиеся могли бы представить эту информацию в виде доклада или компьютерной презентации. Надо об этом подумать!!!

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

Когда я с детьми разбирала тему «Графы», мы изучали теорию, решали задачи и приводили примеры из жизни, отвечали на вопрос «Что можно изобразить в виде графа?», то учащиеся выяснили для себя, что практически любой пример или можно решить с помощью графа, или, изобразив граф, найти то или иное решение задачи. Они вспомнили, что в 5 классе у них была тема, где они решали примеры, используя блок- схемы (те же графы).

Сейчас они в 6 классе, но некоторые примеры предпочитают изображать в виде графа.

Пример:

Решение:

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

А можно одну и ту же задачку оформить по-разному:

Пример:

Гвозди, масса которых m кг, разложили в три ящика. В первый ящик положили 0,6 всех гвоздей, а во второй всех гвоздей. Сколько килограммов гвоздей положили в третий ящик? Найдите значение получившегося выражения при m=45.

Решение:

1 способ: (в виде таблицы)

Из таблицы легко составить выражение, упростив которое мы без труда найдем значение выражения:

2 способ: (в виде направленного графа)

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

24) Элементы теории массового обслуживания.

 

Теория массового обслуживания изучает системы массового

обслуживания (СМО) и сети массового обслуживания (СеМО).

Под системой массового обслуживания (СМО) понимают

динамическую систему, предназначенную для эффективного

обслуживания потока заявок (требований на обслуживание) при

ограничениях на ресурсы системы.

Модели СМО удобны для описания отдельных подсистем

современных вычислительных систем, таких как подсистема

процессор - основная память, канал ввода - вывода и т. д.

Вычислительная система в целом представляет собой совокупность

взаимосвязанных подсистем, взаимодействие которых носит

вероятностный характер. Заявка на решение некоторой задачи,

поступающая в вычислительную систему, проходит последовательность

этапов счета, обращения к внешним запоминающим устройствам и

устройствам ввода - вывода. После выполнения некоторой

последовательности таких этапов, число и продолжительность

которых зависит от трудоемкости программы, заявка считается

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

вычислительную систему в целом можно представлять совокупностью

СМО, каждая из которых отображает процесс функционирования

отдельного устройства или групы однотипных устройств, входящих в

состав сиистемы.

Совокупность взаимосвязанных СМО называется сетью массового

обслуживания (стохастической сетью).

Основными задачами, которые решаются в рамках теории

массового обслуживания, являются:

- задача анализа, т. е. определение количественных

характеристик СМО и СеМО при заданной структуре и заданных

параметрах элементов структуры;

- задача синтеза оптимальной структуры СМО или СеМО при

заданных характеристиках и ограничениях на параметры элементы

структуры