Множества. Комбинаторика. Отношения (стр. 13 )

г) {Ø}; Ответ: не полна

д) {½}; Ответ: полна

е) {¯}; Ответ: полна

ё) {Å, Ù, 1}; Ответ: полна

ж) {Þ, 0}. Ответ: полна.

2.2.8. Предполные классы

Класс булевых функций называется предполным, если он неполный, но при добавлении к нему любой функции, ему не принадлежащей, становится полным. Из определения следует, что предполный класс замкнут.

ТЕОРЕМА (Поста). Классы Т0, Т1, L, M, S предполные. Других предполных классов нет.

Доказательство. Если f0 Ï T0,, то f0(x,…, x) = 1 или `x. В первом случае в [T0 È {f0}] появляется полная система 0, 1, Ù, Å, а во втором тоже полная система Ù, Ø. Отсюда, Т0 – предполный класс.

Если f1 Ï T1, то f1(x,…, x) = 0 или `x. В первом случае в [T1 È {f1}] появляется полная система `х=( хÞ 0), Ù, Ú, а во втором та же полная система Ù, Ú, Ø. Отсюда, Т1 – предполный класс.

Если f2 Ï S, то по лемме в [S È {f2}] появляются 0 или 1, а благодаря отрицанию, обе константы 0 и 1. С помощью самодвойственной функции h(x, y, z) = xyÚxzÚyz и константы 0 можно получить конъюнкцию h(x, y, 0)= ху. Наличие Ù, Ø означает полноту множества [S È {f2}]. Отсюда, S0 – предполный класс.

Если f3 Ï M, то по лемме`x Î [M È {f3}]. С учетом того, что конъюнкция и дизъюнкция функции монотонные получаем предполноту класса М.

Если f4 Ï L, то по лемме о нелинейной булевой функции можно построить конъюнкцию или отрицание конъюнкции. Так как `х Î L, то Ù, Ø Î [L È {f4}] Þ L – предполный класс.

Пусть N – предполный класс, отличный от каждого из важнейших замкнутых классов. По теореме Поста о полноте функциональной системы такой класс полный. <

2.2.9. Замкнутые классы

Из теоремы Поста следует, что любой замкнутый класс полностью принадлежит одному из важнейших замкнутых классов. Американский математик Эмиль Пост осуществил исследование структуры замкнутых классов в том же плане, в котором было изучено множество Р2.

Система функций из замкнутого класса N называется полной, если ее замыкание совпадает с этим классом N. Система функций из N называется базисом N, если она полна в N и независима. Например, можно показать, что система 0, 1, Ù, Ú – базис класса М. Приведем без доказательства теоремы:

ТЕОРЕМА. Замкнутый класс имеет конечный базис. <

ТЕОРЕМА. Замкнутых классов в Р2 счетное число. <

1. Краткий перечень основных понятий теории графов

1.1. Общие понятия

Графы помогают описывать и исследовать различные системы объектов и их связи. Например, в графе, изображенном на рис. 1, точки (вершины графа) можно интерпретировать как города, а линии, соединяющие вершины (ребра), как дороги, соединяющие эти города.

Рис. 1.

Формальное определение графа таково [1-9]. Графом Г=(V,X) называется пара множеств: V – множество, элементы которого называются вершинами, X – множество неупорядоченных пар вершин, называемых ребрами. Если v, w Î V, x=(v,w)ÎX, то говорят, что ребро x соединяет вершины v и w или x инцидентно v и w. Таким образом, {v, w} – обозначение ребра. Если Х представляет собой упорядоченные пары (т. Е. X – подмножество декартова произведения V×V), то граф называется ориентированным, а пары {v, w} называют дугами. Если множеству X принадлежат пары v=w, то такие ребра (v,v) называют петлями. Существование одинаковых пар {v, w} соответствует наличию параллельных или кратных ребер (дуг), а кратностью ребер называют количество таких одинаковых пар.

Например, кратность ребра {v1, v2} в графе, изображенном на рис. 2, равна двум, кратность ребра {v3, v4} − трем.

Рис.2.

Псевдограф − граф, в котором есть петли и/или кратные ребра.

Мультиграф − псевдограф без петель.

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

Итак, используемые далее обозначения:

V – множество вершин;

X – множество ребер или дуг;

v (или vi)– вершина или номер вершины;

G, G0 – неориентированный граф;

D, D0 – ориентированный;

{v,w} − ребра неориентированного графа;

{v,v} – обозначение петли;

(v,w) − дуги в ориентированном графе;

v,w – вершины, x,y,z – дуги и ребра;

n(G), n(D) количество вершин графа;

m(G) – количество ребер, m(D) – количество дуг.

Примеры

1) Ориентированный граф D=(V, X), V={v1, v2, v3, v4},

X={x1=(v1,v2), x2=(v1,v2), x3=(v2,v2), x4=(v2,v3)}.

Рис. 3.

2) Неориентированный граф, изображенный на рис. 4:

G=(V, X), V={v1, v2, v3, v4, v5},

X={x1={v1,v2}, x2={v2,v3}, x3={v2,v4}, x4={v3,v4}}.

Рис. 4.

1.2. Понятия смежности, инцидентности, степени

Если x={v,w} - ребро, то v и w − концы ребра x.

Если x=(v,w) - дуга ориентированного графа, то v − начало, w – конец дуги.

Вершина v и ребро x неориентированного графа (дуга x ориентированного графа) называются инцидентными, если v является концом ребра x (началом или концом дуги x ).

Вершины v, w называются смежными, если {v,w}ÎX.

Степенью вершины v графа G называется число d(v) ребер графа G, инцидентных вершине v.

Вершина графа, имеющая степень 0 называется изолированной, а степень 1 – висячей.

Полустепенью исхода (захода) вершины v ориентированного графа D называется число d+(v) (d-(v)) дуг ориентированного графа D, исходящих из v (заходящих в v).

Следует заметить, что в случае ориентированного псевдографа вклад каждой петли инцидентной вершине v равен 1 как в d+(v), так и в d-(v).

1.3. Маршруты и пути

Последовательность v1x1v2x2v3…xkvk+1, (где k³1, viÎV, i=1,…,k+1, xiÎX, j=1,…,k), в которой чередуются вершины и ребра (дуги) и для каждого j=1,…,k ребро (дуга) xj имеет вид {vj,vj+1} (для ориентированного графа (vj,vj+1)), называется маршрутом, соединяющим вершины v1 и vk+1 (путем из v1 в vk+1).

Пример

В графе, изображенном на рис.4, v1x1v2x2v3x4v4x3v2 – маршрут, v2x2v3x4v4 – подмаршрут;

маршрут можно восстановить и по такой записи x1x2x4x3 ;

если кратности ребер (дуг) равны 1, можно записать и так v1v2v3v4v2 .

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

Цикл − замкнутая цепь (в неориентированном графе).

Контур − замкнутый путь (в ориентированном графе).

Простой путь (цепь) − путь (цепь, цикл, контур), в котором ни одна дуга/ребро не встречается дважды.

Простой цикл (контур) − цикл (контур), в котором все вершины попарно различны.

Гамильтонова цепь (путь, цикл, контур) − простая цепь (путь, цикл, контур), проходящая через все вершины.

Эйлерова цепь (путь, цикл, контур) − цепь (путь, цикл, контур), содержащая все ребра (дуги) графа по одному разу.

Длина маршрута (пути) − число ребер в маршруте (дуг в пути).

Утверждение 1. Для того чтобы связный псевдограф G обладал Эйлеровым циклом, необходимо и достаточно, чтобы степени всех его вершин были четными.