Лабораторные работы Вычислительные системы
  • Регистрация
1 1 1 1 1 1 1 1 1 1 Рейтинг 0.00 (0 Голоса)

2. Структуры представления графов в памяти ЭВМ

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

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

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

Представление графов в памяти ЭВМ существенно зависит от типов структур данных, допускаемых используемым алгоритмическим языком и типов ЭВМ.

2.1. Представление графа с помощью матрицы смежности

Любая программная система оценивается, прежде всего, по двум критериям:

а) быстродействию, величина которого должна стремиться к увеличению;

б) объему памяти, величина которого должна стремиться к уменьшению.

Задача, решаемая в рамках САПР – найти оптимальное соответствие между объемом памяти и быстродействием.

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

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

На рисунке 6 изображен ориентированный граф. Представим этот граф матрицей смежности.

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

Рисунок 6 – Ориентированный граф

 

Граф невзвешенный, поэтому, каждая ячейка матрицы должна отражать только наличие или отсутствие дуги и может принимать два значения: например, 0 или 1. Примем Мi, j = 1, если между вершинами i и j дуга существует, и Мi, j = 0, если между этими вершинами дуги нет.

Количество ячеек или элементов в матрице смежности равно n2. размерность матрицы определяется по формуле

, (1)

где n– число вершин в графе;

L – размер одного элемента матрицы.

М 
 1 2 3 4
i 1 0 1 
 2 0 1 1
 3 1 1
 4 1 
 j

 

минимальная ячейка памяти, с которой компьютер выполняет операцию – 1 байт, поэтому размер одного элемента матрицы в оперативной памяти будет равен 1 байту, (L=1байт).

Тогда размер матрицы будет составлять n2 байт.

Для графа, представленного на рисунке 6, n = 4 и, соответственно R = 16 байт.

Если учесть, что для кодирования 0 и 1 достаточно всего 1 бита, то длина каждого элемента матрицы в оперативной памяти можно выделить 1 бит (L=1 бит), тогда размерность матрицы в битах R=16 бит = 2 байта. Сравнивая две величины R и R, характеризующие одну и ту же математическую модель, делаем вывод, что в первом случае оперативная память используется нерационально. Так как, выделив байт (т. е. 8 бит) для одного элемента матрицы, реально используется только один бит.

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

Подробнее рассмотрим битовую форму представления графа на конкретном примере для нашего графа.

Представление может быть либо по строкам, либо по столбцам. Мы будем представлять по строкам. Строим одномерный битовый вектор из 16 ячеек. Запишем информацию построчно.

 

СКАЧАТЬ  Struktury predstavlenija grafov v pamjati JeVM.doc

Добавить комментарий


Защитный код
Обновить

По темам:

История Украины

Культурология

Высшая математика

Информатика

Охотоведение

Статистика

География

Военная наука

Английский язык

Генетика

Разное

Технологиеские темы

Украинский язык

Филология

Философия

Химия

Экология

Социология

Физическое воспитание

Растениевосдство

Педагогика

История

Психология

Религиоведение

Плодоводство

Экономические темы

Бухгалтерские темы

Маркетинг

Иностранные языки

Ветеринарная медицина

Технические темы

Землеустройство

Медицинские темы

Творчество

Лесное и парковое хозяйство