На головну

Алгоритм Магу для визначення безлічі внутрішньої стійкості графа

  1.  G 4.2 Герундій у функції правого визначення
  2.  I 2.2 Інфінітив у функції визначення. Інфінітив після прикметників
  3.  I. Визначення.
  4.  II. Вивчити і представити класифікацію вищеперелічених товарних груп у вигляді схем, таблиць, алгоритмів, малюнків.
  5.  II. Перевірка правильності визначення оподатковуваних оборотів, обчислення податків і зборів.
  6.  III. визначення
  7.  quot; Визначення "- словниковий підсумок всієї філософії Платона

Нехай дано граф  . Для даного графа існує безліч внутрішньої стійкості .

Введемо булева змінна  , Яка визначається наступним чином:

 , Якщо вершина  належить множині внутрішньої стійкості ;

 , Якщо вершина  не належить безлічі внутрішньої стійкості ;

Введемо булева змінна :

 , Якщо між i-тій та j-тій вершиною є дуга;

 , Якщо між i-тій та j-тій вершиною немає дуги.

Тоді визначення внутрішньої стійкості (3.4) може бути представлено в наступному вигляді:

 (3.5)

Або використовуючи булевої алгебри:

 (3.6)

Застосовуючи формули равносильности, перетворимо:

 (3.7)

Розглянемо вираз:

 (3.8)

якщо  , То це рівність є тавтологією.

якщо  , То рівність має вигляд:

 (3.9)

Дане рівняння лежить в основі алгоритму Магу

алгоритм Магускладається з наступних етапів:

1. Для графа складається матриця суміжності.

2. По таблиці суміжності виписуються всі парні диз'юнкції.

3. Вираз приводиться до ДНФ.

4. Для будь-якої елементарної кон'юнкції виписуються відсутні елементи, які і утворюють безліч внутрішньої стійкості.

ПРИКЛАД

Дан граф


Мал. 3.7 Граф

Матриця суміжності має вигляд:

 
 
     
     
     

Для всіх одиниць виписуються парні диз'юнкції:

 (3.10)

Наведемо вираз до ДНФ:

 (3.11)

Безлічі внутрішньої стійкості:

Числом внутрішньої стійкості  = 2.

 




 Булеві функції та їх властивості. |  Функціональна повнота. Теорема Поста. |  Логіка предикат. |  Логічні операції над предикатами. |  Квантові операції. |  Рівносильні формули логіки предикатів. |  ТЕОРІЯ графів |  матрицею інцидентності |  матрицею суміжності |  Ейлеров граф. |

© um.co.ua - учбові матеріали та реферати