0 votos

Ejemplo del teorema de Berge sobre el emparejamiento

Estoy leyendo sobre el teorema de Berge sobre el emparejamiento, pero creo que he entendido mal el teorema y las definiciones de alguna manera, porque no puedo dar sentido al ejemplo de abajo. En este ejemplo he marcado el emparejamiento en rosa, y el camino alterno en verde. Este es el único camino alterno que implica la coincidencia que pude encontrar, y claramente no es un camino de aumento.

enter image description here

Me he dado cuenta de que hay una coincidencia mayor que podría obtenerse quitando la arista 3 y añadiendo las aristas 1 y 2. Pero como 1325679 no es un camino alterno, ¿no debería esa posibilidad ser considerada por el teorema?

\=============================================

He aquí el teorema y las definiciones pertinentes:

enter image description here

enter image description here

3voto

sewo Puntos 58

132 es una vía de aumento.

No es necesario que una ruta de aumento contenga todo los bordes que están en su coincidencia hasta ahora.

(De hecho, no tiene que contener cualquier borde que está en su coincidencia hasta el momento - digamos, si usted tiene gráfico de ruta con cuatro vértices $a-b-c-d$ y empezar a coincidir con $a$ a $b$ la ruta de aumento que se necesita para hacer coincidir los otros dos nodos consistirá en la arista $cd$ sólo).

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X