Электронный научный журнал

Информационно-коммуникационные технологии
в педагогическом образовании

12+

РЕШЕНИЕ ОЛИМПИАДНЫХ ЗАДАЧ ПО ПРОГРАММИРОВАНИЮ, В КОТОРЫХ ИСПОЛЬЗУЮТСЯ ГРАФЫ

Авторы: Д. О. Каппес, М. С. Можаров
Раздел: Использование информационно-коммуникационных технологий в общем, дополнительном, среднем профессиональном и высшем образовании

УДК 373.519.17

Д. О. Каппес, М. С. Можаров

D. O. Kappes, M. S. Mozharov

Каппес Даниил Олегович, студент группы ИНп-15-1, НФИ КемГУ, г. Новокузнецк.

Можаров Максим Сергеевич, к.п.н., профессор, зав. кафедрой информатики и общетехнических дисциплин, НФИ КемГУ, г. Новокузнецк.

Kappes Daniil Olegovich, student, Novokuznetsk Institute (branch) «Kemerovo State University», Novokuznetsk.

Mozharov Maxim Sergeevich, Ph.D., professor, head Department of computer science and general technical disciplines, Novokuznetsk Institute (branch) «Kemerovo State University», Novokuznetsk.

РЕШЕНИЕ ОЛИМПИАДНЫХ ЗАДАЧ ПО ПРОГРАММИРОВАНИЮ, В КОТОРЫХ ИСПОЛЬЗУЮТСЯ ГРАФЫ

SOLUTION OF OLYMPIAD PROGRAMMING TASKS IN WHICH ARE USED GRAPHS

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

Annotation. The article is devoted to the method of preparing students for solving problems of finding a path in graphs using algorithms, and specifically to the implementation of the two algorithms «search in width» and «search in depth». Depending on the conditions of the problem, students should use one or another method of finding the path.

Ключевые слова: информатика, задачи повышенной сложности, программирование, граф, вершина, ребро, олимпиадная задача.

Keywords: computer science, advanced tasks, programming, graph, vertex, edge, olympiad problem.

При изучении темы «Программирование на графах» школьникам предлагается определение понятия «Граф». Необходимо объяснить им, что такое граф и что он из себя представляет. Приведем фрагмент теоретического материала по теме.

Граф – совокупность точек, соединенных линиями. Точки называются вершинами, или узлами, а линии – ребрами, или дугами.

Степень входа вершины – количество входящих в нее ребер, степень выхода – количество исходящих ребер.

Граф, содержащий ребра между всеми парами вершин, является полным.

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

Встречаются также взвешенные графы, ребрам которых поставлено в соответствие конкретное число – вес ребра.

Когда оба конца ребра встречаются в одной вершине, такое ребро называют петлей (рис. 1).

Графы делятся на:

  • связные (рис. 2);

  • несвязные (рис. 3).

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

Графы также подразделяются на:

  • ориентированные (рис. 4);

  • неориентированные (рис. 5);

  • смешанные.

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

В смешанном графе присутствуют как ориентированные, так и неориентированные ребра [2].

При решении задач граф, обычно, представляют несколькими способами:

  • матрица смежности;
  • матрица инцидентности;
  • список смежности (инцидентности);
  • список ребер.

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

Матрица смежности графа – это квадратная матрица, в которой каждый элемент принимает одно из двух значений: 0 или 1.

Число строк матрицы смежности равно числу столбцов и соответствует количеству вершин графа (рис. 6).

  • 0 – соответствует отсутствию ребра;
  • 1 – соответствует наличию ребра.

Когда из одной вершины в другую проход свободен (имеется ребро), в ячейку заносится 1, иначе – 0. Все элементы на главной диагонали равны 0, если граф не имеет петель.

Матрица инцидентности (инциденции) графа – это матрица, количество строк в которой соответствует числу вершин, а количество столбцов – числу рёбер. В ней указываются связи между инцидентными элементами графа (ребро/дуга и вершина).

В неориентированном графе: если вершина инцидентна ребру, то соответствующий элемент равен 1, в противном случае элемент равен 0.

В ориентированном графе: если ребро выходит из вершины, то соответствующий элемент равен 1; если ребро входит в вершину, то соответствующий элемент равен -1; если ребро отсутствует, то элемент равен 0.

Матрица инцидентности для своего представления требует нумерации рёбер, что не всегда удобно (рис. 7).

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

По отношению к памяти списки смежности менее требовательны, чем матрицы смежности. Такой список можно представить в виде таблицы, столбцов в которой – 2, а строк – не больше, чем вершин в графе.

В каждой строке в первом столбце указана вершина выхода, а во втором столбце – список вершин, в которые входят ребра из текущей вершины (рис. 8).

Преимущества списка смежности:

  • рациональное использование памяти;
  • позволяет быстро перебирать соседей вершины;
  • позволяет проверять наличие ребра и удалять его.

Недостатки списка смежности:

  • при работе с насыщенными графами (с большим количеством рёбер) скорости может не хватать;
  • нет быстрого способа проверить, существует ли ребро между двумя вершинами;
  • количество вершин графа должно быть известно заранее;
  • для взвешенных графов приходится хранить список, элементы которого должны содержать два значащих поля, что усложняет код:

                  o  номер вершины, с которой соединяется текущая вершина;
                  o  вес ребра.

Список рёбер. В списке рёбер в каждой строке записываются две смежные вершины и вес соединяющего их ребра (для взвешенного графа).

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

Выбор представления графа зависит от отношения между числом вершин и числом рёбер [3].

Алгоритмы обхода графа. При решении задач по программированию часто приходится осуществлять обход вершин графа. От порядка обхода графа зависит эффективность алгоритма, скорость его выполнения. Часто при обходе графа необходимо осуществлять усечение обхода для повышения эффективности алгоритма. Для выбора типа алгоритма школьникам важно разобраться в этих алгоритмах. Приведем наше содержание урока для обучения школьников.

Поиск в ширину подразумевает поуровневое исследование графа:

  • вначале посещается корень – произвольно выбранный узел;
  • затем – все потомки данного узла;
  • после этого посещаются потомки потомков и т.д.

Вершины просматриваются в порядке возрастания их расстояния от корня. Алгоритм прекращает свою работу после обхода всех вершин графа, либо в случае выполнения требуемого условия (например, найти кратчайший путь из вершины 1 в вершину 6, рис. 10).

Каждая вершина может находиться в одном из 3 состояний:

  • 0 (оранжевый) – необнаруженная вершина;
  • 1 (зеленый) – обнаруженная, но не посещенная вершина;
  • 2 (серый) – обработанная вершина.

Фиолетовый – рассматриваемая вершина.

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

Применения алгоритма поиска в ширину

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

Алгоритм поиска в ширину работает как на ориентированных, так и на неориентированных графах.

Для примера рассмотрим задачу на поиск кратчайшего пути.

Листинг программы

const n = 7;

var

  Q, D, Prev, ans: array[1..1001] of longint;

  i, j, start, finish, Qstart, Qend, u, v, tmp: longint;

  a: array[1..n, 1..n] of longint =

  ((0, 1, 1, 0, 0, 0, 1 ),

   (1, 0, 1, 1, 0, 0, 0 ),

   (1, 1, 0, 0, 0, 0, 0 ),

   (0, 1, 0, 0, 1, 0, 0 ),

   (0, 0, 0, 1, 0, 1, 0 ),

   (0, 0, 0, 0, 1, 0, 1 ),

   (1, 0, 0, 0, 0, 1, 0 ));

begin

  writeln('----Поиск в ширину-----');

  writeln('Матрица смежности:');

  for i:=1 to n do

  begin

    for j:=1 to n do

      write(a[i,j],' ');

    writeln;

  end;

  writeln('Введите стартовую позицию:');read(start);

  writeln('Введите винишную позицию:');read(finish);

  {заполняем массив длин D}

  for i := 1 to n do

  begin

    D[i] := -1;

    Prev[i] := -1;

  end;

  {расстояние от старта до старта равно нулю}

  D[start] := 0;

  {кладем стартовую вершину в очередь.

  В очереди Q индекс Qstart - номер первого элемента очереди, Qend - номер ячейки после последнего элемента}

  Q[1] := start;

  Qstart := 1;

  Qend := 2;

  {Пока очередь не пуста, то есть, там есть хотя бы один элемент, то есть Qstart и Qend отличаются хотя бы на 1}

  while Qstart < Qend do

  begin

    u := Q[Qstart];//забираем первую вершину из очереди

    inc(Qstart); //передвигаем индекс первого элемента очереди

    {перебираем все вершины графа}

    for v := 1 to n do

      {если нашли соседа, у которого расстояние еще не вычислено, то вычисляем его и кладем этого соседа в очередь}

      if (a[u, v] = 1) and (d[v] = -1) then begin

        d[v] := d[u] + 1;

        Q[Qend] := v;

        inc(Qend);

        Prev[v] := u;

      end;

  end;

  tmp := finish;

  i := 1;

  while tmp <> -1 do

  begin

    ans[i] := tmp;

    inc(i);

    tmp := Prev[tmp];

  end;

  write('Путь до вершины ',finish,': ');

  for j := i - 1 downto 1 do

    write(ans[j], ' ');

end.

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

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

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

Отсутствие последнего свидетельствует об одной из двух возможных ситуаций:

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

Каждая вершина может находиться в одном из 3 состояний (рис. 12):

  • 0 (оранжевый) – необнаруженная вершина;
  • 1 (зеленый) – обнаруженная, но не посещенная вершина;
  • 2 (серый) – обработанная вершина.

Фиолетовый – рассматриваемая вершина.

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

Применения алгоритма поиска в глубину

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

Алгоритм поиска в глубину работает как на ориентированных, так и на неориентированных графах. Применимость алгоритма зависит от конкретной задачи.

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

Листинг программы

var a:array[1..20,1..20] of word; {матрица смежности}

c,pred,fl,d:array[1..20] of word;{c - массив кратчайших расстояний; pred - массив предыдущих вершин; fl - массив флагов; d - массив для записи пути}

i,j,k,n,first,last:byte;

f:text;{переменная для открытия in.txt}

{процедура обхода графа вглубь для поиска всех путей}

Procedure Dfs(x:word); {в качестве параметра передаём текущую вершину}

var i:byte; {локальная переменная}

begin

 if x=last then {если конечная вершина, то вводим путь}

  begin

   write(first,' ');

   for i:=1 to j do {выводим путь}

    write(d[i],' ');

    writeln;

    exit;{выходим из процедуры}

  end;

 fl[x]:=1; {помечаем что были в вершине}

 for i:=1 to n do {если не были в вершине и существует дуга в неё}

  if (fl[i]=0)and(a[x,i]<>32767) then

   begin

    inc(j);

    d[j]:=i; {записываем в путь вершину}

    dfs(i);

    dec(j);

   end;

 fl[x]:=0; {помечаем что вершина свободна}

end;

{основная программа}

begin

     assign(f,'in.txt'); {открываем файл для чтения}

     reset(f);

     readln(f, n); {считываем количество вершин}

     for i:=1 to n do

        for j:=1 to n do

          read(f,a[i,j]); {считываем матрицу смежности}

     writeln('Mатрица:');

     for i:=1 to n do  {выводим матрицу на экран}

        for j:=1 to n do

           if j=n then writeln(a[i,j])

           else write(a[i,j],' ');

     for i:=1 to n do {заменяем нули бесконечностью}

        for j:=1 to n do

          if a[i,j]=0 then a[i,j]:=32767;

     writeln('Введите 1 вершину: ');

     readln(first);

     writeln('Введите 2 вершину');

     readln(last);

     close(f); {закрываем файл in.txt}

     for j:=1 to n do

     begin

       c[j]:=a[first,j]; {записываем начальные значения}

       if a[first,j]<32767 then

       pred[j]:=first; {если существует дуга то записываем предыдущую вершину}

     end;

     for i:=3 to n do

      for j:=1 to n do

       if j<>first then

         for k:=1 to n do {если не бесконечность и путь более выгодный}

           if (c[k]<32767) and (c[k]+a[k,j]<c[j]) then

             begin

              c[j]:=c[k]+a[k,j]; {записываем новое значение}

              pred[j]:=k; {записываем pred вершину}

             end;

     if c[last]=32767 then writeln('Нет путей')

     else {если бесконечность то нет пути}

      begin

          writeln;

          writeln('Кратчайший путь:');

          write(first,' ');

          i:=last;

          k:=1;

          while i<>first do {в обратном порядке обходим путь}

           begin

               d[k]:=i; {записываем путь в массив}

               k:=k+1;

               i:=pred[i];

           end;

          for i:=k-1 downto 1 do {выводим кратчайший путь}

           write(d[i],' ');

          writeln;

          writeln('Все пути:');

          j:=0;

          Dfs(first); {вызываем процедуру поиска всех путей}

      end;

end.

В зависимости от того, до какой вершины мы хотим найти короткий путь, программы выдаст нам тот или иной путь (рис. 13). Вершины заполняются с помощью матрицы смежности графа [1].

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

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

  1. Данная тема довольно сложная, входит в курс высшей математики и требует сложных определений, теорем и т.д. Поэтому для школьников необходимо адаптировать материал или воспользоваться уже адаптированным.
  2. Для дальнейшего использования, при решении олимпиадных задач, школьникам потребуется каждый раз выбирать и модифицировать алгоритм обхода графа, поэтому на этапе изучения они должны досконально изучить приведенный материал, понимать суть алгоритма, знать базовые структуры данных.
  3. Решение задач повышенной сложности на графах часто связано с использованием стека и очереди, поэтому приведенный в статье материал можно использовать при закреплении изученных тем «Очередь», «Стек».

Список литературы

  1. Ахо, А. В. Компиляторы: принципы, технологии и инструменты [Текст] / А. В. Ахо, М. С. Лам, Р. Сети, Д. Д. Ульман, 2 издание. – Compilers : Principles, Techniques and Tools. – 2 изд. – М. : «Вильямс», 2008. – ISBN 978-5-8459-1349-4.
  2. Оре, О. Теория графов [Текст] / О. Оре. – М. : УРСС, 2008. – 352 с. – ISBN 978-5-397-00044-4.
  3. Харари, Ф. Теория графов [Текст] / Ф. Харари. – М. : УРСС, 2003. – 300 с. – ISBN 5-354-00301-6.
Теги: информатика, задачи повышенной сложности, программирование, граф, вершина, ребро, олимпиадная задача, computer science, advanced tasks, programming

Оставить комментарий







Авторизация
E-mail

Пароль  


Регистрация