Представления графов в ЭВМ
Наиболее распространены следующие 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 А = А(2) – логические операции заменяются арифметическими. Тогда каждый элемент a i j будет давать информацию о том, есть ли путь из i в j (i, j = 1, 2,…,n). Выражение А(n) = А(n – 1) L А означает, есть ли путь длиной n между различными узлами i. По диагонали будет характеристика, есть ли циклы (контура) в матрице. Р = А V А(2) V …V А(n) = - матрица связности. Определяется, существует ли какой-либо путь между узлами 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 1), М(X 2),…, М(X n)> для всех его вершин.
Рассмотрим пример (узлы обозначаем в виде цифр: 1, 2,…, n):
Структуру смежности можно реализовать массивом из n линейно связанных списков:
Представление графа может оказать влияние на эффективность алгоритма. Часто запись алгоритмов на графах задается в терминах вершин и дуг, независимо от представления графа. Например, алгоритм определения количества последователей вершин: C (X) Xi, S – количество дуг. S = 0; " x Î X выполнить: начало С(x)=0; " t Î M(x) выполнить: C(x) = C(x) + 1; S = S + C(x);
Множества, графы, системы счисления. (В). Перевод чисел из двоичной восьмеричной шестнадцатеричной СС в десятичную СС. Перевод чисел из десятичной СС в двоичную, восьмеричную. шестнадцатеричную СС. Специальные методы перевода. Представление целых и дробных чисел в памяти ПК. Перевод чисел из одной системы счисления в другую составляет важную часть машинной арифметики. Рассмотрим основные правила перевода. 1. Для перевода двоичного числа в десятичное необходимо его записать в виде многочлена, состоящего из произведений цифр числа и соответствующей степени числа 2, и вычислить по правилам десятичной арифметики:
При переводе удобно пользоваться таблицей степеней двойки: Таблица 4. Степени числа 2
Пример .Число перевести в десятичную систему счисления.
2. Для перевода восьмеричного числа в десятичное необходимо его записать в виде многочлена, состоящего из произведений цифр числа и соответствующей степени числа 8, и вычислить по правилам десятичной арифметики:
При переводе удобно пользоваться таблицей степеней восьмерки: Таблица 5. Степени числа 8
Пример .Число перевести в десятичную систему счисления.
3. Для перевода шестнадцатеричного числа в десятичное необходимо его записать в виде многочлена, состоящего из произведений цифр числа и соответствующей степени числа 16, и вычислить по правилам десятичной арифметики:
При переводе удобно пользоваться таблицей степеней числа 16: Таблица 6. Степени числа 16
Пример .Число перевести в десятичную систему счисления.
Перевод чисел в десятичную систему осуществляется путем составления степенного ряда с основанием той системы, из которой число переводится. Затем подсчитывается значение суммы. Пример 10101101.1012 = 1 27+ 0 26+ 1 25+ 0 24+ 1 23+ 1 22+ 0 21+ 1 20+ 1 2-1+ 0 2-2+ 1 2-3 = 173.62510 б) Перевести 703.048 "10" с.с. 703.048 = 7 82+ 0 81+ 3 80+ 0 8-1+ 4 8-2 = 451.062510 в) Перевести B2E.416 "10" с.с. B2E.416 = 11 162+ 2 161+ 14 160+ 4 16-1 = 2862.2510 4. Для перевода десятичного числа в двоичную систему его необходимо последовательно делить на 2 до тех пор, пока не останется остаток, меньший или равный 1. Число в двоичной системе записывается как последовательность последнего результата деления и остатков от деления в обратном порядке. Пример.Число перевести в двоичную систему счисления. 5. Для перевода десятичного числа в восьмеричную систему его необходимо последовательно делить на 8 до тех пор, пока не останется остаток, меньший или равный 7. Число в восьмеричной системе записывается как последовательность цифр последнего результата деления и остатков от деления в обратном порядке. Пример.Число перевести в восьмеричную систему счисления. 6. Для перевода десятичного числа в шестнадцатеричную систему его необходимо последовательно делить на 16 до тех пор, пока не останется остаток, меньший или равный 15. Число в шестнадцатеричной системе записывается как последовательность цифр последнего результата деления и остатков от деления в обратном порядке. Пример.Число перевести в шестнадцатеричную систему счисления.
Перевод целых чисел Правила перевода целых чисел становится ясным из общей формулы записи числа в произвольной позиционной системе. Пусть число в исходной системе счисления s имеет вид . Требуется получить запись числа в системе счисления с основанием h: . Для нахождения значений разделим этот многочлен на h: . Как видно, младший разряд , то есть , равен первому остатку. Следующий значащий разряд определяется делением частного на h: . Остальные также вычисляются путём деления частных до тех пор, пока не станет равным нулю. Для перевода целого числа из s-ичной системы счисления в h-ичную необходимо последовательно делить это число и получаемые частные на h (по правилам системы счисления с основанием h) до тех пор, пока частное не станет равным нулю. Старшей цифрой в записи числа с основанием h служит последний остаток, а следующие за ней цифры образуют остатки от предшествующих делений, выписываемые в последовательности, обратной их получению.
Популярное: Личность ребенка как объект и субъект в образовательной технологии: В настоящее время в России идет становление новой системы образования, ориентированного на вхождение... Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние... Как вы ведете себя при стрессе?: Вы можете самостоятельно управлять стрессом! Каждый из нас имеет право и возможность уменьшить его воздействие на нас... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (870)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |