Отношение x > y обладает следующими свойствами: Оно антирефлексивно, так как ни для каких х не имеет места x > x, орграф отношения не имеет петель. Оно асимметрично, так как для двух

Отношение x > y обладает следующими свойствами:

1. Оно антирефлексивно, так как ни для каких х не имеет места x > x, орграф отношения не имеет петель.
2. Оно асимметрично, так как для двух чисел имеет место только соотношение x > y.
3. Оно транзитивно, так как если x > y и y > z, то x > z, орграф отношения является транзитивным, т.е. существуют замыкающие дуги: и влечет и т.д.

Пример 5. Задана матрица

Нарисовать на плоскости орграф G = (X, U), единственный с точностью до изоморфизма, имеющий заданную матрицу В своей матрицей смежности. Найти матрицу инцидентности орграфа G.

Решение. Заданная матрица смежности В имеет 4 строки и 4 столбца, следовательно, орграф имеет 4 вершины. Обозначим их соответственно , , , . Матрицу В перепишем в виде

.

Построим на плоскости 4 точки и обозначим их , , , .

Рис. 22. Изоморфный орграф G = (X, U).

Так как , то при вершине нет петель, , значит из вершины исходят 2 стрелки к вершине . Рассуждая таким же образом, построим геометрический орграф, изоморфный орграфу G = (X, U), для которого матрица В является матрицей смежности (рис. 22).

Теперь запишем матрицу инцидентности С для орграфа G.

Построенный орграф G = (X, U) имеет 4 вершины и 12 дуг, т.е. Х={ , , , },

U= .

Матрица инцидентности орграфа G будет иметь 4 строки и 12 столбцов

Петле соответствует нулевой столбец. Матрица инцидентности только указывает на наличие петель в орграфе, но не указывает, каким вершинам эти петли инцидентны.

3. Задана симметрическая матрица А неотрицательных целых чисел.

1. Нарисовать на плоскости граф (единственный с точностью до изоморфа), имеющий заданную матрицу А своей матрицей смежности. Найти матрицу инцидентности графа G.

2. Нарисовать на плоскости орграф (единственный с точностью до изоморфизма), имеющий заданную матрицу А свое матрицей смежности. Найти матрицу инцидентности орграфа G.

А=

Решение1. Напомним, что матрицей смежности графа с множеством вершин называется матрица размера , в которой элемент равен числу ребер в G, соединяющих с . Матрица смежности графа G является симметрической, то есть

= .

Построим граф по заданной матрице смежности.

Поскольку данная матрица является симметрической матрицей четвертого порядка с неотрицательными элементами, то ей соответствует неориентированный граф с четырьмя вершинами. Расположив вершины на плоскости произвольным образом (рис. 3), соединяем их с учетом кратности ребер.

А=

Рис. 3 Граф G=(X,U)

Теперь найдем матрицу инцидентности графа G =(X,U).

Напомним определение матрицы инцидентности графа G=(X,U) с множеством вершин и множеством ребер Так называется матрица размера , у которой

2. Заданная матрица А имеет 4 строки и 4 столбца, следовательно орграф имеет 4 вершины. Обозначим их соответственно а матрицу представим в виде

На плоскости строим 4 точки. Обозначим их через

Рис. 4. Изоморфный орграф G=(X,U).

Так как то при вершине имеется петля; значит, из вершины выходят две стрелки к вершине и т.д. (рис.4).

Теперь запишем матрицу инцидентности С для орграфа G.

Построим орграф G=(X,U) имеет 4 вершины и 17 дуг, т.е.

Матрица инцидентности орграфа G будет иметь 4 строки и 17 столбцов

4. Заданная формула От формулы перейти к эквивалентной ей формуле так, чтобы формула не содержала связок «» и «». Исходя из истинностных таблиц, доказать, что формулы и равно сильны (логически эквивалентны). Для формулы СКНФ и СДНФ.

Решение. Как известно, все формулы логики высказываний можно записать при помощи пропозициональных связок: т.е. пропозициональные связки могут быть определены в терминах связок Можно доказать, что

(1)

(2)

(3)

Используя равенства (1) – (3) и основные законы

21 – 30. Задана симметрическая матрица A неотрицательных целых чисел.

1. Нарисовать на плоскости граф G=(X,U) (единственный с точностью до изоморфизма), имеющий заданную матрицу А своей матрицей смежности. Найти матрицу инцидентности

графа G.

2. Нарисовать на плоскости орграф G=(X,U) (единственный с точностью до изоморфизма)? Имеющий заданную матрицу А своей матрицей смежности. Найти матриц инцидентности

Орграфа G.

21. 22.

23. 24.

25. 26.

27. 28.

29. 30.

Дата добавления: 2015-09-29