Dilworth del Teorema Implica Konig del Teorema de

Question

Un ejercicio que dice "deducir Konig del Teorema en grafos bipartitos de Dilworth del teorema de posets".

Sea G ser un gráfico bipartito G=(a,B). El fin de los bordes de izquierda a derecha. Un máximo antichain es un independiente más grande de establecer en el gráfico.

Puedo ver a un máximo antichain debe tener cada vértice en G incidente con él. Pero no es lógico que cada borde es incidente con él. Que no puede ser cierto.

Entonces, ¿cómo proceder?

Answer 1

Crear un poset mediante el establecimiento $a \le b$ por cada $a \in A$ $b \in B$ tal que $ab \in E(G)$. Deje que cualquiera de los dos elementos en $A$ o $B$ ser incomparable. En otras palabras, orientar cada borde, de manera que se va de $A$ $B$y hacer un orden parcial en base de esta orientación.

Dilworth del Teorema: la cardinalidad mínima de una colección de cadenas con el sindicato de la $G$ es la máxima cardinalidad de un antichain.

Recuerde que cada cadena debe incluir $1$ o $2$ de los miembros, y queremos que muchas de las cadenas de $2$ miembros como sea posible. Por lo tanto un mínimo de recogida de las cadenas de la unión, $G$ contiene un máximo de coincidencia y cualquier sobrante de los vértices.

Un antichain aquí es el complemento de un vértice de la cubierta. No contiene bordes, por lo que su complemento debe cumplir con todos los bordes. Haciendo un antichain máximo hace que el vértice cubrir un mínimo.

El resto es sólo la aritmética.