Теория:

Нагруженный граф это граф, у которого каждому ребру сопоставлено некоторое число. В некоторых задачах это число может обозначать расстояние между вершинами, или время перехода от одной вершины к другой, или еще что-либо. Ненагруженным графом называется тот, у которого каждому ребру поставлено число \(1\).
Способы представления графов:
  1. Перечисление всех ребер графов;
  2. Таблица смежности.
Таблица смежности — таблица, в клетке которой на пересечении строки и столбца, соответствующих данных вершинам, указанно, соединены эти вершины ребром или нет.
Если граф является нагруженным, то для каждого ребра в соответствующей клетке указывается нагрузка.
Пример:
Изображен граф на рисунке 1. Запишем его представления двумя способами.
 
рис1.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
 
 
 
 
 
 
 
 
 
Для ненагруженного графа в таблице смежности везде вместо чисел, указывающих нагрузку (т.е. отличных от \(0\)), стояло бы число \(1\).
 
Далее в заданиях на составления алгоритма, любым из двух способов обрабатывающего графа, вершины графа будут перенумерованными натуральными числами от \(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.
 
Таблица 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
 
 
 
 
 
 
 
 
 
  
Алгоритм обработки графов.
 
Пусть требуется граф с \(n\) вершинами и \(m\) ребрами. Поскольку из каждой вершины выходит не более чем n1 ребер, а сумма всех степеней вершин равна удвоенному числу ребер, имеем соотношение 2mn1n. Приведем алгоритм, в котором через SR1:m;1:2 обозначен массив, содержащий список ребер, а через TS1:n;1:n обозначен массив, содержащий таблицу смежности.
 
Алгоритм Случайный граф
цел: n,m,i,j,k,SR1:m;1:2;TS1:n;1:n;
{ Запросить n;    (* запрашивается количество вершин *)
   Запросить m;   (* запрашивается количество ребер *)
   Если (mn×(n1)/2)
    то  { Сообщить «Такой граф строить нельзя»; }
    иначе
    { Делать от i:=1 до n
        { Делать от j:=1 до n
            { TSi;j:=0;
            }
        }       (* Первоночальное заполнение таблицы смежности нулями *)
        Делать от i:=1 до m
        {j:=INT((n1)×rand(1))+1;
          k:=INT((nj)×rand(1))+j+1;
               Делать пока TS[j;k]:=1
              {j:=INT((n1)×rand(1))+1;
                k:=INT((nj)×rand(1))+j+1;
               }
               TS[j;k]:=1;
               TS[k;j]:=1;
               SR[i;1]:=j;
               SR[i;2]:=k;
        }          (* случайное добавление одного ребра *)
       Сообщить «Вот таблица смежности»;
       Сообщить TS1:n;1:n;      (* в реальной программе это действие оформляется двойным циклом *)
       Сообщить «Вот список ребер»;
       Сообщить SR1:m;1:2;     (* в реальной программе это действие оформляется двойным циклом *)
    }
}
Источники:
Гейн А.Г., Сенокосов А.И. Информатика и ИКТ: учебник для общеобразовательных учреждений. - Москва: Просвещение, 2012. -224 с.