рефераты конспекты курсовые дипломные лекции шпоры

Раздел Математика
/
§2.5. Цикломатическое число.

Реферат Курсовая Конспект

Выберите учебное заведение

§2.5. Цикломатическое число.

§2.5. Цикломатическое число. - раздел Математика, Элементы комбинаторики 1. Будем Рассматривать Подграфы, Которые Мог...

1. Будем рассматривать подграфы, которые могут быть несвязными, но содержащие все вершины графа. Пусть G - граф, содержащий p занумерованных ребер (e₁,e₂,..,e_p) Каждому подграфупоставим в соответствие p-мерный вектор из нулей и единиц:

если e_i H и a_i = 0 если (характеристический вектор подграфа Н).Это соответствие, очевидно, взаимнооднозначное. Более того, сумме по модулю 2 подграфови- соответствует поразрядная сумма по модулю 2 их характеристических векторов. Над множеством коэффициентов {0, 1} множество всех подграфов образует линейное пространство: умножение любого подграфа Н на 1 дает Н, умножение на 0 - пустой подграф, т.е. подграф, не содержащий ребер и состоящий из одних изолированных вершин графа G. Нетрудно видеть, что пространство подграфов графа G и пространство характеристических векторов его подграфов изоморфны и имеют размерность р. Базисом может служить множество всех однореберных подграфов. Характеристический вектор каждого такого подграфа содержит ровно одну единицу, причем для разных подграфов - на разных местах.

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

Элементы комбинаторики

На сайте allrefs.net читайте: "Элементы комбинаторики"

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: §2.5. Цикломатическое число.

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

N,n)-размещения без повторенийназываются n-перестановками,или перестановками из n элементов.
Неупорядоченные (n, К)-выборки называются сочетаниями: с повторениямиили без повторений.Заметим, что (n,k) -сочетание без повторений - это k-элементное подмножеств

Это правило суммы,или правило альтернатив.
Если объект х Є X может быть выбран n способами и после каждого из таких выборов объект у Є Y может быть выбран m способами, то выбор упорядоченной пары (х, у) может быть осуществлен m n способами.

конфигураций.
1. Число (n,k)-размещений без повторенийможет быть определено с помощью правила произведения.

Способы задания графов.
1. Граф - это система некоторых объектов вместе с некоторыми парами этих объектов, изображающая отношения связи между ними. Неориентированный граф

§2.2. Цепи. Циклы. Связность.
1. Последовательность вершин и ребер графа G называется путем

§2.3. Деревья.
1. Ребро е произвольного графа G называется циклическим,если оно принадлежит хотя бы одному элементарному циклу в графе, и ациклическим

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

§3.1. Представление информации.
Кодирование – представление информации в виде сигналов и их характеристик. Декодирование – обратный процесс. Сигнал может представлять информацию в виде своих хара

Рассмотрим преобразователь перемещения в двоичный неизбыточный код.
Рассмотрим возникновение ошибки при передаче от 3х до 4х

§3.3. Помехоустойчивые избыточные коды.
В неизбыточных двоичных кодах, в кодах Грея и в кодах, построенных на картах Карно всякая ошибка состоит в искажении какого-либо символа или разряда кода

§3.4. Коды с проверкой на четность.
Обладают большой эффективностью и малой избыточностью. Коды с проверкой на четность строятся таким образом, чтобы к кодовой комбинации добавлялся один разряд, который делает число единиц кодовой ко

§3.5. Код Хэмминга.
Код Хэмминга относится к кодам, которые позволяют не только обнаруживать но и исправлять одиночные ошибки. Исправляющую способность кода достигается за счет многократных проверок на четнос