Построение геометрических орграфов на основании матриц

Отношение 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.