1. Conjuntos Independientes –
- Un conjunto de vértices I se llama conjunto independiente si no hay dos vértices en el conjunto I que sean adyacentes entre sí o, en otras palabras, el conjunto de vértices no adyacentes se denomina conjunto independiente.
- También se le llama conjunto estable.
- El parámetro α 0 (G) = max { |I|: I es un conjunto independiente en G } se llama número de independencia de G, es decir, el número máximo de vértices no adyacentes.
- Cualquier conjunto independiente I con |I| = α 0 (G) se llama conjunto máximo independiente.
Para el gráfico G dado anteriormente, los conjuntos independientes son:
I1 = {1}, I2 = {2}, I3 = {3}, I4 = {4}
I5 = {1, 3} and I6 = {2, 4}
Por lo tanto, número máximo de vértices no adyacentes, es decir, número de independencia α 0 (G) = 2.
2. Recubrimiento de vértices –
- Un conjunto de vértices K que puede cubrir todas las aristas del gráfico G se denomina cubierta de vértice de G, es decir, si cada arista de G está cubierta por un vértice en el conjunto K.
- El parámetro β 0 (G) = min { |K|: K es una cubierta de vértice de G } se denomina número de cubierta de vértice de G, es decir, el número mínimo de vértices que pueden cubrir todas las aristas.
- Cualquier vértice cubre K con |K| = β 0 (G) se llama cobertura mínima de vértices.
Para el gráfico G dado anteriormente, la cobertura del vértice es:
V1 = {1, 3}, V2 = {2, 4},
V3 = {1, 2, 3}, V4 = {1, 2, 3, 4}, etc.
Por lo tanto, el número mínimo de vértices que pueden cubrir todos los bordes, es decir, el número de vértice que cubre β 0 (G) = 2.
Notas –
- I es un conjunto independiente en G iff V(G) – I es la cubierta de vértice de G.
- Para cualquier gráfico G, α 0 (G) + β 0 (G) = n, donde n es el número de vértices en G.
Recubrimiento de bordes –
- Un conjunto de aristas F que puede cubrir todos los vértices del grafo G se denomina cubierta de aristas de G, es decir, si cada vértice de G incide con una arista de F.
- El parámetro β 1 (G) = min { |F|: F es una cobertura de borde de G } se denomina número de cobertura de borde de G, es decir, la suma del número mínimo de bordes que pueden cubrir todos los vértices y el número de vértices aislados (si existen ).
- Cualquier borde cubre F con |F| = β 1 (G) se llama cobertura de borde mínima.
Para el gráfico G anterior, la cobertura del borde es:
E1 = {a, b, c, d},
E2 = {a, d} and E3 = {b, c}.
Por lo tanto, el número mínimo de aristas que pueden cubrir todos los vértices, es decir, Número de cobertura de aristas β 1 (G) = 2.
Nota – Para cualquier gráfico G, α 1 (G) + β 1 (G) = n, donde n es el número de vértices en G.
3. Coincidencia –
- El conjunto de aristas no adyacentes se denomina coincidencia , es decir, conjunto independiente de aristas en G tal que no hay dos aristas adyacentes en el conjunto.
- El parámetro α 1 (G) = max { |M|: M es una coincidencia en G } se denomina número de coincidencia de G, es decir, el número máximo de aristas no adyacentes.
- Cualquier M coincidente con |M| = α 1 (G) se llama coincidencia máxima.
Para el gráfico G dado anteriormente, las coincidencias son:
M1 = {a}, M2 = {b}, M3 = {c}, M4 = {d}
M5 = {a, d} and M6 = {b, c}
Por lo tanto, el número máximo de bordes no adyacentes, es decir, el número coincidente α 1 (G) = 2.
Emparejamiento completo: Un emparejamiento de un grafo G es completo si contiene todos los vértices de G. A veces, esto también se denomina coincidencia perfecta.
TEOREMA DEL MATRIMONIO DE HALL: El grafo bipartito G =(V, E) con bipartición (V1, V2) tiene una coincidencia completa de V1 a V2 si y solo si |N (A)| > |A| para todos los subconjuntos A de V1. (Esta es una condición necesaria y suficiente para la coincidencia completa).
