Побудова геометричних орграфов на підставі матриць

Ставлення 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 дуг, тобто Х =<, , ,>,

Матриця інцидентності орграфа G матиме 4 рядки і 12 стовпців

Петлі відповідає нульовий стовпець. Матриця інцидентності тільки вказує на наявність петель в орграфе, але не вказує, яким вершин ці петлі інцидентні.

3. Задана симетрична матриця А невід'ємних цілих чисел.

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

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

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

Побудуємо граф по заданій матриці суміжності.

Оскільки дана матриця є симетричною матрицею четвертого порядку з невід'ємними елементами, то їй відповідає неорієнтовані граф з чотирма вершинами. Розташувавши вершини на площині довільним чином (рис. 3), з'єднуємо їх з урахуванням кратності ребер.

На площині будуємо 4 точки. Позначимо їх через

Мал. 4. Ізоморфне орграф G = (X, U).

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

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

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

Матриця інцидентності орграфа G матиме 4 рядки і 17 стовпців

4. Задана формула Від формули перейти до еквівалентної їй формулою так, щоб формула не містила зв'язок «» і «». Виходячи з істиннісних таблиць, довести, що формули і так само сильні (логічно еквівалентні). Для формули СКНФ і СДНФ.

Рішення. Як відомо, всі формули логіки висловлювань можна записати за допомогою пропозіціональних зв'язок. тобто пропозіціональние зв'язки можуть бути визначені в термінах зв'язок Можна довести, що

Використовуючи рівності (1) - (3) і основні закони

21 - 30. Задана симетрична матриця A невід'ємних цілих чисел.

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

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