Способы представления графов в компьютере - «оцифровка» графов

1. Матрица смежности. Это таблица 2хn, где n - количество вершин графа. Если из вершины i есть ребро к вершине j, то в клетке с координатами (i, j)указывают 1, а если нет – то 0. Для взвешенного графа вместо 1 указывают вес. Если граф неориентиованный, то матрица получается симметричной. Таким способом нельзя задать только взвешенные псевдографы, но они почти никогда не применяются. Такой способ требует n×n ячеек памяти.
2. Список ребер. Простое перечисление всех ребер: для каждого ребра – начальная и конечная вершины (для взвешенного графа – еще и вес). Такой способ задания требует достаточно мало памяти: 2×m ячеек, где m - количество ребер. Обычно этот способ используется для задания входных данных, которые затем конвертируются программой в другую форму представления.
3. Список смежности – набор строк по числу вершин графа. Каждая вершина начинает одну из строк списка, а правее в строке перечислены вершины, связанные с ней ребрами. Таким образом, всего будет столько же значений, сколько ребер графа, не считая первых ячеек каждой строки. Необходимое количество памяти: m+n ячеек, где m - количество ребер графа, n- количество вершин графа.

Псевдослучайная последовательность – последовательность чисел, которые вычисляются по некоторым правилам, но соответствуют случайным числам в задаче. Чаще всего для генерации таких последовательностей используют специальные функции. Например, \(\left( {{t}^{5}}+4\cdot {{t}^{3}}+11\cdot t \right)\bmod 100\)

где t - количество секунд, прошедших за сутки. Можно также использовать в формулах расчета такие величины, как температура чипа или количество параллельных процессоров.