Сети. Сетевые модели представления информации

В этом проглядывается талант исследователя охватить значительные районы явлений с помощью немногочисленных допущений, представить разносторонние совокупности предметов и процессов в сжатой, компактной форме.

А. Сухотин

Граф называется взвешеннымили сетью,если каждому его ребру поставлено в соответствие некоторое число (вес). Взвешенными графами могут быть схемы в электронике, электрические схемы, карты автомобильных и железных дорог и др. Например, на картах автодорог вершины являются населенными пунктами, ребра — дорогами, а весом — числа, равные расстоянию между населенными пунктами.

В строительстве сетевые графы применяются для наглядного изображения некоторого комплекса работ или производственных процессов. Ребрам графа могут соответствовать числа, означающие длину, уклон, запланированное время и другие характеристики.

Например, последовательность работ для монтажа каркаса здания изображена в виде графа (рис. 2.20).

Числами обозначены технологические операции:

1 — рытье котлована;

2 — монтаж фундамента;

3 — завоз металлоконструкций;

4 — монтаж подъемного крана;

5 — монтаж каркаса здания.

На рис. 2.21 изображен сетевой граф некоторого комплекса раб в виде взвешенного графа с указанием времени, затраченного выполнение этой работы (в минутах).

В основе процесса планирования лежит некоторый сценарл представляющий собой сеть, состоящую из вершин — пошагового описания действий и дуг — отношений между ними. Такой дает возможность, сравнивая альтернативы, планировать действия для достижения поставленной цели.

Рис. 2.20. Диаграмма последовательности работ при строительстве здания

Сети широко используются в качестве моделей для представления знаний в интеллектуальных системах. Сетевая модель представления информации основана на том, что любые знания можно рассматривать как множества объектов (понятий) и связи между ними (отношения).

Понятия-объекты и другие элементы предметной области могут быть графически изображены в виде вершин, а отношения между ними — в виде дуг, связывающих эти вершины. Такое физическое представление информации (знаний) в интеллектуальных системах носит название семантических сетей.Они являются универсальным средством для представления знаний в интеллектуальных системах. Понятия, входящие в сети, можно описать с помощью фрейма. Фреймомназывается минимально возможное описание сущности некоторого явления, объекта, события процесса. Состоит фрейм из набора стандартных единиц — слотов, содержащих определенный минимум информации о его содержании и назначении. Семантическая сеть в виде некоторой ее совокупности фреймов нуждается в указании отношения между ее вершинами, что тоже возможно осуществить в виде слота. Семантические сети широко применяются в информатике, например, для операций поиска по образцу,где в виде сетей представляется база данных. Результат такого поиска можно изобразить графом. Используются сети и для графической иллюстрации системы отношений базы данных.

Широко применяются сети для графического изображения различных логических схем в теории автоматов, например схемы с памятью, у которых каждый узел F(i) — функция алгебры логики (см., например, рис. 4.17, 4.18).

Для формального описания совокупности процессов, протекающих одновременно, используют сети Петри.Они представляют собой ориентированные графы, состоящие из вершин двух видов: некоторых позиций и переходов, причем позиции изображают кружочками, а переходы — «планками» (рис. 2.22). Сети Петри предназначены для описания действия дискретных процессов во времени. Такие сети дают возможность моделировать ситуации протекания параллельных процессов, прослеживать возможные варианты их взаимодействия, выявлять нежелательные ситуации. Также в виде сетей изображаются схемы устройств, например радиоприемника или телевизора.