Usuario:Jarcil13/Reescritura de grafos

En ciencias de la computación, la transformación de grafos o la reescritura de grafos consiste en la técnica de crear un nuevo grafo a partir de uno original algoritmicamente. Tiene numerosas aplicaciones, variando de ingeniería de software (construcción de software y también verificación de software) a algoritmos de diseño y generación de imagenes.

La reescritura de grafos pueden ser utilizada como la abstracción de una computación. La idea básica es que el estado de una computación puede ser representada como un grafo, pasos siguientes en dicha computación pueden ser representada a partir de la reescritura de aquel grafo. Tales reglas consistente en un grafo original y un grafo de reemplazo, en donde se busca un subgrafo que coincida completamente con una parte o la totalidad del grafo original para luego ser sustituido por el grafo de reemplazo.

Formalmente, una ${\displaystyle }$reescritura de grafos normal${\displaystyle }$mente consta de un conjunto de regl${\displaystyle }$as de la forma ${\displaystyle }$

, con L {${\displaystyle }$} siendo llamado patrón del grafo (o lado izquierdo de la regla) y R {${\displaystyle }$} siendo llamado grafo de sustitución  (o lado derecho de la regla).https://wikimedia.org/api/rest_v1/media/math/render/svg/0d1fa4bff26e858093155ef0e0f06377a055aa96${\displaystyle }$${\displaystyle }$ Un graph reescribe la regla está aplicada al anfitrión graph por buscar una ocurrencia del patrón graph (el patrón que empareja, por ello solucionando el subgraph problema de isomorfismo) y por reemplazar la ocurrencia encontrada por un caso de la sustitución graph. Reescribe las reglas pueden ser más allá reguladas en el caso de labeled graphs, como en cuerda-regulado graph gramáticas.