- •Оглавление
- •Предисловие
- •1. Теоретико‑множественные основания дисциплины
- •1.1. Понятия и аксиомы теории множеств
- •1.2. Декартовы произведения, отношения и отношение эквивалентности
- •1.3. Понятия образа, прообраза, функции и отображения на конечном множестве. Аксиома выделения.
- •1.4. Аксиомы степени и бесконечности. Мощности и кардинальные числа множеств
- •1.5. Счетные и континуальные множества
- •1.6. Ординалы и трансфиниты. Аксиома выбора и континуум‑гипотеза
- •2. Основы математической логики
- •2.1. Высказывания и функции на высказываниях
- •2.2. Операции математической логики
- •2.3. Понятие формулы и свойства операций
- •2.4. Разложения булевых функций. Принцип двойственности. Совершенные нормальные формы.
- •2.5. Понятие полноты системы булевых функций
- •2.5. Исчисление предикатов
- •2.6. Введение в методы теории доказательств
- •1 Если X a,
- •0 Если X a.
- •1 Если X a,
- •0 Если X a.
- •3. Комбинаторика
- •3.1. Размещения
- •3.2. Размещения без повторений
- •3.3. Перестановки, подстановки и их свойства
- •3.4. Сочетания, структура соединений
- •3.5. Свойства биномиальных коэффициентов
- •Структура соединений
- •3.6. Понятие производящей функции
- •3.7. Соединения с повторениями
- •3.8. Разбиения множеств
- •3.9. Разбиения чисел
- •3.10. Композиции чисел
- •4. Основы теории графов
- •4.1. Основные понятия и определения
- •4.2. Графы и бинарные отношения
- •4.3. Понятие изоморфизма и изоморфизм плоских графов
- •4.4. Степени вершин графа
- •4.5. Представление графов матрицами
- •4.6. Представление графов списками инцидентности. Оценка пространственной сложности алгоритмов.
- •4.7. Маршруты, цепи, циклы и связность
- •4.7. Эйлеровы циклы и цепи
- •4.9. Гамильтоновы циклы. Оценка временной сложности алгоритмов
- •4.10. Деревья
- •4.11. Раскраска вершин и теорема Шеннона об информационной емкости графа
- •4.12. Раскраска ребер графа и теоремы о хроматическом классе
- •Ответы и решения
- •Список литературы
4.6. Представление графов списками инцидентности. Оценка пространственной сложности алгоритмов.
Применение компьютерных технологий, связанных с решением задач на графах, породило новые способы представления графов. Это связано с тем, что, матричное описание графов, будучи весьма привлекательным с точки зрения теоретических доказательств, приводит к неоправданно большому расходу оперативной памяти компьютера.
Под пространственной характеристикой сложности алгоритма понимают оценку О(f(n1, n2, …, nk)) требуемой памяти компьютера в зависимости от мощностей n1, n2, …, nk множеств исходных данных при неограниченном увеличении этих мощностей.
По определению классического анализа O(f(x)) вводится следующим образом.
Пусть x0 — некоторое предельное значение.
Если для функций и g(x) существуют такие постоянные A > 0 и δ > 0, что
|g(x)| ≤ A |f(x)| при |x - x0| < δ, x ≠ x0, то говорят, что g является ограниченной по сравнению с f функцией в некоторой окрестности точки x0 и пишут
g(x) = O(f(x)) при x → x0.
Последнее выражение читается следующим образом: «g(x) есть O большое от f(x) при x стремящемся к x0».
Таким образом, выражение O(f(x)) представляет асимптотическую оценку, которая имеет место лишь в некоторой окрестности x0.
Естественным образом это определение переносится и на случай x → ∞, что представляет теоретический интерес при оценке сложности алгоритмов.
В этом случае смысл асимптотической оценки состоит в том, что для некоторой быть может сложной в аналитическом описании функции g(x) находят сравнительно простую и наглядную асимптотическую оценку f(x). По виду этой функции и судят о сложности алгоритма.
Так широко известен следующий ряд функций f(x), в котором каждая из последующих функций опережает рост предыдущей на бесконечности:
1, log (x) , x, x log (x), x2, …, xm (m — больше нуля), cx (c > 0), x! (при натуральном x), xx (x > 0) и другие.
Символ О(f(x1, x2, …, xk)) функций многих переменных вводится аналогично тому, как и для функций одного переменного.
На практике при оценке пространственных затрат алгоритмов функцию О(f(n1, n2, …, nk)) определяют как асимптотически потребное число ячеек памяти при n1, n2, …, nk → ∞.
При оценке пространственной сложности размещения графов имеем f(nv, nu), где nv, nu — соответственно число вершин и ребер графа.
Легко видеть, что оценка пространственной сложности алгоритма зависит от способа представления графа. Так для чтения либо записи графа, представленного матрицей смежности порядка nv, нам потребуется Anv2 байтов для размещения элементов матрицы плюс некоторое ограниченное число переменных и констант для инициализации данных при выполнении опрераций чтения - записи. Таким образом, в этом случае пространственные затраты представляются некоторым полиномом степени не выше второй, коэффициенты которого, вообще говоря, плохо поддаются учету.
Используя асимптотическую оценку, видим, что полученный полином, асимптотически приближается функцией O(nv2). Этого вполне достаточно, чтобы иметь представление о размерности нашей задачи.
Аналогично, в случае представления графа матрицей инцидентности, имеем асимптотическую оценку O(nunv). Фактически она также сводится к предыдущей поскольку, если граф имеет хотя бы одно ребро, то всегда найдется такая постоянная A > 0, что Anu = nv.
Исследования показали, что пространственные затраты можно оценивать не квадратом, а — первой степенью, если изменить способ представления графов. В качестве альтернативы был предложен способ, именуемый: представление графов списками инцидентности.
Такое представление в программировании базируется на понятиях указателя, записи и списка.
Пусть имеем некоторое множество переменных: A, B, C, … . Поставим каждой из этих переменных в однозначное соответствие некоторое число. Это число будем именовать указателем на переменную, например А, и обозначать @A в формулах либо →А на графиках. Указатель на несуществующую переменную условимся обозначать специальным символом — nil.
Так при размещении данных в памяти компьютера указатель представляет физический адрес ячейки памяти, где размещена соответствующая переменная.
Под записью понимают поименованное упорядоченное множество переменных. Например, переменные ‹x, y, z› можно поименовать так: A = ‹x, y, z›. При этом предполагается, что переменные x, y или z представляют любые математические объекты, например, скаляры, векторы, и т.д.. Эти переменные именуются полями записи. Для того, чтобы адресоваться, скажем, к полю x записи A применяют обозначение: A.x.
Под списком понимают упорядоченную последовательность записей, в которой каждая предыдущая запись содержит в качестве одного из полей указатель на последующую запись. Кроме того определен указатель на первую запись как на начало списка, а последняя в качестве поля указателя содержит nil. Таким образом, список любого числа записей полностью определяется указателем на его начало.
Списки инцидентности строятся следующим образом. Имеется общая таблица начала, в которой представлены указатели на начало списков каждой из вершин графа G. Каждая запись имеет минимум два поля. В одно из них помещается номер вершины, смежной с той, которая указана в таблице начала, а в другую — указатель на следующую запись. Каждая последующая запись имеет аналогичную структуру. Она представлена полем вершины, смежной с таблицей начала и указателем на следующую запись. При этом, если вершина начала инцидентна кратным ребрам, то соответствующая смежная ей вершина должна повторяться в списке столько раз, какова кратность ребра. Таким же образом строятся все остальные списки для каждой из вершин таблицы начала.
Списки инцидентности на примере представления графа, изображенного на рисунке 4.9, представлены на рисунке 4.10.
Из описанного построения видно, что каждый список инцидентности представляет множество ребер, инцидентных данной вершине графа. Множество всех списков, отвечающих каждой из вершин некоторого графа G, представляет данный граф.
В теоретико‑множественной формулировке списки, соответствующие графу могут быть представлены упорядоченным семейством упорядоченных множеств, независимо от наличия неориентированных ребер.
В данном семействе порядковый номер списка соответствует номеру вершины графа, а элементы каждого из списков, определяют множество ребер, инцидентных данной вершине.
Например, граф, изображенный на рисунке 4.9, представляется следующим семейством:
v2, v3, , v2, v4, , v4,v6 , v5 .
v1 |
|
|
v2 |
|
|
v3 |
nil | ||
v2 |
nil |
|
| ||||||
v3 |
|
v2 |
|
v4 |
nil | ||||
v4 |
nil |
|
|
|
|
| |||
v5 |
|
v6 |
|
v4 |
nil | ||||
v6 |
|
v5 |
nil |
|
|
|
|
Рисунок 4.10
Такой способ представления графов обладает тем преимуществом, что общее количество числа ячеек памяти, необходимых для представления графа, определяется всего лишь как O(nv+nu). Кроме того, структура мобильна в отношении к преобразованиям графа, связанных с добавлением или уменьшением числа его ребер: ребро просто включается в список либо удаляется из списка.
Отметим, что в различных языках программирования имеются эффективные средства организации и обработки списков.