О ПРОЦЕДУРЕ ПОРОЖДЕНИЯ МАКСИМАЛЬНЫХ ПУСТЫХ ПОДГРАФОВ
Практическая значимость комбинаторных задач связана с развитием искусственного интеллекта, который из теоретической области переместился в востребованную практическую сферу. Большое число интеллектуальных задач достаточно естественно переформулируются на языке графов, и для их решения требуется использование теоретико-графовых методов. В частности, большое число задач по описанию разнообразных предметных областей сводится к так называемым графам ортогональности, которые очень естественно позволяют описывать различные соотношения объектов предметной области. В свою очередь для исследования графов ортогональности необходимо проводить исследование совокупностей их максимальных пустых подграфов, что требует достаточно эффективной процедуры порождения последних. При этом должны учитываться определенные условия, которым должны удовлетворять пустые подграфы. Как правило, условия суть следствия, вытекающие из содержательных ограничений на объекты предметной области. Поэтому актуальным представляется создание процедуры порождения в определенном смысле полной совокупности пустых подграфов по заданному графу ортогональности, которая позволила бы учитывать содержательные особенности предметной области. К последним следует отнести в первую очередь отношение близости объектов, которое позволяет существенно снижать перебор при порождении пустых подграфов. В статье представлен теоретический базис такой процедуры, порождающей полную совокупность максимальных пустых подграфов заданного графа ортогональности, и краткое ее описание. Процедура получает на входе матрицу смежности графа, реализована на языке С++ и показала неплохие результаты при порождении объектов предметной области, заданной графом ортогональности. Отличительной ее особенностью является возможность учитывать различные соотношения локальности объектов предметной области, что существенно ускоряет работу.