Переписывание графов

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