Matemáticas | Coincidencia (teoría de grafos)

Prerrequisito: fundamentos de la teoría de grafos
Dado un grafo no dirigido , una coincidencia es un conjunto de aristas, de modo que no hay dos aristas que compartan el mismo vértice. En otras palabras, la coincidencia de un gráfico es un subgráfico en el que cada Node del subgráfico tiene cero o un borde incidente.
Se dice que un vértice es coincidente si una arista incide sobre él, libre en caso contrario.
Posibles coincidencias de , aquí los bordes rojos indican la coincidencia:

Terminología coincidente –

Coincidencia máxima: se dice que una coincidencia de gráfico es máxima si al agregar un borde que está en pero no en , no hace una coincidencia.
En otras palabras, una coincidencia máxima no es un subconjunto propio de ninguna otra coincidencia de . Por ejemplo, los siguientes gráficos son coincidencias máximas:

agregar cualquier borde a cualquiera de los gráficos anteriores daría como resultado que ya no sean una coincidencia.

Coincidencia máxima: se dice que una coincidencia de gráfico es máxima si es máxima y tiene el número máximo de aristas.
Puede haber muchas coincidencias máximas posibles de un gráfico.
Cada coincidencia máxima es una coincidencia máxima, pero no toda coincidencia máxima es una coincidencia máxima.
Por ejemplo, en la primera figura hay una coincidencia máxima y en la segunda figura, los gráficos segundo y tercero son coincidencias máximas.

Coincidencia perfecta: se dice que una coincidencia de gráfico es perfecta si cada vértice está conectado exactamente a un borde. Todo emparejamiento perfecto es un emparejamiento máximo, pero no todo emparejamiento máximo es un emparejamiento perfecto.
Dado que cada vértice debe incluirse en una coincidencia perfecta, el número de aristas en la coincidencia debe ser donde V es el número de vértices. Por lo tanto, solo existe un emparejamiento perfecto si el número de vértices es par.
Por ejemplo en la primera figura, es un emparejamiento perfecto.
Se dice que una coincidencia es casi perfectasi el número de vértices en el gráfico original es impar, es una coincidencia máxima y deja fuera solo un vértice. Por ejemplo, en la segunda figura, el tercer gráfico es una coincidencia casi perfecta.

• Ejemplo: cuente el número de coincidencias perfectas en un gráfico completo .
• Solución: si el número de vértices en el gráfico completo es impar, es decir, es impar, entonces el número de coincidencias perfectas es 0.
  Pero si es par, podemos derivar una fórmula general para contar el número de coincidencias perfectas.
  Como es par, podemos denotarlo como un entero positivo .
  Cada vértice está conectado con todos los demás vértices en un gráfico perfecto, por lo tanto, el grado de cada vértice es . De estos bordes, tenemos que elegir 1 borde para incluir dos vértices.
  Podemos elegir una ventaja de maneras. Ahora los vértices permanecen y las aristas permanecen ya que las aristas conectadas a los vértices ya seleccionados no se pueden seleccionar porque es una coincidencia.
  Entonces, el número de formas de seleccionar un borde de los bordes es .
  Podemos seguir eligiendo aristas de la misma manera, luego por regla de producto-
  Número de emparejamientos perfectos- .
  Esto también se puede escribir como :
  
  
  
  Entonces, para un gráfico perfecto con vértices, el número de coincidencias perfectas es:

Emparejamiento bipartito:
el emparejamiento tiene muchas aplicaciones en redes de flujo, programación y planificación, coloreado de gráficos, redes neuronales, etc. El más común de estos es el problema de programación donde hay tareas que los trabajadores pueden completar . Las tareas y los trabajadores representan los dos conjuntos de vértices en un gráfico bipartito, donde una tarea está conectada a un trabajador si el trabajador puede completarla.
Por lo tanto, el problema es encontrar una coincidencia máxima.
Más sobre este tema se discute en el artículo – Coincidencia bipartita máxima

Preguntas de GATE CS Corner

Practicar las siguientes preguntas te ayudará a poner a prueba tus conocimientos. Todas las preguntas se han hecho en GATE en años anteriores o en pruebas simuladas de GATE. Es muy recomendable que los practiques.

1. GATE CS 2003, Pregunta 36

Referencias –

Emparejamiento – Wikipedia
Matemáticas discretas y sus aplicaciones, por Kenneth H Rosen

Este artículo es una contribución de Chirag Manwani . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.