 |
Определение III формы для функции k-значной логики. Аналогом какой формы для функции 2значной логики она является?
|
|
|
|
III форма для функции k-значной логики – способ представления функции f(x1..xn), являющийся аналогом СКНФ для функций двузначной логики. f(x1..xn)=min(max(f(s1..sn), ~Js1(x1), ~Js2(x2)… ~Jsn(xn)),…) Где минимум берётся по всем наборам f(s1.. sn) значений переменных х1..xn.
11 Представление функций ji(x) полиномом по модулю k
J0(x)=1-xk-1 j s=1-(x-s)k-1 и подставляем их во II форму с учётом mod k
Определение полинома по модулю k для функции 1 переменной.
F(x)=f( x1)*j0(x)+…+f(xk)*jk-1(x)
13 Теорема о представлении функции полиномом по модулю k. Можно ли разложить в полином функцию j0(x) при k=25?
Теория графов
Абстрактный граф
Абстрактный граф – это граф заданный непустым множеством вершин V={V1, V2..Vn}, множеством ребер x(Vi, Vj).
Абстрактный ориентированный граф
Абстрактный ориентированный граф – задается непустым множеством вершин V={V1, V2..Vn}, множеством ребер x(Vi, Vj) (с упорядоченным направлением из Vi в Vj).
Кратные рёбра и петли
Кратные ребра – ребра с общими вершинами. Петля – ребро, концы которого совпадают.
Смежные вершины, изолированные вершины
Смежные вершины – 2 вершины инцидентные одному ребру.
Изолированная вершина - вершина, степень которой равна 0 (то есть нет ребер, инцидентных ей).
Псевдограф (ориентированный псевдограф)
Псевдограф - граф, который может содержать петли и/или кратные рёбра.
Мультиграф (ориентированный мультиграф)
Мультиграф – граф, который может содержать кратные ребра, но не содержащий петель.
Матрица смежности графа (орграфа)
Матрица смежности – это матрица n x n (где n – число вершин), в которой каждый элемент а(i,j) равен числу ребер, соединяющих V(i) и V(j).
Определение полного и двудольного графа
Полный граф - граф, у которого каждая пара вершин соединена ребром. Полный n -вершинный граф обозначается Gn.
|
|
|
Двудольный граф - граф, у которого существует такое разбиение множества вершин на две части (доли), что концы каждого ребра принадлежат разным долям. Если при этом любые две вершины, входящие в разные доли, смежны, то граф называется полным двудольным.
Матрица инцидентности неориентированного графа
Матрица инцидентности графа – это матрица n x m, в которой b(i,j)=0 если v(i) не инц x(j), 1 если v(i) инц ребру x(j).
Матрица инцидентности орграфа
Матрица инцидентности орграфа – это матрица n x m, в которой b(i,j)=0 если v(i) не инц x(j), 1 если v(i) – конец x(j), -1 если v(i) начало x(j).
Степень вершины, полустепени захода и полустепени исхода в орграфе.
Степень вершин графа – deg V(i)= число инц. ребер. Вклад петли = 2
Полустепень: Исхода deg- V(i)- число выходящих ребер. Захода deg+ V(i) – число заходящих ребер. Для петли вклад в полустепени и исхода и захода =1
Найти сумму степеней всех вершин в графе
сумма deg V(i)=2m (где m – число ребер)
Найти сумму полустепеней исхода (захода) в орграфе
сумма deg+ V(i)+ deg- V(i)=2m
Как найти степень вершины по матрице смежности мультиграфа?
Deg V(i)=сумма элементов i строки или i столбца
Как найти степень вершины по матрице инцидентности графа?
Сумма элементов i - ой строки матрицы инцидентности графа равна Deg V(i)
Как найти полустепень исхода (захода) по матрице смежности ориентированного мультиграфа?
Сумма элементов i - ой строки матрицы смежности ориентированного мультиграфа равна Deg-V(i), а сумма элементов i – го столбца – Deg+ V(i)
Изомрфный граф
Графы и изоморфны, если существует такое взаимно однозначное соответствие между множествами их вершин v и v’, что вершины соединены ребрами в одном из графов в том и только том случае, когда соответствующие им вершины соединены в другом графе.
Подразбиения ребра (дуги)
|
|
|
Операция подразбиения (измельчения) дуги (u, v) в орграфе D = (V, E) состоит в удалении из Е дуги (u, v), добавлении к V новой вершины w и добавлении к Е | {(u, v)} двух дуг (u, w), (w, v). Аналогично определяется операция подразбиения ребра в графах.
Гомеоморфные графы
Орграфы D1, D2 называются гомеоморфными, если существуют их подразбиения, являющиеся изоморфными.
Правильно реализованный граф
граф называется правильно реализованным (или правильным), если его дуги не имеют общих точек, отличных от вершин графа.
20. Плоский (планарный) граф
Планарный граф — граф, который может быть изображён на плоскости без пересечения ребер.
21. нарисовать графы G5 и G3,3 . Являются ли они планарными?
Теорема Понтрягина-Куратовского
Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных К5 или К3,3 .
Маршрут в графе (пути в орграфе)
Маршрут в графе (путь в орграфе) из вершины i в вершину j – последовательность вершин и ребер (дуг), инцидентных двум соседним вершинам.
Длина маршрута, пути
Длиной маршрута(пути) называется количество ребер(дуг) в нем.
25. цепь, простой цепь
Цепь (орцепь) – маршрут (путь), в котором ребра (дуги) проходятся один раз. Простая цепь (простая орцепь) – цепь (орцепь) без повторяющихся вершин.
|
|
|
