Reescrita de grafos

Na Teoria dos Grafos, reescrita de grafos denota um sistema de reescrita para grafos, isto é, um conjunto de regras de reescrita de grafos da forma , sendo o grafo usado como padrão (no lado esquerdo) e o grafo de substituição (no lado direito da regra). Uma regra de reescrita de grafos é aplicada ao grafo hospedeiro procurando por uma ocorrência do grafo padrão (resolvendo assim o problema do isomorfismo de subgrafos) e substituindo a ocorrência encontrada por uma instância do grafo de substituição. Algumas vez gramática de grafos é usado como um sinônimo para sistema de reescrita de grafos, especialmente no contexto de linguagens formais; a expressão distinta é usada para enfatizar o objetivo de enumerar todos os grafos a partir de um grafo inicial, isto é, descrevendo uma linguagem de grafos (como em uma gramática de atributos), em vez de transformar um estado dado (um grafo hospedeiro) em um novo estado.