Théorie des graphes - Revêtements

Un graphe de couverture est un sous-graphe qui contient soit tous les sommets, soit toutes les arêtes correspondant à un autre graphe. Un sous-graphe contenant tous les sommets est appeléline/edge covering. Un sous-graphe qui contient toutes les arêtes est appelé unvertex covering.

Couverture de ligne

Soit G = (V, E) un graphe. Un sous-ensemble C (E) est appelé un recouvrement de ligne de G si chaque sommet de G est incident avec au moins un bord en C, c'est-à-dire,

deg (V) ≥ 1 ∀ V ∈ G

car chaque sommet est relié à un autre sommet par une arête. Par conséquent, il a un degré minimum de 1.

Example

Jetez un œil au graphique suivant -

Ses sous-graphiques ayant une couverture de ligne sont les suivants:

C ₁ = {{a, b}, {c, d}}

C ₂ = {{a, d}, {b, c}}

C ₃ = {{a, b}, {b, c}, {b, d}}

C ₄ = {{a, b}, {b, c}, {c, d}}

Le recouvrement de ligne de 'G' n'existe pas si et seulement si 'G' a un sommet isolé. Le recouvrement de ligne d'un graphe avec 'n' sommets a au moins [n / 2] arêtes.

Couverture de ligne minimale

Une ligne couvrant C d'un graphe G est dite minimale if no edge can be deleted from C.

Example

Dans le graphique ci-dessus, les sous-graphiques ayant une couverture de ligne sont les suivants -

C ₁ = {{a, b}, {c, d}}

C ₂ = {{a, d}, {b, c}}

C ₃ = {{a, b}, {b, c}, {b, d}}

C ₄ = {{a, b}, {b, c}, {c, d}}

Ici, C ₁ , C ₂ , C ₃ sont des couvertures de lignes minimales, tandis que C ₄ ne l'est pas parce que nous pouvons supprimer {b, c}.

Couverture minimale de la ligne

Il est également connu sous le nom de Smallest Minimal Line Covering. Une couverture de ligne minimale avec un nombre minimum d'arêtes est appelée une couverture de ligne minimale de «G». Le nombre d'arêtes dans une ligne minimale couvrant en 'G' est appelé leline covering numberde 'G' (α ₁ ).

Example

Dans l'exemple ci-dessus, C ₁ et C ₂ sont la couverture de ligne minimale de G et α ₁ = 2.

Chaque couverture de ligne contient une couverture de ligne minimale.
Chaque recouvrement de ligne ne contient pas de recouvrement de ligne minimum (C ₃ ne contient pas de recouvrement de ligne minimum.
Aucune couverture de ligne minimale ne contient un cycle.
Si une ligne couvrant 'C' ne contient aucun chemin de longueur 3 ou plus, alors 'C' est une ligne minimale car toutes les composantes de 'C' sont un graphe en étoile et à partir d'un graphe en étoile, aucune arête ne peut être supprimée.

Couverture de sommet

Soit 'G' = (V, E) un graphe. Un sous-ensemble K de V est appelé une couverture de vertex de «G», si chaque arête de «G» est incidente ou couverte par un sommet de «K».

Example

Jetez un œil au graphique suivant -

Les sous-graphiques qui peuvent être dérivés du graphique ci-dessus sont les suivants -

K ₁ = {b, c}

K ₂ = {a, b, c}

K ₃ = {b, c, d}

K ₄ = {a, d}

Ici, K ₁ , K ₂ et K ₃ ont une couverture de sommet, alors que K ₄ n'a pas de couverture de sommet car elle ne couvre pas l'arête {bc}.

Couverture minimale des sommets

Un sommet 'K' du graphe 'G' est dit être une couverture de sommet minimale si aucun sommet ne peut être supprimé de 'K'.

Example

Dans le graphique ci-dessus, les sous-graphiques ayant une couverture de vertex sont les suivants -

K ₁ = {b, c}

K ₂ = {a, b, c}

K ₃ = {b, c, d}

Ici, K ₁ et K ₂ sont des revêtements de sommets minimaux, tandis que dans K ₃ , le sommet 'd' peut être supprimé.

Couverture minimale des sommets

Il est également connu comme le plus petit recouvrement minimal de vertex. Une couverture minimale de sommets du graphe «G» avec un nombre minimum de sommets est appelée la couverture minimale de sommets.

Le nombre de sommets dans une couverture minimale de sommets de «G» est appelé le nombre de sommets couvrant de G (α ₂ ).

Example

Dans le graphique suivant, les sous-graphes ayant une couverture de sommet sont les suivants -

K ₁ = {b, c}

K ₂ = {a, b, c}

K ₃ = {b, c, d}