Teoria dei grafi - Abbinamenti
Un grafico corrispondente è un sottografo di un grafico in cui non ci sono bordi adiacenti l'uno all'altro. Semplicemente, non dovrebbe esserci alcun vertice comune tra due spigoli.
Corrispondenza
Sia 'G' = (V, E) un grafico. Un sottografo è chiamato corrispondenza M (G),if each vertex of G is incident with at most one edge in M, cioè
gradi (V) ≤ 1 ∀ V ∈ G
il che significa che nel grafo di corrispondenza M (G), i vertici dovrebbero avere un grado di 1 o 0, dove i bordi dovrebbero essere incidenti dal grafo G.
Notation - M (G)
Example
In un abbinamento,
se deg (V) = 1, si dice che (V) corrisponde
se deg (V) = 0, allora (V) non corrisponde.
In una corrispondenza, non ci sono due bordi adiacenti. È perché se due bordi qualsiasi sono adiacenti, il grado del vertice che si unisce a quei due bordi avrà un grado di 2 che viola la regola di corrispondenza.
Corrispondenza massima
Una M corrispondente del grafico 'G' è detta massima if no other edges of ‘G’ can be added to M.
Example
M1, M2, M3 dal grafico sopra sono la corrispondenza massima di G.
Abbinamento massimo
È anche noto come corrispondenza massima massima. La corrispondenza massima è definita come la corrispondenza massima con il numero massimo di bordi.
Il numero di archi nella corrispondenza massima di 'G' è chiamato suo matching number.
Example
Per un grafico dato nell'esempio sopra, M1 e M2 sono la corrispondenza massima di "G" e il suo numero di corrispondenza è 2. Quindi, utilizzando il grafico G, possiamo formare solo i sottografi con solo 2 bordi al massimo. Quindi abbiamo il numero corrispondente come due.
Abbinamento perfetto
Un abbinamento (M) del grafo (G) si dice che sia un abbinamento perfetto, se ogni vertice del grafo g (G) è incidente esattamente a un lato della corrispondenza (M), cioè,
deg (V) = 1 ∀ V
Il grado di ogni vertice nel sottografo dovrebbe avere un grado di 1.
Example
Nei grafici seguenti, M1 e M2 sono esempi di corrispondenza perfetta di G.
Note - Ogni corrispondenza perfetta del grafico è anche una corrispondenza massima del grafico, perché non c'è possibilità di aggiungere un altro bordo in un grafico di corrispondenza perfetta.
Non è necessario che una corrispondenza massima del grafico sia perfetta. Se un grafo 'G' ha una corrispondenza perfetta, allora il numero di vertici | V (G) | è anche. Se è dispari, allora l'ultimo vertice si accoppia con l'altro vertice, e alla fine rimane un unico vertice che non può essere accoppiato con nessun altro vertice per il quale il grado è zero. Viola chiaramente il principio di corrispondenza perfetta.
Example
Note- Il contrario della dichiarazione di cui sopra non deve essere vero. Se G ha un numero pari di vertici, allora M1 non deve essere perfetto.
Example
È una corrispondenza, ma non è una corrispondenza perfetta, anche se ha un numero pari di vertici.