Решение задач с прямым использованием логики

Применение логики предикатов в теории графов

Теория графов — одна из наиболее широко распространенных математических теорий, широко используемая в технических науках.

Графом называется пара (G, U), где G — множество вершин; U — множество ребер (пары вершин (а> b)), ребра представляют бинарные отношения и могут быть определены двуместными предикатами.

Граф имеет наглядное графическое отображение, что позволяет наблюдать важные свойства и ставить и легко решать задачи интуитивно, внедрять наблюдаемые методы в программы компьютеров.

Граф неориентированный определен неупорядоченным списком вершин, например коммутативной операцией а & b или aw b в зависимости от того, какие свойства необходимо представлять: Р(х, у) = «х соединен с у» = (х w у).

Пример неориентированного графа изображен на рис. 5.4.

Пример неориентированного графа

Рис. 5.4. Пример неориентированного графа

Логическое описание неориентированного графа, представленного на рис. 5.4:

В качестве примера использования неориентированного графа рассмотрим следующую задачу.

Пример 5.4

Найдем число красок, достаточных для окраски вершин графа на рис. 5.4 так, чтобы никакие смежные вершины не были окрашены в один цвет.

Задача сводится к выбору разбиения графа на несвязные подмножества вершин.

Используем следующее утверждение. Всякая вершина входит в некоторое несвязное подмножество:

Выбираем стратегию исключения связанных дизъюнктами вершин, выделяя произвольную начальную вершину х.

Пусть выбрана вершина S = {1}. Связанные с ней вершины могут быть исключены. В данном случае связанные вершины {1, 2, 3, 6} входят в общие дизъюнкты U(x, у) = = v у). Исключение связанных вершин х, у е {1, 2, 3, 6}, а также ребер, соединяющих вершины из множества {1, 2, 3, 6} с другими вершинами графа, можно рассматривать как применение правила поглощения х(х v у) = х. Остаются вершины 4, 5 и ребро (4 v 5). В подграфе G1 = {4, 5} выбирается вершина 4, нс связанная с 1 из G. Получим несвязное подмножество S= {1,4}. Исключая вершины, связанные с вершиной 4, получаем G2 = 0, что обозначает завершение выбора несвязного подмножества S.

Аналогичным образом находим подмножества 51 = {2, 3, 5}, 52 = {6}.

Таким образом, несвязные подмножества S = {1, 4}, 51 = {2, 3, 5}, 52 = {6} можно окрасить тремя красками.

Демонстрация решения позволяет определить шаги алгоритма, связать с ними процедуры и условия ветвления в компьютерной программе.

Пример ориентированного графа представлен на рис. 5.5. Ориентированный граф имеет упорядоченные пары вершин (а —> Ь).

Пример ориентированного графа

Рис. 5.5. Пример ориентированного графа

Логическое описание ориентированного графа, представленного на рис. 5.5, на множестве ориентированных ребер:

В качестве примера использования ориентированного графа рассмотрим следующую задачу.

Пример 5.5

Поиск минимального пути на графе (см. рис. 5.5) между двумя вершинами. Пусть выбраны две вершины: 1 — начальная и 2 — конечная.

В логике решаем задачу вывода обратным методом с использованием правила резолюции.

На первом шаге 1(—il v 3) —> 3 и пара (-«1 v 3) из списка вычеркивается.

На следующем шаге проверяем другие возможные направления движения: 1 (—•! v v б) —^ б, и пара (-il v 6) вычеркивается.

Далее возможно движение начиная с вершины 3 или 6. Выбираем вершину 6.

Следующая возможна только вершина 5: 6(—16 v 5) —» 5, и пару (-16 v 5) вычеркиваем.

За ней следующей возможна только вершина 4: 5(—15 v 4) —> 4, и ребро (-i5 v 4) вычеркиваем.

Текущее состояние списка:

Возможен выбор двух направлений:

  • 4(—14 v 3) —> 3(—13 v 6) —> 6 — зацикливание (вершина уже есть в списке вершин выбранной трассы), вычеркиваются из списка ребра (-4 v 3), (-»3v6);
  • 4(—14 v 2) —> 2 — конечная вершина трассы, и в списке находим -i2, формула является противоречием, что доказывает истинность достижения вывода 2.

Текущее состояние списка:

Искомый путь: 1 —> 6 —> 5 —> 4 —> 2.

Движение через вершину 3 позволило бы найти гамильтонов цикл, проходящий через все вершины графа: 1—>3—>6—>5—>4—» 2 —» 1.

Заданная фигура к примеру 5.6

Рис. 5.6. Заданная фигура к примеру 5.6

Программа вводит координаты точки, вычисляет логическое выражение, определяющее принадлежность точки области, и выводит полученную логическую величину на экран.

Логическая схема алгоритма контроля попадания точки в заштрихованную область приведена на рис. 5.7.

Логическая схема алгоритма контроля попадания точки в заштрихованную область

Рис. 5.7. Логическая схема алгоритма контроля попадания точки в заштрихованную область

Здесь не обозначены в явном виде предикаты ввода и вывода — после чего могут быть интерпретированы все входные предикаты программы.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >