2. Способы задания графов

 

Далее в заданиях на составления алгоритма, любым из двух способов обрабатывающего графа, вершины графа будут перенумерованными натуральными числами от \(1\) до \(n\).

 

1 способ. Если граф задается перечислением всех его ребер, то список ребер для нагруженного графа задается как двумерный массив $A[1:3;1:n]$, где в первой строке соответствующей этому массиву таблицы указывается один конец ребра, во второй — другой его конец, а в третьей — величина нагрузки (здесь \(n\) — число ребер в графе). А для ненагруженного графа соответствующий массив содержит только первые две строчки.

  

2 способ. Если граф задается таблицей смежности, то значение первого индекса считается номером первой вершины, а второго индекса — номером второй вершины; сами номера вершин в массиве не присутствуют. Для графа на рисунке 1 при естественной нумерации вершин  \(A\) — \(1\), \(B\) — \(2\), \(C\) — \(3\), \(D\) — \(4\) и \(E\) — \(5\) список ребер задается массивом, который можно изобразить в виде таблицы 2. 

 

 

 

 

 

 

 

А таблица смежности имеет вид таблицы 3.

 

 

 

 

 

 

 

 

 

 

  

Пусть требуется граф с \(n\) вершинами и \(m\) ребрами. Поскольку из каждой вершины выходит не более чем $n-1$ ребер, а сумма всех степеней вершин равна удвоенному числу ребер, имеем соотношение $2m\le \left(n-1\right)n$. Приведем алгоритм, в котором через $\mathit{SR}\left[1:m;1:2\right]$ обозначен массив, содержащий список ребер, а через $\mathit{TS}\left[1:n;1:n\right]$ обозначен массив, содержащий таблицу смежности.

 

Алгоритм Случайный граф

цел: $n,m,i,j,k,\mathit{SR}\left[1:m;1:2\right];\mathit{TS}\left[1:n;1:n\right];$

{ Запросить $n$;    (* запрашивается количество вершин *)

   Запросить $m$;   (* запрашивается количество ребер *)

   Если $(m\succ n\times (n-1)/2)$

    то  { Сообщить «Такой граф строить нельзя»; }

    иначе

    { Делать от $i:=1$ до $n$

        { Делать от $j:=1$ до $n$

            { $\mathit{TS}\left[i;j\right]:=0;$

            }

        }       (* Первоночальное заполнение таблицы смежности нулями *)

        Делать от $i:=1$ до $m$

        {$j:=\mathit{INT}((n-1)\times \mathit{rand}(1))+1;$

          $k:=\mathit{INT}((n-j)\times \mathit{rand}(1))+j+1;$

               Делать пока $\mathit{TS}[j;k]:=1$

              {$j:=\mathit{INT}((n-1)\times \mathit{rand}(1))+1;$

                $k:=\mathit{INT}((n-j)\times \mathit{rand}(1))+j+1;$

               }

               $\mathit{TS}[j;k]:=1;$

               $\mathit{TS}[k;j]:=1;$

               $\mathit{SR}[i;1]:=j;$

               $\mathit{SR}[i;2]:=k;$

        }          (* случайное добавление одного ребра *)

       Сообщить «Вот таблица смежности»;

       Сообщить $\mathit{TS}\left[1:n;1:n\right]$;      (* в реальной программе это действие оформляется двойным циклом *)

       Сообщить «Вот список ребер»;

       Сообщить $\mathit{SR}\left[1:m;1:2\right]$;     (* в реальной программе это действие оформляется двойным циклом *)

    }

}