Teoría de grafos - Coberturas
Un gráfico de cobertura es un subgráfico que contiene todos los vértices o todos los bordes correspondientes a algún otro gráfico. Un subgrafo que contiene todos los vértices se llamaline/edge covering. Un subgrafo que contiene todos los bordes se llamavertex covering.
Recubrimiento de línea
Sea G = (V, E) una gráfica. Un subconjunto C (E) se llama una línea que cubre G si cada vértice de G es incidente con al menos un borde en C, es decir,
grados (V) ≥ 1 ∀ V ∈ G
porque cada vértice está conectado con otro vértice por una arista. Por tanto, tiene un grado mínimo de 1.
Example
Eche un vistazo al siguiente gráfico:
Sus subgrafos que tienen cobertura de línea son los siguientes:
C 1 = {{a, b}, {c, d}}
C 2 = {{a, d}, {b, c}}
C 3 = {{a, b}, {b, c}, {b, d}}
C 4 = {{a, b}, {b, c}, {c, d}}
La cobertura de línea de 'G' no existe si y solo si 'G' tiene un vértice aislado. La línea que cubre un gráfico con 'n' vértices tiene al menos [n / 2] aristas.
Recubrimiento de línea mínimo
Se dice que una línea que cubre C de un gráfico G es mínima if no edge can be deleted from C.
Example
En el gráfico anterior, los subgrafos que tienen cobertura de línea son los siguientes:
C 1 = {{a, b}, {c, d}}
C 2 = {{a, d}, {b, c}}
C 3 = {{a, b}, {b, c}, {b, d}}
C 4 = {{a, b}, {b, c}, {c, d}}
Aquí, C 1 , C 2 , C 3 son cubiertas de línea mínimas, mientras que C 4 no lo es porque podemos eliminar {b, c}.
Cobertura mínima de línea
También se conoce como Smallest Minimal Line Covering. Una cobertura de línea mínima con un número mínimo de bordes se denomina cobertura de línea mínima de 'G'. El número de bordes en una línea mínima que cubre en 'G' se llamaline covering numberde 'G' (α 1 ).
Example
En el ejemplo anterior, C 1 y C 2 son la línea mínima que cubre G y α 1 = 2.
Cada revestimiento de línea contiene un revestimiento de línea mínimo.
Cada cobertura de línea no contiene una cobertura de línea mínima (C 3 no contiene ninguna cobertura de línea mínima.
Ningún recubrimiento de línea mínimo contiene un ciclo.
Si una línea que cubre 'C' no contiene trayectos de longitud 3 o más, entonces 'C' es una línea mínima que cubre porque todos los componentes de 'C' son gráficos en estrella y de un gráfico en estrella, no se puede eliminar ningún borde.
Recubrimiento de vértices
Sea 'G' = (V, E) una gráfica. Un subconjunto K de V se denomina recubrimiento de vértice de 'G', si cada borde de 'G' incide o está cubierto por un vértice de 'K'.
Example
Eche un vistazo al siguiente gráfico:
Los subgrafos que se pueden derivar del gráfico anterior son los siguientes:
K 1 = {b, c}
K 2 = {a, b, c}
K 3 = {b, c, d}
K 4 = {a, d}
Aquí, K 1 , K 2 y K 3 tienen cobertura de vértice, mientras que K 4 no tiene ninguna cobertura de vértice ya que no cubre el borde {bc}.
Recubrimiento de vértice mínimo
Se dice que un vértice 'K' del gráfico 'G' es una cobertura mínima de vértices si no se puede eliminar ningún vértice de 'K'.
Example
En el gráfico anterior, los subgrafos que tienen cobertura de vértice son los siguientes:
K 1 = {b, c}
K 2 = {a, b, c}
K 3 = {b, c, d}
Aquí, K 1 y K 2 son cubiertas de vértices mínimas, mientras que en K 3 , el vértice 'd' se puede eliminar.
Recubrimiento mínimo de vértice
También se conoce como la cobertura de vértice mínima más pequeña. Una cobertura de vértice mínima del gráfico 'G' con un número mínimo de vértices se denomina cobertura de vértice mínima.
El número de vértices en una cobertura de vértice mínima de 'G' se denomina número de cobertura de vértice de G (α 2 ).
Example
En el siguiente gráfico, los subgráficos que tienen cobertura de vértice son los siguientes:
K 1 = {b, c}
K 2 = {a, b, c}
K 3 = {b, c, d}
Aquí, K 1 es una cobertura de vértice mínima de G, ya que solo tiene dos vértices. α 2 = 2.