Teoria de grafos - coberturas
Um gráfico de cobertura é um subgrafo que contém todos os vértices ou todas as arestas correspondentes a algum outro gráfico. Um subgrafo que contém todos os vértices é chamado deline/edge covering. Um subgrafo que contém todas as arestas é chamado devertex covering.
Cobertura de Linha
Seja G = (V, E) um gráfico. Um subconjunto C (E) é chamado de cobertura de linha de G se cada vértice de G incide com pelo menos uma aresta em C, ou seja,
deg (V) ≥ 1 ∀ V ∈ G
porque cada vértice está conectado a outro vértice por uma aresta. Portanto, tem um grau mínimo de 1.
Example
Dê uma olhada no gráfico a seguir -
Seus subgráficos com cobertura de linha são os seguintes -
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}}
A linha de cobertura de 'G' não existe se e somente se 'G' tem um vértice isolado. A cobertura da linha de um gráfico com 'n' vértices tem pelo menos [n / 2] arestas.
Cobertura mínima de linha
Uma linha cobrindo C de um gráfico G é considerada mínima if no edge can be deleted from C.
Example
No gráfico acima, os subgráficos com cobertura de linha são os seguintes -
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}}
Aqui, C 1 , C 2 , C 3 são coberturas de linha mínimas, enquanto C 4 não é, porque podemos excluir {b, c}.
Cobertura mínima de linha
Também é conhecido como Smallest Minimal Line Covering. Uma cobertura de linha mínima com número mínimo de bordas é chamada de cobertura de linha mínima de 'G'. O número de arestas em uma linha mínima cobrindo em 'G' é chamado deline covering numberde 'G' (α 1 ).
Example
No exemplo acima, C 1 e C 2 são a cobertura de linha mínima de G e α 1 = 2.
Cada cobertura de linha contém uma cobertura de linha mínima.
Cada cobertura de linha não contém uma cobertura de linha mínima (C 3 não contém nenhuma cobertura de linha mínima.
Nenhuma cobertura de linha mínima contém um ciclo.
Se uma linha cobrindo 'C' não contém caminhos de comprimento 3 ou mais, então 'C' é uma linha mínima cobrindo porque todos os componentes de 'C' são gráfico de estrela e de um gráfico de estrela, nenhuma aresta pode ser excluída.
Cobertura de vértices
Seja 'G' = (V, E) um gráfico. Um subconjunto K de V é chamado de cobertura de vértice de 'G', se toda aresta de 'G' incide ou é coberta por um vértice em 'K'.
Example
Dê uma olhada no gráfico a seguir -
Os subgráficos que podem ser derivados do gráfico acima são os seguintes -
K 1 = {b, c}
K 2 = {a, b, c}
K 3 = {b, c, d}
K 4 = {a, d}
Aqui, K 1 , K 2 e K 3 têm cobertura de vértices, enquanto K 4 não tem cobertura de vértices, pois não cobre a aresta {bc}.
Cobertura mínima de vértices
Um vértice 'K' do gráfico 'G' é considerado um vértice mínimo cobrindo se nenhum vértice puder ser excluído de 'K'.
Example
No gráfico acima, os subgráficos com cobertura de vértices são os seguintes -
K 1 = {b, c}
K 2 = {a, b, c}
K 3 = {b, c, d}
Aqui, K 1 e K 2 são coberturas de vértices mínimas, enquanto em K 3 , o vértice 'd' pode ser excluído.
Cobertura mínima do vértice
É também conhecido como a menor cobertura mínima do vértice. Uma cobertura mínima de vértices do gráfico 'G' com um número mínimo de vértices é chamada de cobertura mínima de vértices.
O número de vértices em um vértice mínimo cobrindo 'G' é chamado de vértice cobrindo o número de G (α 2 ).
Example
No gráfico a seguir, os subgráficos com cobertura de vértices são os seguintes -
K 1 = {b, c}
K 2 = {a, b, c}
K 3 = {b, c, d}
Aqui, K 1 é uma cobertura de vértice mínima de G, pois tem apenas dois vértices. α 2 = 2.