На головну

Внутрішня стійкість графа

  1.  V Головне в творчості не зовнішня активність, а внутрішня.
  2.  А. А. Кизеветтер. Внутрішня політика в царювання Миколи Павловича // Історія Росії в XIX столітті. Дореформена Росія. М., 2001.
  3.  А. С. Шишков наводить свідчення вченого іноземця, графа Мейстера.
  4.  Алгоритм Магу для визначення безлічі внутрішньої стійкості графа
  5.  Алгоритм отримання дерева з графа
  6.  Алгоритм приведення графа до ярусно-паралельній формі.
  7.  Аналіз графа моделі Керка

Безліч внутрішньої стійкості - Безліч несуміжних вершин графа.

a

 f b


 e c


d

  a b c d e f
a          
b        
c          
d        
e          
f      

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

Класичний приклад, завдання про восьми ферзів: Як розставити на шахівниці вісім ферзів, щоб вони не били один одного. Тобто побудувати граф з 64 вершинами (клітинами), де кожна клітинка з'єднана з клітинами, які знаходяться під боєм. Максимальні безлічі несуміжних вершин і дають рішення цього завдання.

Довго це завдання було класичним полігоном для систем штучного інтелекту, як творче завдання, що використовує несуворі (евристичні) методи.

Останні роки ситуація змінилася.

Для знаходження таких множин з'явився чудовий алгоритм Магу, який,

Фактично дає аналітичне (!) Рішення цього завдання.

Алгоритм Магу.

1. За одиницям матриці будуємо парні диз'юнкт.

(А U b) (a U c) (b U e) (c U f) (d U b) (d U e) (e U c) (f U b) (f U d) (f U e)

2. Перетворимо в ДНФ, виконавши всі можливі поглинання і операції ідемпотентності.

Отримаємо: bcde U bcef U adef U afeb U fbdc

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

{A, f}, {a, d}, {a, e}, {b, c}, {c, d}

Максимальна з таких множин дає число внутрішньої стійкості (Тут воно дорівнює 2).




 виходів |  мінімізація автоматів |  Перехід від автомата Мура до автомату Мілі і навпаки |  теорія графів |  теорема Ейлера |  Повні графи і дерева |  дерева |  алгоритм Краскала |  Завдання про 4 фарбах |  Визначення шляхів в графі |

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