Сибирский государственный технологический  университет

     Кафедра информационных технологий 
 

     ЗАДАНИЕ

     НА  КУРСОВУЮ РАБОТУ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ 
 

     Студент        Якименко Андрей Владимирович

     Факультет   ФАИТ   Группа 21-8

     Тема: Исследование и программная реализация методов и алгоритмов теории          графов. 

       Вариант 41

                    Алгоритм обхода графа в ширину.

        

       Предложенную задачу сформулировать в терминах теории графов и подобрать соответствующий алгоритм.

     Реализовать выбранный алгоритм на языке Delphi.

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

     Календарный план выполнения работы 

     1-5.04.11-      формализация программы

     6-10.04.11-    уточнение входной и выходной информации

     11-18.04.11-  составление схемы алгоритма

     19-30.04.11-  проведение расчетов

     1-10.05.11-    отладка и тестирование

     11-22.05.11-  оформление пояснительной записки

     25.05.11        защита курсовой 

            Задание выдано    01.04.11

                      Руководитель           Доррер А.Г.

                                                     

 

Содержание

 
Реферат

     Расчетно-графическая  работа представляет собой реализацию алгоритма обхода графа в ширину. Расчет выполнен с помощью языка программирования Delphi 7.

     Пояснительная записка включает в себя 14 страниц текста, схему алгоритма, 3 использованных литературных источника.

     Ключевые  слова:  граф, ширина графа, обход графа

     Цель  работы – овладение навыками работы с алгоритмом обхода графа в ширину.

     Метод исследования – теория графов, алгоритмизация, язык программирования Delphi.

     Данная  программа позволяет:

     1) ознакомиться с работой алгоритма обхода графа в ширину;

     2) сделать обход графа в ширину для любого графа до 6 вершин;

     3) провести тестирование алгоритма. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

       
Введение

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

 

     1 Алгоритм обхода графа в ширину

     Пусть G=({v1,...,vn}, {Lv1,...,Lvn}) - упорядоченный граф.  Выберем некоторую начальную вершину vs,  s in  Nn  и предположим, что Lvs=(w1,...,wk).

     Первые (k+1) членов последовательности  t  определяются  следующим образом:  v/sigma(1)=vs, v/sigma(2)=w1, ..., v/sigma(k+1)=wk, а v/sigma(k+1+i) является i-й вершиной из списка Lw1,  не входящей в t. Когда исчерпан список Lw1,  процесс продолжается над списком Lw2 и т.д. Процесс прекращается, когда все вершины, достижимые из v/sigma(1), содержатся  в  t.  Замечания о единственности,  связности и числе обходов в глубину также применимы к обходу в ширину.

     

       
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     2 Решение задачи

     2.1 Входная и выходная информация

 

     Входная информация в данной программе:

• размерность матрицы;
• матрица смежности;

 

     Выходная  информация:

• Обход графа в ширину

       
 2.2 Схемы алгоритма

     

     Рисунок 1 – Алгоритм выполнения программы

         

 

     2.3 Текст программы

procedure TForm1.FormCreate(Sender: TObject);

begin

  raz:=strtoint(r.Text)+1;

  sv.RowCount:=3;

  sv.ColCount:=3;

  //Заполнение  матрицы нулями

  for i:=1 to raz do

  for j:=1 to raz do

  sv.Cells[j,i]:=inttostr(0); 

  //вывод вершин

  for i:=1 to raz do

  begin

    sv.Cells[0,i]:='V'+inttostr(i);

    sv.Cells[i,0]:='V'+inttostr(i);

  end;

end; 

procedure TForm1.rChange(Sender: TObject);

begin

  raz:=strtoint(r.Text)+1;

  if raz>7 then

  begin r.Text:='6';

  raz:=7;

  end;

  if raz<2 then

  begin r.Text:='1';

  raz:=2;

  end;

  sv.RowCount:=raz;

  sv.ColCount:=raz;

  for i:=1 to raz do

  for j:=1 to raz do

  sv.Cells[j,i]:=inttostr(0); 

  //вывод вершин

  for i:=1 to raz do

  begin

    sv.Cells[0,i]:='V'+inttostr(i);

    sv.Cells[i,0]:='V'+inttostr(i);

  end;

end; 

procedure TForm1.Button1Click(Sender: TObject);

begin

//обнуление переменных

  t:=0; 

  step:=0;

  p:=0;

  m:=1;

  bol:=false;

  raz:=strtoint(r.Text);

  //проверка правильности ввода матрицы

  for i:=1 to raz do

  for j:=1 to raz do

  begin

  if ((sv.Cells[i,j]<>sv.Cells[j,i]) or (sv.Cells[i,i]<>'0'))

  then

  begin

  ShowMessage('  Матрица смежности введена НЕВЕРНО!  ');

  exit;

  end;

  end;

  //Обход графа  в ширину

  label3.Visible:=true;

       for i:=1 to raz do

       for j:=1 to raz do

       begin

       a[i,j]:=strtoint(sv.Cells[i,j]);

       end;

      i:=2;

      for j:=1 to raz do

      begin

        prov[j]:=0;

        if a[i,j]=1 then

        begin

          b[j]:=j;

          prov[j]:=j;

          label4.Visible:=true;

          label4.Caption:=label4.Caption+'V'+inttostr(j)+' ,';

          inc(m);

        end;

      end;

      if m=raz then exit;

      prov[2]:=2;

      for p:=1 to raz do

      if b[p]<>0 then

      begin

        i:=p;

        for j:=1 to raz do

        begin

          if a[i,j]=1 then

          begin

            for t:=1 to raz do 

            if j=prov[t] then bol:=true;

            if bol=false then

            begin

              label5.Visible:=true;

              label5.Caption:=label5.Caption+'V'+inttostr(j)+' ,';

              inc(m);

              prov[j]:=j;

            end;

            bol:=false;

          end;

        end;

      end;

      if m=raz then exit;

      for p:=1 to raz do

      begin

        if prov[p]=0 then label6.Caption:=label6.Caption+'V'+inttostr(prov[j])+' ';

        label6.Visible:=true;

      end;

end;

       
2.4 Протокол контрольного  расчета

     

     Рисунок 2 – Общий вид программы с  выведенным результатом

 

     3 Инструкция по  работе с программой

• После запуска  программы, на экране появляется матрица смежности.
• Указываем размерность матрицы
• Заполняем матрицу
• Если матрица смежности была введена неправильно, программа выдаст сообщение об ошибке, нажимаем «ОК» и исправляем матрицу
• Нажимаем на кнопку «Рассчитать»
• Готово.

       
Заключение

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

       
Библиографический список

1. Иванилова Т.Н. Дискретная математика. Ч.1,2.-Красноярск: КГТА,1995.
2. Новиков Ф.А. Дискретная математика для программистов. – М.: Питер, 2002.
3. Иванилова Т.Н. Дискретная математика. Сборник заданий для выполнения курсовых работ, 2004.