Теория:

Нагруженный граф это граф, у которого каждому ребру сопоставлено некоторое число. В некоторых задачах это число может обозначать расстояние между вершинами, или время перехода от одной вершины к другой, или еще что-либо. Ненагруженным графом называется тот, у которого каждому ребру поставлено число \(1\).
Способы представления графов:
  1. Перечисление всех элементов графа, то есть рёбер;
  2. Таблица или матрица смежности.
Таблица (матрица) смежности — таблица, в которой строки и столбцы соответствуют вершинам, а на их пересечении в ячейках указывается их смежность.
В таблице смежности ненагруженного графа в ячейке ставим \(1\), если вершины смежные, в ином случае — \(0\).
В таблице смежности нагруженного графа для каждого ребра в ячейке записывается вес соответствующего ребра.
Пример:
Рассмотрим нагруженный граф на рисунке 1. Необходимо представить его двумя вариантами.
 
64.png
Рис. \(1\). Нагруженный граф
 
1 вариант (перечисление рёбер графа):
 
(AC;8),(AD;10),(BE;1),(BD;4),(CE;3),(CD;1).
 
2 вариант (таблица смежности):
 
Таблица 1.
Вершина
A
B
C
D
E
A
0
0
8
10
0
B
0
0
0
4
1
C
8
0
0
1
3
D
10
4
1
0
0
E
0
1
3
0
0
 
 
 
 
 
 
 
 
 
Далее в заданиях на составления алгоритма, любым из двух способов обрабатывающего графа, вершины графа будут перенумерованными натуральными числами от \(1\) до \(n\).
 
1 способ. Если граф задается перечислением всех его ребер, то список ребер для нагруженного графа задается как двумерный массив A[1:3;1:n], где в первой строке соответствующей этому массиву таблицы указывается один конец ребра, во второй — другой его конец, а в третьей — величина нагрузки (здесь \(n\) — число ребер в графе). Ненагруженный граф задается массивом, содержащим соответственно только две строчки без строки с величиной нагрузки.
  
2 способ. Рассмотрим задание графа таблицей смежности. Имена столбцов и строк в таблице смежности соответствуют вершинам графа. Так у графа на рисунке 1 Вершины возможно пронумеровать следующим способом: \(A\) — \(1\), \(B\) — \(2\), \(C\) — \(3\), \(D\) — \(4\) и \(E\) — \(5\). Если все ребра данного графа  задать массивом, то получим массив как в таблице 2. 
 
Таблица 2.
1
1
2
2
3
3
3
4
4
5
4
5
8
10
4
1
1
3
 
 
 
 
 
 
Тогда таблица смежности будет следующая:
 
Таблица 3.
Вершина
1
2
3
4
5
1
0
0
8
10
0
2
0
0
0
4
1
3
8
0
0
1
3
4
10
4
1
0
0
5
0
1
3
0
0
 
 
 
 
 
 
 
 
 
  
Алгоритм обработки графов
Имеется  граф с v вершинами и \(r\) рёбрами. Так как граф содержит рёбер на единицу меньше, чем вершин, то получим что из каждой вершины может исходить v1 рёбер, но не более. Известно также, что сумма всех степеней вершин равна удвоенному числу рёбер. Исходя из этого получаем, что 2rv1v. Рассмотрим алгоритм, где все ребра заданы массивом SR1:r;1:2, а таблица смежности задана массивом TS1:v;1:v.
 
Алгоритм Случайный граф
цел: v,r,i,j,k,SR1:r;1:2;TS1:v;1:v;
{ Запросить v;
   Запросить r
   Если (rv×(v1)/2)
    то  { Сообщить «Граф построить невозможно»; }
    иначе
    { Делать от i:=1 до v
        { Делать от j:=1 до v
            { TSi;j:=0;
            }
        }       (* Первичное заполнение таблицы смежности нулями *)
        Делать от i:=1 до r
        {j:=INT((v1)×rand(1))+1;
          k:=INT((vj)×rand(1))+j+1;
               Делать пока TS[j;k]:=1
              {j:=INT((v1)×rand(1))+1;
                k:=INT((vj)×rand(1))+j+1;
               }
               TS[j;k]:=1;
               TS[k;j]:=1;
               SR[i;1]:=j;
               SR[i;2]:=k;
        }          (* случайное добавление одного ребра *)
       Сообщить «Полученая таблица смежности»;
       Сообщить TS1:v;1:v;      (* в реальной программе это действие оформляется двойным циклом *)
       Сообщить «Вот список ребер»;
       Сообщить SR1:r;1:2;     (* в реальной программе это действие оформляется двойным циклом *)
    }
}