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

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




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

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

Пример маршрута: (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 ставится число rij, соответствующее числу ребёр, которые соединяют эти вершины. Диагональными элементами матрицы являются нули, если в матрице отсутствуют петли. В противном случае проставляется число равное числу петель у соответствующей вершины. Ясно, что матрица симметрична относительно главной диагонали (rij = rji).

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

r (xi) = (ri 1+ ri 2+ ri 3+... + riN).

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

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

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

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

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

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

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

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

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

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

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

A = an-110n-1+a n-210n-2+...+a1101+a0100+a-110-1+ a-210-2+...+am10-m.

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

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

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

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

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

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

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

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

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

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

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

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

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

Поделиться:





Читайте также:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...