Contracción de borde

Dejar${\displaystyle G=(V,E)}$ser un grafo ( o grafo dirigido ) que contiene una arista${\displaystyle e=(u,v)}$con${\displaystyle u\neq v}$. Dejar${\displaystyle f}$sea ​​una función que mapea cada vértice en${\displaystyle V\setminus \{u,v\}}$a sí mismo, y de lo contrario, lo asigna a un nuevo vértice.${\displaystyle w}$. La contracción de${\displaystyle e}$da como resultado un nuevo gráfico${\displaystyle G'=(V',E')}$, dónde${\displaystyle V'=(V\setminus \{u,v\})\cup \{w\}}$,${\displaystyle E'=E\setminus \{e\}}$y por cada${\displaystyle x\in V}$,${\displaystyle x'=f(x)\in V'}$es incidente a un borde${\displaystyle e'\in E'}$si y solo si , la arista correspondiente,${\displaystyle e\in E}$es incidente a${\displaystyle x}$en${\displaystyle G}$.

La identificación de vértices (a veces llamada contracción de vértices ) elimina la restricción de que la contracción deba ocurrir sobre vértices que comparten una arista incidente. (Por lo tanto, la contracción de aristas es un caso especial de identificación de vértices). La operación puede ocurrir en cualquier par (o subconjunto) de vértices en el grafo. A veces se eliminan las aristas entre dos vértices que se contraen . Si${\displaystyle v}$y${\displaystyle v'}$son vértices de componentes distintos de${\displaystyle G}$Entonces podemos crear un nuevo gráfico.${\displaystyle G'}$mediante la identificación${\displaystyle v}$y${\displaystyle v'}$en${\displaystyle G}$como un nuevo vértice${\displaystyle {\textbf {v}}}$en${\displaystyle G'}$. ^{[ 4 ]} De manera más general, dada una partición del conjunto de vértices, se pueden identificar vértices en la partición; el grafo resultante se conoce como grafo cociente .

La división de vértices , que es lo mismo que la escisión de vértices, consiste en dividir un vértice en dos, de modo que estos dos nuevos vértices sean adyacentes a los vértices adyacentes al vértice original. Esta es la operación inversa a la identificación de vértices, aunque, en general, para la identificación de vértices, los vértices adyacentes de los dos vértices identificados no son el mismo conjunto.

La contracción de la ruta se produce cuando un conjunto de aristas se contraen para formar una sola arista entre los extremos de la ruta. Las aristas incidentes a los vértices a lo largo de la ruta se eliminan o se conectan arbitrariamente (o sistemáticamente) a uno de los extremos.

Consideremos dos grafos disjuntos.${\displaystyle G_{1}}$y${\displaystyle G_{2}}$, dónde${\displaystyle G_{1}}$contiene vértices${\displaystyle u_{1}}$y${\displaystyle v_{1}}$y${\displaystyle G_{2}}$contiene vértices${\displaystyle u_{2}}$y${\displaystyle v_{2}}$Supongamos que podemos obtener el gráfico.${\displaystyle G}$identificando los vértices${\displaystyle u_{1}}$de${\displaystyle G_{1}}$y${\displaystyle u_{2}}$de${\displaystyle G_{2}}$como vértice${\displaystyle u}$de${\displaystyle G}$y la identificación de los vértices${\displaystyle v_{1}}$de${\displaystyle G_{1}}$y${\displaystyle v_{2}}$de${\displaystyle G_{2}}$como vértice${\displaystyle v}$de${\displaystyle G}$. En un torbellino${\displaystyle G'}$de${\displaystyle G}$con respecto al conjunto de vértices${\displaystyle \{u,v\}}$, identificamos, en cambio,${\displaystyle u_{1}}$con${\displaystyle v_{2}}$y${\displaystyle v_{1}}$con${\displaystyle u_{2}}$. ^{[ 5 ]}

Dado un conjunto finito de aristas, el orden en que se realizan las contracciones en un grafo no cambia el resultado (salvo isomorfismo). El resultado se reduce a demostrar que${\displaystyle G/e/(f/e)}$es isomorfo a${\displaystyle G/f/(e/f)}$para dos bordes${\displaystyle e,f}$de${\displaystyle G}$. ^{[ 6 ]}