Представления графов в ЭВМ

Наиболее распространены следующие 4 метода представления графов в ЭВМ:

- Матрица смежности,

- Матрица инцидентности,

- Списки смежности вершин,

- Списки смежности дуг.

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

1) Графический способ представления (если граф небольшой).

2) Использование матриц. Матрица легко описывается и при анализе характеристик графа можно использовать алгоритмы линейной алгебры. Также используется представление графа в связной памяти, в том случае, если большее количество элементов в матрице равно нулю (матрица не заполнена).

Числовыми характеристиками графаявляются: количество узлов, количество дуг, ранг графа. Ранг графа: R(G) = |X| - K, где К – количество компонентов связности графа в случае, если но не связан.

Рассмотрим матрицу смежности. Пусть задан граф G = (X, U), |X| = n. Имеем матрицу А размерности n ´ n, которая называется матрицей смежности, если элементы ее определяются следующим образом:

Рассмотрим применение матричной алгебры для определения характеристик графа. Выражение a _{i k} L a _{k j} означает, что между узлами i и j есть две дуги, проходящие через узел k, если значение выражения равно True.

Выражение означает, что всегда имеется путь между этими узлами длиною 2 (два), если выражение истинно.

А L А = А⁽²⁾ – логические операции заменяются арифметическими. Тогда каждый элемент a _{i j} будет давать информацию о том, есть ли путь из i в j (i, j = 1, 2,…,n).

Выражение А⁽ⁿ⁾ = А^{(n – 1)} L А означает, есть ли путь длиной n между различными узлами i. По диагонали будет характеристика, есть ли циклы (контура) в матрице.

Р = А V А⁽²⁾ V …V А⁽ⁿ⁾ = - матрица связности. Определяется, существует ли какой-либо путь между узлами i и j. Алгоритм вычисления данного выражения:

1. Р = А;

2. повторить 3, 4 (k=1, 2,…, n);

3. повторить 4 для i=1, 2, …,n;

4. повторить Р_{i j} = Р_{i j} V (Р_{i k} L Р_{k j}), j=1, 2,…, n.

В связной памяти наиболее часто представление графа осуществляется с помощью структур смежности. Для каждой вершины множества X задается множество М(X _i) соответственно всех его последователей (если это орграф) или соседей (для неорграфа). Таким образом, структура смежности графа G будет представлять собой список таких множеств: < М(X ₁), М(X ₂),…, М(X _n)> для всех его вершин.

Рассмотрим пример (узлы обозначаем в виде цифр: 1, 2,…, n):

			Для неорграфа: 1: 2, 3; 2: 1, 3; 3: 1, 2; 4: 5; 5: 4. Для орграфа: 1: 2; 2: 3; 3: 1; 4: 5; 5: - .

Структуру смежности можно реализовать массивом из n линейно связанных списков:

Представление графа может оказать влияние на эффективность алгоритма. Часто запись алгоритмов на графах задается в терминах вершин и дуг, независимо от представления графа. Например, алгоритм определения количества последователей вершин: C (X) X_i, S – количество дуг.

S = 0;

" x Î X выполнить:

начало

С(x)=0;

" t Î M(x) выполнить: C(x) = C(x) + 1;

S = S + C(x);

Множества, графы, системы счисления. (В).

Перевод чисел из двоичной восьмеричной шестнадцатеричной СС в десятичную СС. Перевод чисел из десятичной СС в двоичную, восьмеричную. шестнадцатеричную СС. Специальные методы перевода. Представление целых и дробных чисел в памяти ПК.

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

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

При переводе удобно пользоваться таблицей степеней двойки:

Таблица 4. Степени числа 2

n (степень)

Пример .Число перевести в десятичную систему счисления.

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

При переводе удобно пользоваться таблицей степеней восьмерки:

Таблица 5. Степени числа 8

n (степень)

Пример .Число перевести в десятичную систему счисления.

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

При переводе удобно пользоваться таблицей степеней числа 16:

Таблица 6. Степени числа 16

n (степень)

Пример .Число перевести в десятичную систему счисления.

Перевод чисел в десятичную систему осуществляется путем составления степенного ряда с основанием той системы, из которой число переводится. Затем подсчитывается значение суммы.

Пример

10101101.101₂ = 1 2⁷+ 0 2⁶+ 1 2⁵+ 0 2⁴+ 1 2³+ 1 2²+ 0 2¹+ 1 2⁰+ 1 2^-1+ 0 2^-2+ 1 2^-3 = 173.625₁₀

б) Перевести 703.04₈ "10" с.с.

703.04₈ = 7 8²+ 0 8¹+ 3 8⁰+ 0 8^-1+ 4 8^-2 = 451.0625₁₀

в) Перевести B2E.4₁₆ "10" с.с.

B2E.4₁₆ = 11 16²+ 2 16¹+ 14 16⁰+ 4 16^-1 = 2862.25₁₀

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

Пример.Число перевести в двоичную систему счисления.

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

Пример.Число перевести в восьмеричную систему счисления.

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

Пример.Число перевести в шестнадцатеричную систему счисления.

Перевод целых чисел

Правила перевода целых чисел становится ясным из общей формулы записи числа в произвольной позиционной системе. Пусть число в исходной системе счисления s имеет вид . Требуется получить запись числа в системе счисления с основанием h:

.

Для нахождения значений разделим этот многочлен на h:

.

Как видно, младший разряд , то есть , равен первому остатку. Следующий значащий разряд определяется делением частного на h:

.

Остальные также вычисляются путём деления частных до тех пор, пока не станет равным нулю.

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