Teoria dei grafi - Rivestimenti

Un grafo coprente è un sottografo che contiene tutti i vertici o tutti i bordi corrispondenti a qualche altro grafo. Un sottografo che contiene tutti i vertici è chiamato aline/edge covering. Un sottografo che contiene tutti i bordi è chiamato avertex covering.

Linea di copertura

Sia G = (V, E) un grafico. Un sottoinsieme C (E) è chiamato copertura di linea di G se ogni vertice di G è incidente con almeno un arco in C, cioè

gradi (V) ≥ 1 ∀ V ∈ G

perché ogni vertice è connesso con un altro vertice da un bordo. Quindi ha un grado minimo di 1.

Example

Dai un'occhiata al grafico seguente:

I suoi sottografi con copertura della linea sono i seguenti:

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 copertura di linea di 'G' non esiste se e solo se 'G' ha un vertice isolato. La copertura di linea di un grafo con vertici 'n' ha almeno [n / 2] bordi.

Copertura minimale

Si dice che una linea che copre C di un grafo G sia minima if no edge can be deleted from C.

Example

Nel grafico sopra, i sottografi che coprono la linea sono i seguenti:

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}}

Qui, C 1 , C 2 , C 3 sono coperture di linea minime, mentre C 4 non lo è perché possiamo eliminare {b, c}.

Copertura minima della linea

È anche conosciuto come Smallest Minimal Line Covering. Una copertura di linea minima con un numero minimo di bordi è chiamata copertura di linea minima di "G". Il numero di bordi in una linea minima che copre in 'G' è chiamatoline covering numberdi 'G' (α 1 ).

Example

Nell'esempio sopra, C 1 e C 2 sono la copertura di linea minima di G e α 1 = 2.

  • Ogni rivestimento di linea contiene un rivestimento di linea minimale.

  • Ogni copertura di linea non contiene una copertura di linea minima (C 3 non contiene alcuna copertura di linea minima.

  • Nessuna copertura di linea minima contiene un ciclo.

  • Se una linea che copre "C" non contiene percorsi di lunghezza 3 o più, allora "C" è una linea minima che copre perché tutti i componenti di "C" sono un grafico a stella e da un grafico a stella, nessun bordo può essere eliminato.

Copertura del vertice

Sia 'G' = (V, E) un grafico. Un sottoinsieme K di V è chiamato copertura di vertici di "G", se ogni spigolo di "G" è incidente o coperto da un vertice in "K".

Example

Dai un'occhiata al grafico seguente:

I sottografi che possono essere derivati ​​dal grafico sopra sono i seguenti:

K 1 = {b, c}

K 2 = {a, b, c}

K 3 = {b, c, d}

K 4 = {a, d}

Qui, K 1 , K 2 e K 3 hanno copertura dei vertici, mentre K 4 non ha alcuna copertura dei vertici in quanto non copre il bordo {bc}.

Copertura minima dei vertici

Un vertice "K" del grafo "G" si dice che sia copertura di vertici minima se nessun vertice può essere cancellato da "K".

Example

Nel grafico sopra, i sottografi con copertura dei vertici sono i seguenti:

K 1 = {b, c}

K 2 = {a, b, c}

K 3 = {b, c, d}

Qui, K 1 e K 2 sono coperture di vertici minimi, mentre in K 3 , il vertice "d" può essere cancellato.

Copertura del vertice minimo

È anche noto come la più piccola copertura del vertice minimo. Una copertura minima dei vertici del grafo 'G' con un numero minimo di vertici è chiamata copertura minima dei vertici.

Il numero di vertici in una copertura di vertici minima di 'G' è chiamata numero di copertura di vertici di G (α 2 ).

Example

Nel grafico seguente, i sottografi con copertura dei vertici sono i seguenti:

K 1 = {b, c}

K 2 = {a, b, c}

K 3 = {b, c, d}

Qui, K 1 è una copertura di vertici minima di G, poiché ha solo due vertici. α 2 = 2.