БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Выпускная работа по
«Основам информационных технологий»

Магистрант

кафедры УМФ

Петрович Роман Александрович

Руководители:

профессор, доктор

физико-математических наук Тышкевич Регина Иосифовна,

доцент Кожич Павел Павлович

Минск – 2009 г.

Список обозначений ко всей выпускной работе

ИТ – информационные технологии.

ЭВМ – электронно-вычислительная машина.

Реферат на тему «Применение информационный технологий в теории графов».

Введение

Рассматриваемый реферат посвящен применению информационных технологий в теории графов. В наше время теория графов приобретает все возрастающий интерес у специалистов самых различных областей науки и техники. Эта привлекательность объясняется не только очень широким разнообразием возможностей ее применения, но и красотой результатов, достигаемых простыми средствами. Известно, что само появление теории графов восходит к началу XVIII века к задаче «О Кёнигсбергских мостах». Эта задача была решена великим математиком того времени Леонардом Эйлером. В современной математике его результат известен как «Лемма о рукопожатиях». Следующий раз про теорию графов «вспомнили» лишь в начале XX века, найдя ее применение в химии (описание строений соединений углеродов), физике (электрические цепи) и конечно же в самой математике. Действительно, в рамках теории графов имеется множество различных направлений; результаты ее формулируются с привлечением понятий теории множеств, топологии, алгебры, но в тоже время методы теории графов нельзя рассматривать как простую совокупность методов этих разделов математики.

Теория графов и гиперграфов является эффективным аппаратом формализации современных инженерных и научных задач, как уже сказано, в различных областях знаний. Язык теории графов удобен при проведении системных исследований, описании организации генетических систем. В последнее время большое применение нашла теория графов в современной вычислительной технике и кибернетике: в теоретическом программировании, при проектировании на ЭВМ и сетей ЭВМ, баз данных, систем логического управления [1].

Глава 1. Некоторые сведения из теории алгоритмов

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

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

Память абстрактной вычислительной машины состоит из неограниченного числа ячеек, имеющих адреса 1, 2, 3, ..., n. Причем, ко всем ячейкам памяти этой машины есть прямой доступ.

При анализе алгоритмов наибольший интерес представляет зависимость времени работы алгоритма от числа вершин и (или) ребер графа. Cчитается, что любое число, независимо от его величины, можно разместить в одной ячейке памяти и каждая ячейка может содержать только одно число.

Рассмотрим теперь представление информации в памяти машины. Всякая конечная последовательность элементов произвольной природы называется списком, а число элементов списка — его длиной. Элементами этого списка могут быть числа, буквы алфавита, векторы, матрицы и т. п. В той ситуации, когда, каждый элемент списка помещается в одной ячейке, этот список будем размещать в n последовательных ячейках памяти, где n — длина списка. Такое представление списка обычно называется последовательным, и далее используется только это представление.

Пусть А =||A_i,j|| — матрица порядка n.

A^*=(A₁₁, A₁₂, …, A_1n, A₂₁, A₂₂,…, A_2n, …, A_n1, A_n2,…, A_nn) — список ее элементов по строкам. Принцип «одно число — одна ячейка» означает, что матрица порядка n занимает n²ячеек памяти.

Рассмотрим теперь представление графа G в памяти машины. Пусть VG={v₁,v₂,…,v_n}. Будем пользоваться тремя способами представления.

Первый — задание графа матрицей смежности. Если граф взвешенный и w(x, у) обозначает вес ребра xу, то вместо матрицы смежности используется матрица весов W(G)=W. У этой матрицы W_ij=w(v_i, v_j), если v_i,v_jÎEG. Если же v_iv_jне является ребром графа G, то полагаем W_ij=0 или W_ij=∞ — в зависимости от задачи, которую предстоит решить. Из сказанного выше о представлении матрицы в машине следует, что такой способ задания графа требует |G|² ячеек памяти. Стоит отметить, что в рассматриваемом примере весами ребер могут быть любые вещественные числа.

Второй способ — задание графа списком ребер VE={e₁,e₂,…,e_m}, где m=|EG|, e_iÎEG. Поскольку ребро графа можно хранить, используя две ячейки (по одной на каждую концевую вершину), то для хранения всего списка Е достаточно 2т ячеек. Если граф взвешенный, то под каждый элемент списка Е можно отвести три ячейки — две для ребра и одну для его веса, т. е. всего потребуется Зm ячеек.

И, наконец, последний способ, который будет использоваться, — представление графа списками смежности. При таком способе каждой вершине v_i, ставится в соответствие список N_vi вершин, смежных с v_i. Под этот список достаточно отвести deg(v_i)+1 ячеек — по одной на каждый элемент и одну ячейку для обозначения конца списка. Кроме того, формируется список N={N₁,N₂,…,N_m}, где N_i, — номер ячейки, в которой хранится первый элемент списка N_vi. Следовательно, такой способ

представления графа требует

ячеек памяти. Если граф G взвешенный, то дли каждой вершины v_j, списка N_viотводится дополнительно одна ячейка, содержащая число w(v_i, v_j).

Хотя представление графа списком ребер является наиболее экономным «по памяти», оно имеет существенный недостаток. Чтобы определить, содержит ли граф данное ребро, надо просматривать поочередно элементы этого списка, а это может потребовать около 2т элементарных операций. Если же граф задан списками смежности, вычислительные затраты составят не более n+1 таких операций. Представление графа матрицей смежности, требующее наибольших затрат памяти, обеспечивает «прямой доступ» к ребрам графа. Узнать, содержит ли граф ребро v_iv_jможно, вычислив адрес k = in + j и сравнив М(k) c нулем, где М — массив, в котором построчно размещена матрица смежности графа.

«Применение информационный технологий в теории графов» (стр. 1 из 5)

Оглавление

Список обозначений ко всей выпускной работе

Реферат на тему «Применение информационный технологий в теории графов».

Введение

Глава 1. Некоторые сведения из теории алгоритмов