Главная > Документ


Поурочные планы по теме

«Алгоритмы на графах»

Блок 1

Тема:Представление информации в форме графа

Цель: Познакомить учащихся с понятием графа, историей возникновения и развития теории графов, представлением информации в форме графа и представлением графа в памяти компьютера.

Тип занятий: Формирование новых знаний.

План:

I. Объяснение нового материала:

  1. Вводные понятия.

  2. История возникновения и развития теории графов.

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

I. Объяснение нового материала:

1. Вводные понятия.

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

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

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

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

Две вершины, соединенные ребром (дугой) называются смежными.

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

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

2. История возникновения и развития теории графов.

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

Первая работа по теории графов, принадлежащая известному швейцарскому математику Л. Эйлеру, появилась в 1736 г. Толчок к развитию теория графов получила на рубеже ХIX и ХХ столетий, когда резко возросло число работ в области топологии и комбинаторики, с которыми ее связывают самые тесные узы родства. Графы стали использоваться при построении схем электрических цепей и молекулярных схем. Как отдельная математическая дисциплина теория графов была впервые представлена в работе венгерского математика Кенига в 30-е годы ХХ столетия.

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

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

С полным основанием можно сказать, что теория графов является одним из простейших и наиболее элегантных разделов современной математики с широкой областью применения. Имея в своей основе простейшие идеи и элементы: точки, соединенные линиями, теория графов строит из них богатое многообразие форм, наделяет эти формы интересными свойствами и в результате становится полезным инструментом при исследовании самых разнообразных систем. Кроме того, теория графов внесла большой вклад в разработку методов анализа широкого круга комбинаторных проблем. Если помимо основных чисто структурных соотношений в графе задаются некоторые количественные характеристики точек и линий, образующих граф, тогда вместо понятий графа можно использовать понятие сеть. В качестве примеров можно назвать электрические сети, сети выполнения работ в проектах сети потоков. При этом ребром сети ставятся в соответствие определенные количественные характеристики энергии, затрат и потока.

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

Определим граф G как пару (V,E), где V – конечное множество вершин, а Е – множество неупорядоченных и упорядоченных пар вершин. Мощности множеств V и E обозначим буквами N и M. (Мощность конечного множества совпадает с количеством элементов в нем.) Неупорядоченная пара вершин называется ребром, а упорядоченная пара – дугой. Граф, содержащий только ребра, называется неориентированным; граф, содержащий только дуги – ориентированным или орграфом. Единственное структурное различие между ориентированным и неориентированным графом состоит в том, что в первом случае граничные вершины ребра образуют упорядоченную пару, а во втором неупорядоченную. Говорят, что ребро (U, V) соединяет вершины U и V. Вершины, соединенные ребром, называются смежными. Ребра, имеющие общую вершину, также называются смежными. Ребро и любая из его 2-х вершин называютя инцидентными. Каждый граф можно представить на плоскости множеством точек, соответствующих вершинам, которые соединены линиями, соответствующими ребрам и дугам. Направление дуги графа на рисунке обозначается стрелкой. В 3-х мерном пространстве любой граф можно представить таким образом, что линии не будут пересекаться.


рис.1

На рис.1 представлены различные изображения одного и того же графа.

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

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

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

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

Для хранения перечня ребер необходим 2- мерный массив Х размерности 2*М. Каждая строка массива описывает одно ребро.

Пример:



l1 V1 V3

l2 V1 V2

l3 V1 V2

l4 V2 V3

Матрица смежности – это двумерный массив А размерности N*N

1, если вершины i и j - смежные

A[i,j]=

0, если вершины i и j - несмежны


Пример: Данный граф можно представить в виде матрицы смежности:

V1 V2 V3 V4 V5 V6 V7 V8

V1 0 0 0 0 0 0 0 0

V2 1 0 0 0 0 0 0 0

V3 0 1 0 1 1 0 0 0

A= V4 0 0 0 0 1 0 0 0

V5 0 1 0 0 0 0 0 0

V6 0 0 0 0 0 0 1 1

V7 0 0 0 0 0 0 0 1

V8 0 0 0 0 0 0 0 0

Матрица инцидентности графа, имеющего n вершин и m ребер– это двумерный массив А размерности N*M

1, если j-е ребро инцидентно i-й вершине

A[i,j]=

0, если j-е ребро неинцидентно i-й вершине

e1 e2 e3 e4 e5 e6

v1 1 0 0 0 0 0

v2 1 1 0 0 0 1

v3 0 1 1 0 1 0

v4 0 0 1 1 0 0

v5 0 0 0 1 1 1

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

• шинная конфигурация, когда к незамкнутому каналу с некоторыми интервалами подключаются отдельные абоненты (К), информация от абонента-источника распространяется по каналу в обе стороны;

• кольцевая конфигурация, когда каждый абонент непосредственно связан с двумя соседними абонентами, а информация передаётся по замкнутому кольцу, чаще всего в одну сторону;

• звездообразная конфигурация, в центре которой находится центральный коммутатор (ЦК), который последовательно опрашивает абонентов и предоставляет им право на обмен данными;

• древовидная конфигурация образуется подсоединением нескольких простых каналов связи к одному магистральному;

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

Рис. 2

Различные типы

конфигураций Шинная

локальных

вычислительных

сетей

Кольцевая

Звездообразная

Полносвязная

Древовидная

Задания:

  1. Описать двумя способами различные типы конфигураций ЛВС.

  2. Описать двумя способами графы на рис 1.

  3. Привести пример графа и описать его двумя способами.

Практическая работа.

Задание 1 Разработать программы ввода описания графа для каждого способа. Для контроля ввода обеспечить вывод каждого описания на экран монитора.

Задание 2 Разработать процедуры преобразования способов описания графа.

Задание 3. Создать граф по его матрице смежности.

Поурочные планы по теме

«Алгоритмы на графах»

Блок 2

Тема блока:Поиск в графе.

Цель: Познакомить учащихся с алгоритмами просмотра вершин графа..

Тип занятий: Активизация и формирование новых знаний.

План:

  1. Активизация знаний

  2. Объяснение нового материала.

а)Поиск в глубину.

б)Поиск в ширину.

в)Деревья.

  1. Активизация знаний:

Вопросы:

1. Дайте определение графа.

  1. 2. Какие ребра называются смежными?

  2. 3. Какой граф называется взвешенным?

  3. 4. Где в жизни можно наблюдать использование графов?

5. Какие способы описания графа используются?

  1. Объяснение нового материала.

Множество алгоритмов на графе требует просмотра вершин графа.

а) Алгоритм поиска в глубину

Идея метода

Просмотр вершин графа начинается с некоторой вершины v. Выбирается вершина u, смежная с v. Процесс повторяется с вершины u. Если на очередном шаге мы работаем с вершиной q и нет вершин, смежных с q и не просмотренных ранее (новых ), то возвращаемся из вершины q к вершине, из которой мы попали в q. Если это вершина v, просмотр закончен. Для фиксации признака, просмотрена вершина графа или нет, требуется структура данных типа:

Nnew: array[1..N] of boolean;

Пример

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


(a) рис. 1 (б)

Реализация алгоритма

(Массив Nnew и A глобальные)

procedure PG(v:integer);

var j:integer;

begin

Nnew[v]:=false; write (v:3);

for j:=1 to N do

if (A[v,j]<>0) and Nnew[j] then Pg(j);

end;

Фрагментвызывающегоалгоритма

FillChar(Nnew,SizeOf(Nnew),true);

for i:=1 to N do if Nnew[i] then Pg(i);

Рассмотрим нерекурсивную реализацию этого алгоритма. А-матрица смежности; Nnew – массив признаков вершин (новая/просмотренная). Номера просмотренных вершин запоминаются в стеке St, указатель стека – переменная yk.

procedure PG1(v:integer);

var St:array[1..N] of integer;

yk:integer;

t,j:integer;

pp:boolean;

begin

FillChar (St,SizeOf (St), 0); yk:=0;

Inc(yk); St[yk]:=v; Nnnew[v]:=false;

while yk<>0 do

begin {пока стек не пуст}

t:=St[yk]; {выбор вершины из стека}

j:=0; pp:=false;

repeat

if (A[t,j+1]<>0) and Nnnew[j+1] then pp:=true else Inc(j);

until pp or (j>=N);

{найдена новая вершина или все вершины, связанные с данной, просмотренны}

if pp then

begin

Inc(yk); St[yk]:=j+1;

Nnew[j+1]:=false; {добавляем вершину в стек}

end

else Dec(yk); {убираем вершину из стека}

end;

end;

Работа алгоритма на примере графа приведенного выше. Первое обращение к PG(1).

yk

St

Nnew

t

1

1

f t t t t t t t t

1

2

3 1

f t f t t t t t t

3

3

2 3 1

f f f t t t t t t

2

2

3 1

f f f t t t t t t

3

3

6 3 1

f f f t t f t t t

6

4

7 6 3 1

f f f t t f f t t

7

5

5 7 6 3 1

f f f t f f f t t

5

6

4 5 7 6 3 1

f f f f f f f t t

4

5

5 7 6 3 1

f f f f f f f t t

5

6

8 5 7 6 3 1

f f f f f f f f t

8

5

5 7 6 3 1

f f f f f f f f t

7

5

9 7 6 3 1

f f f f f f f f f

9

4

7 6 3 1

f f f f f f f f f

6

3

6 3 1

f f f f f f f f f

3

2

3 1

f f f f f f f f f

1

1

1

f f f f f f f f f

-

0

б) Алгоритм поиска в ширину

Идея метода

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

Пример

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

(а) (б)

рис. 2

Процедура реализации данного метода.

procedure PW(v:integer);

var Og:array[1..N] of 0..N; {очередь}

yk1, yk2: integer; {указатели очереди, yk1 - запись; yk2 - чтение}

j:integer;

begin

FillChar(Og,SizeOf(Og),0); yk1:=0;yk2:=0; {начальная инициализация}

Inc(yk1); Og[yk1]:=v; Nnew[v]:=false; {в очередь - вершину v}

while yk2

begin

Inc(yk2); v:=Og[yk2]; write (v:3); {берем элемент из очереди}

for j;=1 to N do {просмотр всех вершин связанных с вершиной v}

if (A[v,j}<>0) and Nnew[j] then

begin {если вершина ранее не просмотрена}

Inc(yk1); Og[yk1]:=j; Nnew:=false; {заносим ее в очередь}

end;

end;

end;

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

const nmax = 500;

type ptr = ^el; (указатель на элемент списка) el = record

i: integer; next: ptr end;

var a, b: array[1..nmaxJ of ptr;

vert: array[1..nmax] of boolean;

p: ptr;

i, j, k, m, n, cnt: integer;

procedure d_f_s(v: integer);

begin

vert[v] := false;

while a[v] о nil do

{пока список вершин, связанных с v, не исчерпан} begin

if vert[a[v]^.i] then d_f_s(a[v]^.i) ;

{переходим к следующему элементу списка} a[v] := a[v]^.next

end

end;

procedure b_f_s(v: integer) ;

var p,q: ptr;

begin

vert[v] := false;

p := a[v]; {указатель на начало очереди}

q := b[v]; {указатель на конец очереди}

while p о nil do {пока очередь не исчерпана}

begin

if vert[p^.i] then begin

vert[p^.i] := false;



Скачать документ

Похожие документы:

  1. Представление информации в форме графа

    Документ
    ... графах» Блок 1 Тема: Представлениеинформации в формеграфа Цель: Познакомить учащихся с понятием графа, историей возникновения и развития теории графов, представлениеминформации в формеграфа и представлениемграфа ...
  2. Примерные программы по информатике и икт для 8-9 классов и 10-11 классов (базовый уровень) федеральный компонент государственного стандарта общего образования 8-9 класс (105 часов) информация и информационные процессы (4 часа)

    Документ
    ... текстовой информации. Представление данных ;в табличной форме. Представлениеинформации в формеграфа. Представление зависимостей в виде формул. Представление последовательности действий в форме блок-схемы ...
  3. Новосибирск 2012 Информация и информационные процессы

    Программа
    ... текстовой информации. Представление данных в табличной форме. Представлениеинформации в формеграфа. Представление зависимостей в виде формул. Представление последовательности действий в форме блок-схемы ...
  4. «01 » сентября 2010 года «01»сентября 2010 года Образовательная программа

    Программа
    ... текстовой информации. Представление данных в табличной форме. Представлениеинформации в формеграфа. Представление зависимостей в виде формул. Представление последовательности действий в форме блок-схемы ...
  5. «методы визуализации информации при помощи графов»

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

Другие похожие документы..