Théorie des graphes - Appariements

Un graphe correspondant est un sous-graphe d'un graphe où il n'y a pas d'arêtes adjacentes les unes aux autres. Simplement, il ne devrait y avoir aucun sommet commun entre deux arêtes.

Correspondant à

Soit 'G' = (V, E) un graphe. Un sous-graphe est appelé un M (G) correspondant,if each vertex of G is incident with at most one edge in M, c'est à dire,

deg (V) ≤ 1 ∀ V ∈ G

ce qui signifie que dans le graphe correspondant M (G), les sommets devraient avoir un degré de 1 ou 0, où les arêtes devraient être incidentes du graphe G.

Notation - M (G)

Example

Dans un match,

si deg (V) = 1, alors (V) est dit correspondant

si deg (V) = 0, alors (V) ne correspond pas.

Dans une correspondance, il n'y a pas deux arêtes adjacentes. C'est parce que si deux arêtes quelconques sont adjacentes, alors le degré du sommet qui joint ces deux arêtes aura un degré de 2, ce qui viole la règle de correspondance.

Correspondance maximale

Une correspondance M du graphe 'G' est dite maximale if no other edges of ‘G’ can be added to M.

Example

M1, M2, M3 du graphique ci-dessus sont l'appariement maximal de G.

Correspondance maximale

Il est également connu sous le nom de correspondance maximale la plus grande. La correspondance maximale est définie comme la correspondance maximale avec le nombre maximal d'arêtes.

Le nombre d'arêtes dans la correspondance maximale de 'G' est appelé son matching number.

Example

Pour un graphique donné dans l'exemple ci-dessus, M1 et M2 sont la correspondance maximale de «G» et son numéro de correspondance est 2. Par conséquent, en utilisant le graphique G, nous ne pouvons former que les sous-graphiques avec seulement 2 arêtes maximum. Par conséquent, nous avons le nombre correspondant à deux.

Correspondance parfaite

Un appariement (M) du graphe (G) est dit être un appariement parfait, si chaque sommet du graphe g (G) est incident à exactement un bord de l'appariement (M), c'est-à-dire,

deg (V) = 1 ∀ V

Le degré de chaque sommet du sous-graphe doit avoir un degré de 1.

Example

Dans les graphiques suivants, M1 et M2 sont des exemples d'appariement parfait de G.

Note - Chaque correspondance parfaite de graphique est également une correspondance maximale de graphique, car il n'y a aucune chance d'ajouter une autre arête dans un graphique de correspondance parfaite.

Une correspondance maximale du graphique n'a pas besoin d'être parfaite. Si un graphe 'G' a une correspondance parfaite, alors le nombre de sommets | V (G) | est même. S'il est impair, alors le dernier sommet s'apparie avec l'autre sommet, et finalement il reste un seul sommet qui ne peut être apparié avec aucun autre sommet pour lequel le degré est nul. Cela viole clairement le principe de correspondance parfaite.

Example