Главная | Обратная связь | Поможем написать вашу работу!

Структурные свойства связных графов

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

Маршрут – последовательность рёбер, заданная парами вершин, в которых каждая пара вершин – смежная.

Пример маршрута: (X 1, X 2)(X 2, X 3)(X 3, X 1)(X 1, X 4)…, и т. д.

Цепь – маршрут, в котором все ребра различны. Простая цепь – это цепь, в которой все вершины различны.

Цикл – цепь, в которой совпадает начальная и конечная вершины. Простой цикл – это простая цепь, с совпадающими начальной и конечной вершинами.

Пример цикла: (X 1, X 2)(X 2, X 3)(X 3, X 1).

Гамильтонов цикл HC – такой цикл, который проходит через все вершины графа по одному разу: HC = (X 1, X 2)(X 2, X 3)(X 3, X 4)(X 4, X 1). Его наличие в графе не очевидно, хотя его полезно знать для решения ряда топологических задач. Существуют алгоритмы для выделения гамильтонова цикла.

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

d = NN -2.

Структурные свойства графа во многом определяют возможность реализации тех или иных алгоритмов их обработки.

Матрица соединений

Матрицы соединений используются для формализованного описания графов. Обозначение этой матрицы - R.

Правило заполнения матрицы следующее. Столбцы и строки матрицы соответствуют вершинам графа; число строк и столбцов равно числу вершин, т. е. матрица квадратная. На пересечении строки i и столбца j ставится число r_ij, соответствующее числу ребёр, которые соединяют эти вершины. Диагональными элементами матрицы являются нули, если в матрице отсутствуют петли. В противном случае проставляется число равное числу петель у соответствующей вершины. Ясно, что матрица симметрична относительно главной диагонали (r_ij = r_ji).

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

r (x_i) = (r_i ₁+ r_i ₂+ r_i ₃+... + r_iN).

Матрица инциденций

Отличие матрицы инциденций (от матрицы соединений (смежности) состоит в том, что строки матрицы соответствуют вершинам графа, а столбцы – рёбрам. Элементами _ij матрицы являются либо нули, либо единицы. В случае, если ребро не инцидентно вершине, то элемент равен 0, если ребро инцидентно вершине – элемент равен 1.

В. СИСТЕМЫ СЧИСЛЕНИЯ

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

Системы счисления делятся на два типа: непозиционные и позиционные.

Позиционная система счисления характеризуется основанием и базисом.

Основание позиционной системы счисления q - это число знаков (или символов), используемых для изображения цифр в данной системе.

Базис — это множество самих знаков (символов), используемых для изображения цифр в данной системе.

Замечание: Основание системы счисления q само не является цифрой в q-ричной системе счисления. В любой системе счисления, использующей базис {0, 1, 2,..., q-1} ее основание будет представлено числом 10₍_q₎.^{^[1]}

Десятичная система счисления. Полиномиальное представление чисел

Наибольшее распространение в вычислительной практике получила десятичная система счисления. Всякое рациональное десятичное число можно представить в так называемой полиномиальной записи.

A = a_n-110^n-1+a _n-210^n-2+...+a₁10¹+a₀10⁰+a_-110^-1+ a_-210^-2+...+a_m10^-m.

(Здесь n - число знаков в целой части числа A, m - в дробной.)

Недесятичные системы счисления

Перевод чисел из недесятичной системы счисления в десятичную

Для перевода числа из системы счисления с основанием q в десятичную систему счисления следует представить q-ричное число в полиномиальной форме, заменить во всех слагаемых все цифры q-ричного числа и само основание q их десятичными эквивалентами^{^[2]}, а затем вычислить значения всех слагаемых и соответствующего полинома. Все вычисления при этом проводятся в десятичной системе счисления по

Перевод чисел из десятичной системы счисления в недесятичную

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

Чтобы перевести десятичное число в систему счисления с основанием q необходимо отдельно перевести его целую часть, затем дробную часть и объединить полученные результаты.

Т. Способ запуска Microsoft Word стандартен. Отличаются данные текстовые процессоры значками и названием программ.

Универсальный способ запуска процессора Word:

1. Щелкнуть левой клавишей мыши по кнопке "Пуск" на Панели инструментов Windows.

2. Указать в появившемся стартовом меню на пункт "Программы".

3. В открывшемся списке программ щелкнуть на строке "Microsoft Word".

Также запуск можно осуществить нажатием ярлыка на рабочем столе соответствующего текстового процессора.

⇐ Предыдущая 1 234 Следующая ⇒