WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 || 3 | 4 |   ...   | 5 |

Раздел 4. Основные понятия неориентированного графа Абстрактное описание; степень вершины; разбиение графа на составляющие части; маршруты и циклы; связность графа; разновидности графов.

Литература: [1, c. 10–21].

Пусть V – непустое множество вершин графа v V. В неориентированном графе ребром, соединяющим две вершины vi и vj, называется неупоu рядоченная пара [vi, vj] или [vj, vi], при этом ребро обозначается = [vi, vj].

Множество ребер является конечным подмножеством (возможно пусu тым) неупорядоченного произведения V&V (т. е. V&V ) с элементами вида [v, w], где v, w V и допустимо совпадение элементов пары v = w.

Тогда граф G можно определить как совокупность G = (V, ).

U Можно ввести отображение инцидентности графа – Г. Если вершиu ны v, w V являются граничными точками ребра U, то это можно обозначить u ~[v, w] (читается “ребро u соединяет вершины v и w”) и ввести отображение Г(u) = [v, w] – это означает, что ребро инцидентно каждой из вершин v и w и, наоборот, вершины инцидентны ребру.

Поскольку отображение инцидентности графа Г включает множество ребер графа U, постольку описание графа как совокупности мноU жества вершин V и отображения Г множества в V&V вида G = (V, Г) полностью определяет граф.

Степенью вершины (v) называется число концов ребер, инцидентных вершине v (т. е. петля учитывается дважды). Для изолированной вершины (v) = 0.

Вырожденным называется граф, у которого все вершины изолированы.

Разбиение графа на составляющие Суграфом графа G называется граф G’ = (V, ), где, т. е.

U U U суграф получается из исходного графа удалением некоторого числа ребер (с сохранением вершин).

Подграфом графа G называется граф G’ = (, ), где V, = U V U V =U (V’ & V’), т. е. подграф получается из исходного графа удалением некоторого числа вершин вместе со всеми ребрами, инцидентными удаленной вершине.

U Частью (частичным графом) графа G называется граф G’ = (V’, ), U где V V,, т. е. часть графа получается из исходного графа приU менением обеих описанных операций.

Маршрутом называется конечная последовательность n ребер графа u u u,,..., (не обязательно различных), если существует последова1 2 n тельность v0, v1,..., vn из n + 1 (не обязательно различных) вершин таких, что ui ~ [vi-1, vi], для i = 1, 2,..., n.

Длиной маршрута (n) называется число ребер, которые он содержит.

Маршрут замкнут, если v0 = vn, и незамкнут, если v0 vn.

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

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

Простой цепью называется цепь, в которой все n + 1 вершин v0, v1,..., vn различны (в этом случае ребра обязательно различны).

Простым циклом называется цикл, если v0 = vn, но все остальные вершины различны.

Связным называется граф G = (V, U ), если для всех vi и vjV (vi vj) всегда существует цепь из vi в vj, т. е. если каждая пара различных вершин может быть соединена, по крайней мере, одной цепью. В противном случае граф называется несвязным.

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

Лесом из K деревьев называется граф без циклов, состоящий из K компонент.

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

Полным называется граф, в котором любые две различные вершины являются смежными, т. е. соединяются ребром.

Раздел 5. Основные понятия для ориентированного графа Абстрактное описание орграфа; отображение инцидентности и смежности; части графа; перемещения в орграфе; разновидности орграфов; орграфы и бинарные отношения; транзитивные замыкания;

связность орграфа.

Литература: [1, c. 23–35].

Орграф G можно определить как совокупность G = (V, U), где V = ={v1, …, vn} – множество вершин графа, а U V V – конечное подмножество упорядоченного (декартова) произведения, образующее множество дуг графа.

Дугу (стрелку), соединяющую вершины vi, vj, обозначают (vi, vj), где vi – начало дуги, а vj – конец дуги. Говорят, что дуга направлена от вершины vi к вершине vj или дуга исходит из вершины vi и входит в вершину vj. Для удобства дуги также обозначают одной буквой: uij = =(vi, vj), uk = (vi, vj) или u = (vi, vj).

Пусть задан граф G = (V, U) и подмножество V1 V. Говорят, что дуга u = (vi, vj) заходит в V1, если viV1, а vj V1 (конец дуги vj находится в V1). Если viV1, а vjV1, то говорят, что дуга исходит из V1 (начало дуги vi находится в V1). В обоих случаях дугу u называют инцидентной подмножеству V1. Если подмножество сводится к одной вершине, то дугу называют инцидентной этой вершине (заходящей в нее или исходящей из нее).

Обозначим через Гv подмножество вершин V, смежных с v, в которые можно прийти по инцидентным дугам (стрелки исходят из v), или иначе подмножество концов дуг, имеющих началом вершину v. По матрице смежности S можно выделить подмножество Гvi по i-й строке, где ненулевые элементы sij указывают на вершины vj Гvi. Это отображение инцидентности и смежности позволяет определить граф как пару G = (V, Г), образованную множеством вершин V и многозначным отображением Г множества V в себя. Элемент vi V называют вершиной, а пару (vi, vj), где vj Гvi, – дугой. Граф G имеет порядок n, если число вершин V = n.

Обозначим через Г -1v подмножество вершин, смежных с v, из которых можно зайти в вершину v по инцидентным дугам, при этом матрица смежности графа G-1 = (V, Г-1) образуется транспонированием (перестановкой строк и столбцов) матрицы смежности графа G.

Части графа Суграфом G’ = (V, Г’) графа G = (V, Г) называется граф, если (vi V) (Г’vi Гvi), т. е. из исходного графа удаляется некоторое количество дуг (с сохранением вершин).

Подграфом G’ = (V’, Г’) графа G = (V, Г) называется граф, если V’ V и (vi V) (Г’vi = V’ Гvi), т. е. из исходного графа удаляются некоторые вершины вместе со всеми дугами, инцидентными удаленной вершине.

Частичным подграфом G’ = (V’, Г’) графа G = (V, Г) называется граф, если V’ V, Г’ Г, т. е. к исходному графу применены обе описанные выше операции.

Путем длины n является последовательность (не обязательно различных) дуг (u1, u2, …, un) таких, что для соответствующей последовательности n + 1 вершин v0, v1, …, vn справедливо ui = (vi-1, vi) для i = 1, 2, …, n (т. е. конец предыдущей дуги совпадает с началом следующей).

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

Путь называется замкнутым, если v0 = vn, и незамкнутым, если v0 vn.

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

Контуром называется замкнутый путь, когда v0 = vn. Элементарным контуром называется контур с различными вершинами (кроме начальной и конечной, которые совпадают).

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

Ориентированным деревом (прадеревом), растущим из корня v0, называется граф G = (V, U), если: 1) существует единственная вершина v0 (корень дерева), в которую не заходит ни одна дуга; 2) в каждую другую вершину заходит только одна дуга (только одна вершина предшествует вершине vi); 3) граф не содержит контуров.

Вершина vi называется висячей, если Гvi =, т. е. из vi не исходит дуга (нет следующей вершины), её также называют листом.

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

Орграфы и бинарные отношения Пусть V – множество объектов попарного (бинарного) сравнения.

Множество всех упорядоченных пар v, v’V обозначается V V (декартово произведение). Подмножество B V V называется бинарным отношением, т. е. (v, v’) B. Бинарные отношения легко представляются в виде орграфа, при этом вершины графа соответствуют объектам сравнения vi V, а дуги отображают бинарное отношение между объектами. Если (v, v’) B, то проводится дуга из v в v’, при этом v – начало, а v’ – конец дуги, т. е. дуга определяется парой (v, v’).

Описания специальных классов орграфов, не имеющих параллельных дуг, аналогичны терминологии бинарных отношений. Рефлексивным называется граф, имеющий петлю (v, v) в каждой вершине; симметрическим является граф, в котором каждой дуге u = (v, w) соответствует встречная дуга u’ = (w, v); транзитивным называется граф, в котором из существования дуг u1 = (v, v’) и u2 = (v’, v’’) следует существование дуги u3 = (v, v’’).

Выше были обозначены через Гv подмножество смежных вершинконцов дуг, имеющих началом вершину v, а через Г-v подмножество смежных вершин-начал дуг, имеющих концом вершину v.

Обозначим через Гnv подмножество тех вершин, в которые можно прийти из вершины v, используя пути длины n (или меньшей), а через Г- n v подмножество тех вершин, из которых можно прийти в вершину v, используя пути длины n (или меньшей).

Транзитивным замыканием называется многозначное отображение, определяемое следующей формулой:

vi = {vi}vi 2vi …, т. е. множество вершин, в которые можно прийти из вершины vi по некоторому пути без повторения дуг. Аналогично определяется обратное транзитивное замыкание:

-vi = {vi} -1vi -2vi …, т. е. множество вершин, из которых попадают в вершину vi по некоторому пути без повторения дуг.

Сильно связным графом G = (V, Г) называется граф, если, (vi V )Гvi = V, т. е. для любых двух вершин vi, vj существует путь, идущий из vi в vj.

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

Раздел 6. Булевы (переключательные) функции Понятие о булевых функциях (БФ); булевы операции и булева алгебра; способы задания БФ; представление БФ дизъюнктивными и конъюнктивными нормальными формами; эквивалентные преобразования формул; минимизация БФ; получение простых импликантов; теорема о функциональной полноте.

Булевыми (переключательными) функциями f(x1, x2, …, xn) называют такие функции, у которых все аргументы, как и сами функции, могут принимать лишь два значения. Эти значения, называемые булевыми, представляют двумя системами обозначений: {ложь, истина}, {0, 1}. Последнюю систему удобно использовать при разработке дискретных элементов преобразователей информации с двумя устойчивыми состояниями, например “высокое или низкое напряжение”. Булеву функцию f(x1, x2, …, xn) называют n-местной с областью значений из множества {0, 1} и со значениями аргументов из этого же множества. Область определения n-местной булевой функции может состоять максимум из 2n различных наборов значений n ее аргументов (кортежи (последовательности) из 0 и 1).

Конечность области определения и области значения булевой функции позволяет задавать функцию с помощью таблиц. Так как число наборов аргументов равно 2n, а на каждом наборе функция может принимать значения 0 или 1, то существует точно 22n различных булевых функций от n переменных. Число булевых функций от n переменных растет очень быстро: при n = 1 число функций равно 4; при n = 2 число функций равно 16; при n = 3 число функций равно 256 и т. д. Поэтому представляют таблицы одно- и двухместных булевых функций (табл. и 2), а на основе этих элементарных функций с помощью формул создают булевы функции любой сложности. Множество булевых функций от n переменных обозначим P.

n Булева функция f P существенно зависит от переменной xi, если n существует такой набор значений x1, …, xi-1, xi, xi+1, …, xn, что f (x1, …, xi-1, 0, xi+1, …, xn) f (x1, …, xi-1, 1, xi+1, …, xn). В этом случае xi называют существенной переменной, или фиктивной (несущественной) переменной, т. е. изменение значения фиктивной переменной не меняет значения функции. Например, f(x1, x2, x3) = g(x1, x2) означает, что при любых значениях x1, x2 f = g независимо от значения x3. Фиктивные переменные можно удалять из функции. Однако бывает полезно вводить их, чтобы обеспечить полный набор переменных.

Булевы функции одной переменной Таблица Обозна- Значения x ФиктивФункция Название чение 0 1 ные f0 Нуль 000х f1 Тождествен- хная x f2 Отрицание 1 f3 Единица 111х Булевы функции двух переменных Таблица Значения x:

Обозначе- 0 0 1 Функция Название Фиктивные Формула ние Значения y:

0 1 0 Нульf0 константа 0 0 0 0 0 x, y f1 Конъюн- x & y 0 0 0 1xy, ху кция (И) xy f2 Прямая анти- x y 0 0 1 импликация Переменная f3 x 0 0 1 1 y x х Обратная анxy f4 тиимплика- x y 0 1 0 ция Переменная f5 y 0 1 0 1 x y у xy v xy f6 Сложение x y 0 1 1 по mod x v y f7 Дизъюнкция x y 0 1 1 (ИЛИ) Стрелка xy f8 x y 1 0 0 Пирса Окончание таблицы Значения x:

Обозначе- 0 0 1 Функция Название Фиктивные Формула ние Значения y:

0 1 0 Эквивалентxy v xy f9 x y 1 0 0 ность Отрицание у y y f10 1 0 1 0 x (НЕ у) Обратная x v y f11 x y 1 0 1 импликация Отрицание х x f12 1 1 0 0 y x (НЕ х) x v y f13 Импликация x y 1 1 0 Штрих f14 xy 1 1 1 0 x v y Шеффера Единицаf15 1 1 1 1 1 x, y константа Более удобный аналитический способ задания булевых функций основан на использовании булевой алгебры функций с операцией суперпозиции. Суперпозицией функций f1, f2, …, fm называется функция f, полученная с помощью подстановок этих функций друг в друга и переименования переменных, а формулой называется выражение, описывающее эту суперпозицию, например, ( х у ). Формулу ху ху можно вычислить, если уже вычислены значения всех ее подформул.

Пример. Вычислить формулу (х3 х2) (х1 & (x1 x2)) на наборе х1 = 1, х2 = 1, х3 = 0. Используя табл. 2, получим:

х3 х2 = 1;

х1 &(x1 x2) = х1 0 = 0;

(х3 х2) (х1 & (x1 x2)) = 1 0 = 1.

О формуле, задающей функцию, говорят, что она реализует или представляет функцию. В отличие от табличного задания представление данной функции формулой не единственно. Например, используя множество функций {f1, f7, f12} (И, ИЛИ, НЕ), функцию f8 (стрелка Пирса) можно представить формулами:

х y = х y и х y = х y, а функцию f14 (штрих Шеффера) – формулами:

х | y = х y и х | y = хy.

Формулы, представляющие одну и ту же функцию, называются эквивалентными, или равносильными, что обозначается знаком равенства:

f8 = x y = x y, f14(x, у) = х у = ху.

Алгеброй булевых функций будем называть множество всех конечноместных булевых функций, рассматриваемое вместе с заданными на нем операциями отрицания, конъюнкции и дизъюнкции, т. е. алгебра вида (P, -, &, ), где P – множество n-местных булевых функций.

n n Пусть буквы латинского алфавита (с индексами или без них) обозначают произвольные элементы булевой алгебры (булевы функции). Одной из основных задач булевой алгебры является установление тождественных соотношений вида A(x, y, z, …) = B(x, y, z, …), где через А и В обозначены формулы булевой алгебры. Для упрощения формул вводятся следующие правила:

1) соблюдается старшинство операций (отрицание, конъюнкция и дизъюнкция), а при необходимости изменить порядок действий применяются скобки;

2) знак конъюнкции (умножения) может быть опущен;

3) отрицание над всем выражением позволяет не заключать его в скобки;

4) при выполнении подряд одноименных операций скобки можно опускать.

Правила и законы булевых операций аналогичны свойствам операций алгебры множеств, рассмотренным выше:

Ассоциативность (возможность опускать скобки):

а) х(уz) = (xу)z = xyz б) (x v y) v z = x v ( y v z) = x v y v z (1) Коммутативность (перестановка операндов):

x v y = y v x а) ху = ух б) (2) Идемпотентность (отсутствие степеней и коэффициентов):

x v x = x а) хх = х б) (3) Дистрибутивность конъюнкции относительно дизъюнкции:

x v yz = (x v y) v (x v z) (4) Дистрибутивность дизъюнкции относительно конъюнкции:

x( y v z) = xy v z (5) Закон двойного отрицания: x = x (6) Закон противоречия: xx = 0 (7) Закон “исключенного третьего”: x v x = 1 (8) Свойства констант:

х&1 = x, (9) x&0 = 0, (10) x v 1 = 1, (11) x v 0 = 0, (12) = 0, (13) = 1. (14) Правила де Моргана (для трех операций булевой алгебры):

а) (15) ху = х у, б) (16) х у = х у.

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

Pages:     | 1 || 3 | 4 |   ...   | 5 |






















© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.