Théorie des graphes - Ensembles indépendants

Les ensembles indépendants sont représentés dans des ensembles, dans lesquels

  • il ne devrait pas y avoir any edges adjacent to each other. Il ne devrait y avoir aucun sommet commun entre deux arêtes.

  • il ne devrait pas y avoir any vertices adjacent to each other. Il ne doit pas y avoir d'arête commune entre deux sommets.

Jeu de lignes indépendant

Soit 'G' = (V, E) un graphe. Un sous-ensemble L de E est appelé un ensemble de lignes indépendant de «G» si deux arêtes de L ne sont pas adjacentes. Un tel ensemble est appelé un ensemble de lignes indépendant.

Example

Considérons les sous-ensembles suivants -

L1 = {a,b}
L2 = {a,b} {c,e}
L3 = {a,d} {b,c}

Dans cet exemple, les sous-ensembles L2 et L3 ne sont clairement pas les arêtes adjacentes dans le graphique donné. Ce sont des ensembles de lignes indépendants. Cependant L1 n'est pas un ensemble de lignes indépendant, car pour créer un ensemble de lignes indépendant, il doit y avoir au moins deux arêtes.

Jeu de lignes indépendant maximal

Un ensemble de lignes indépendant est considéré comme l'ensemble de lignes indépendantes maximal d'un graphe «G» si aucune autre arête de «G» ne peut être ajoutée à «L».

Example

Considérons les sous-ensembles suivants -

L1 = {a, b}
L2 = {{b, e}, {c, f}}
L3 = {{a, e}, {b, c}, {d, f}}
L4 = {{a, b}, {c, f}}

L 2 et L 3 sont des ensembles de lignes indépendants maximaux / correspondance maximale. Comme pour ces deux sous-ensembles seulement, il n'y a aucune chance d'ajouter un autre bord qui ne soit pas adjacent. Par conséquent, ces deux sous-ensembles sont considérés comme les ensembles de lignes indépendants maximaux.

Ensemble de lignes indépendantes maximum

Un ensemble de lignes indépendantes maximum de «G» avec un nombre maximum d'arêtes est appelé ensemble de lignes indépendantes maximum de «G».

Number of edges in a maximum independent line set of G (β1)
   = Line independent number of G
   = Matching number of G

Example

Considérons les sous-ensembles suivants -

L1 = {a, b}
L2 = {{b, e}, {c, f}}
L3 = {{a, e}, {b, c}, {d, f}}
L4 = {{a, b}, {c, f}}

L 3 est l'ensemble de lignes indépendantes maximum de G avec des arêtes maximales qui ne sont pas les arêtes adjacentes dans le graphe et est noté β1 = 3.

Note - Pour tout graphe G sans sommet isolé,

α1 + β1 = nombre de sommets dans un graphe = | V |

Example

Ligne couvrant le nombre de K n / C n / w n ,

$$ \ alpha 1 = \ lceil \ frac {n} {2} \ rceil \ begin {cases} \ frac {n} {2} \: if \: n \: is \: even \\\ frac {n + 1} {2} \: if \: n \: is \: odd \ end {cases} $$

Numéro indépendant de la ligne (Matching number) = β 1 = [n / 2] α 1 + β 1 = n.

Ensemble de sommets indépendants

Soit 'G' = (V, E) un graphe. Un sous-ensemble de «V» est appelé un ensemble indépendant de «G» si deux sommets de «S» ne sont pas adjacents.

Example

Considérez les sous-ensembles suivants des graphiques ci-dessus -

S1 = {e}

S2 = {e, f}
S3 = {a, g, c}
S4 = {e, d}

Clairement S 1 n'est pas un ensemble de sommets indépendant, car pour obtenir un ensemble de sommets indépendant, il doit y avoir au moins deux sommets dans le à partir d'un graphe. Mais ici ce n'est pas le cas. Les sous - ensembles S 2 , S 3 et S 4 sont des ensembles de sommets indépendants car il n'y a pas de sommet qui est adjacent à un sommet quelconque des sous - ensembles.

Ensemble maximal de sommets indépendants

Soit «G» un graphe, alors un ensemble de sommets indépendant de «G» est dit maximal si aucun autre sommet de «G» ne peut être ajouté à «S».

Example

Considérez les sous-ensembles suivants des graphiques ci-dessus.

S1 = {e}
S2 = {e, f}
S3 = {a, g, c}
S4 = {e, d}

S 2 et S 3 sont des ensembles de sommets indépendants maximaux de «G». En S 1 et S 4 , nous pouvons ajouter d'autres sommets; mais en S 2 et S 3 , nous ne pouvons ajouter aucun autre sommet.

Ensemble maximal de sommets indépendants

Un ensemble de sommets indépendant maximal de «G» avec un nombre maximal de sommets est appelé comme le jeu de sommets indépendant maximal.

Example

Considérez les sous-ensembles suivants du graphique ci-dessus -

S1 = {e}
S2 = {e, f}
S3 = {a, g, c}
S4 = {e, d}

Seul S 3 est l'ensemble maximal de sommets indépendants, car il couvre le plus grand nombre de sommets. Le nombre de sommets dans un ensemble maximal de sommets indépendants de «G» est appelé le nombre de sommets indépendants de G (β 2 ).

Example

Pour le graphe complet K n ,

Nombre de couverture de sommet = α 2 = n − 1

Nombre indépendant du sommet = β 2 = 1

Vous avez α 2 + β 2 = n

Dans un graphe complet, chaque sommet est adjacent à ses (n - 1) sommets restants. Par conséquent, un ensemble indépendant maximal de K n ne contient qu'un seul sommet.

Par conséquent, β 2 = 1

et α 2 = | v | - β 2 = n-1

Note - Pour tout graphe 'G' = (V, E)

  • α 2 + β 2 = | v |
  • Si 'S' est un ensemble de sommets indépendant de 'G', alors (V - S) est une couverture de sommets de G.