Teoría de grafos - Coincidencias
Un gráfico coincidente es un subgráfico de un gráfico donde no hay bordes adyacentes entre sí. Simplemente, no debería haber ningún vértice común entre dos aristas.
Pareo
Sea 'G' = (V, E) una gráfica. Un subgrafo se llama coincidencia M (G),if each vertex of G is incident with at most one edge in M, es decir,
grados (V) ≤ 1 ∀ V ∈ G
lo que significa que en el gráfico coincidente M (G), los vértices deben tener un grado de 1 o 0, donde los bordes deben incidir en el gráfico G.
Notation - M (G)
Example
En un emparejamiento,
si deg (V) = 1, entonces se dice que (V) coincide
si deg (V) = 0, entonces (V) no coincide.
En una coincidencia, no hay dos bordes adyacentes. Esto se debe a que si dos bordes son adyacentes, entonces el grado del vértice que une esos dos bordes tendrá un grado de 2, lo que viola la regla de coincidencia.
Coincidencia máxima
Se dice que una M coincidente de la gráfica 'G' es máxima if no other edges of ‘G’ can be added to M.
Example
M1, M2, M3 del gráfico anterior son la coincidencia máxima de G.
Coincidencia máxima
También se conoce como mayor coincidencia máxima. La coincidencia máxima se define como la coincidencia máxima con el número máximo de bordes.
El número de aristas en la coincidencia máxima de 'G' se llama su matching number.
Example
Para una gráfica dada en el ejemplo anterior, M1 y M2 son la coincidencia máxima de 'G' y su número coincidente es 2. Por lo tanto, al usar la gráfica G, podemos formar solo los subgrafos con solo 2 bordes como máximo. Por tanto, tenemos el número correspondiente como dos.
Combinación perfecta
Se dice que una coincidencia (M) del gráfico (G) es una coincidencia perfecta, si cada vértice del gráfico g (G) es incidente exactamente en un borde de la coincidencia (M), es decir,
grados (V) = 1 ∀ V
El grado de todos y cada uno de los vértices del subgráfico debe tener un grado de 1.
Example
En los siguientes gráficos, M1 y M2 son ejemplos de coincidencia perfecta de G.
Note - Cada coincidencia perfecta de gráfico es también una coincidencia máxima de gráfico, porque no hay posibilidad de agregar un borde más en un gráfico de coincidencia perfecta.
No es necesario que una coincidencia máxima de gráfico sea perfecta. Si una gráfica 'G' tiene una coincidencia perfecta, entonces el número de vértices | V (G) | incluso. Si es impar, entonces el último vértice se empareja con el otro vértice y, finalmente, queda un único vértice que no puede emparejarse con ningún otro vértice cuyo grado sea cero. Claramente viola el principio de combinación perfecta.
Example
Note- Lo contrario de la declaración anterior no tiene por qué ser cierto. Si G tiene un número par de vértices, entonces M1 no necesita ser perfecto.
Example
Es coincidente, pero no es una coincidencia perfecta, aunque tiene un número par de vértices.