Винесення квантора за дужки

3)Перестановка однойменних кванторів.

4)Перейменування пов'язаних змінних. Якщо замінити пов'язану змінну формули А інший змінної, що не входить до цієї формули, в кванторі і всюди в дію квантора отримуємо формулу, рівносильну А.

Обчислення предикатів базується на наведених вище властивостях та правилах, які називаються аксіомами.

Якими б не були формули А і В для них справедливі такіаксіоми :

2) (A Þ (B Þ C)) Þ ((A Þ B) Þ (A Þ C));

3) (ØB Ø ØA) Þ ((ØB Þ A) Þ B);

Кінцеві графи та мережі. Основні визначення.

Визначення. Якщо на площині задати кінцеву множину V точок і кінцевий набір ліній Х, що з'єднують деякі пари з точок V, то отримана сукупність точок і ліній буде називатисяграфом.

У цьому елементи множини V називаютьсявершинами графа, а елементи множини Х –ребрами.

У множині V можуть зустрічатися однакові елементи, ребра, що з'єднують однакові елементи, називаютьсяпетлями. Однакові пари у множині Х називаютьсякратними (або паралельними) ребрами. Кількість однакових пар

(v, w) у Х називаєтьсякратністю ребра (v, w).

Безліч V і набір Х визначають граф з кратними ребрами - псевдограф.

Псевдограф без петель називається мультиграфом.

Якщо в наборі Х жодна пара не зустрічається більше одного разу, мультиграф називаєтьсяграфом.

Якщо пари в наборі Х є упорядкованими, то граф називається орієнтованим абоорграфом.

Графу відповідає геометрична конфігурація. Вершини позначаються точками (кружечками), а ребра – лініями, що з'єднуютьвідповідні вершини.

Визначення. Якщох= v, w> – ребро графа, то вершиниv, wназиваються кінцями ребрах.

Якщох = (v, w)- дуга орграфа, то вершинаv- початок, а вершинаw- кінець дугих.

Визначення. Вершиниv, wграфа G = (V, X) називаютьсясуміжними, якщо v,w>ÎX. Два ребра називаютьсясуміжними, якщо вони мають спільну вершину.

Визначення.Ступенем вершини графа називається число ребер, яким ця вершина належить. Вершина називаєтьсяізольованою, якщо її ступінь дорівнює одиниці івисячої, якщо її ступінь дорівнює нулю.

Визначення. Графи G1(V1, X1) і G2(V2, X2) називаютьсяізоморфмними, якщо існує взаємно однозначне відображення j: V1 ® V2, що зберігає суміжність .

Визначення.Маршрутом (шляхом) для графа G(V, X) називається послідовність v1x1v2x2v3…xkvk+1. Маршрут називаєтьсязамкнутим, якщо його початкова та кінцева точки збігаються. Число ребер (дуг) маршруту (шляху) графа називаєтьсядовжиною маршруту (шляху).

Визначення. Незамкнений маршрут (шлях) називаєтьсяланцюгом. Ланцюг, у якому всі вершини попарно різні, називаєтьсяпростим ланцюгом.

Визначення. Замкнений маршрут (шлях) називаєтьсяциклом (контуром). Цикл, у якому всі вершини попарно різні, називаєтьсяпростим циклом.

Матриці графів.

Визначення.Матрицею суміжності орграфа D називається квадратична матриця A(D) = [aij] порядкуп, у якої

Визначення. Якщо вершинаvє кінцем ребрах, то кажуть, щоvіх-інциндентні.

Визначення.Матрицею інцидентності орграфа D називається матриця розмірностіп'тB(D) = [bij], у якої

Приклад. Записати матриці суміжності та інцидентності для графа, зображеного на малюнку.

Складемо матрицю суміжності:

v1	v2	v3
v1
v2
v3

Тобто. - матриця суміжності.

x1	x2	x3	x4
v1	-1
v2	-1	-1
v3	-1

Тобто.

Якщо граф має кратні дуги (ребра), то в матриці суміжності приймається aij=k , деk- кратність дуги (ребра).

За допомогою матриць суміжності та інцидентності завжди можна повністю визначити граф та всі його компоненти. Такий метод завдання графів дуже зручний обробки даних на ЕОМ.

Приклад. Задано симетричну матрицю Q невід'ємних чисел. Намалювати на площині граф G(V, X), що має задану матір Q своєю матрицею суміжності. Знайти матрицю інцидентності R графа G. Намалювати також орграф, що має матрицю суміжності Q, визначити його матрицю інцидентності.

x4

Складемо матрицю інцидентності:

x1	x2	x3	x4	x5	x6	x7	x8	x9	x10	x11
v1
v2
v3
v4

Разом:

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

x4

v2

x2 x7

х3 x6

x1 v1 х8 v3 x10 x11

Складемо матрицю інцидентності для орієнтованого графа.

Елемент матриці дорівнює 1, якщо точка є кінцем дуги, -1 якщо початком дуги, якщо дуга є петлею, елемент матриці запишемо як ±1.

Таким чином, операції з графами можна звести до операцій із їх матрицями.

---