¿Cómo podemos demostrar que un grafo es bipartito si y solo si todos sus ciclos tienen orden par? Además, ¿este teorema tiene un nombre común? Lo encontré en una caja de herramientas de la Olimpiada de Matemáticas.
Genio... ¡muchas gracias Brian!
Respuestas
¿Demasiados anuncios?Una dirección es muy fácil: si $G$ es bipartito con conjuntos de vértices $V_1$ y $V_2$, cada paso a lo largo de un camino te lleva de $V_1$ a $V_2$ o de $V_2$ a $V_1$. Por lo tanto, para terminar donde empezaste, debes dar un número par de pasos.
Recíprocamente, suponga que cada ciclo de $G$ es par. Sea $v_0$ cualquier vértice. Para cada vértice $v$ en el mismo componente $C_0$ que $v_0$, sea $d(v)$ la longitud del camino más corto desde $v_0$ hasta $v$. Colorea de rojo cada vértice en $C_0$ cuya distancia desde $v_0$ sea par, y colorea de azul los otros vértices de $C_0$. Haz lo mismo para cada componente de $G$. Comprueba que si $G$ tuviera alguna arista entre dos vértices rojos o entre dos vértices azules, tendría un ciclo impar. Por lo tanto, $G$ es bipartito, siendo los vértices rojos y los vértices azules las dos partes.
@BrianM.Scott Creo que en la segunda dirección de la prueba, podemos demostrarlo mediante una prueba directa. es decir, Supongamos que tenemos un ciclo impar, entonces no se pueden crear dos conjuntos independientes. Por lo tanto, no se puede tener un grafo bipartito. la prueba está completada.
pundir
Puntos
11
¿Este teorema tiene un nombre común?
A veces se le llama Teorema de König (1936), por ejemplo en notas de conferencias aquí (Máquina del Tiempo).
Sin embargo, este nombre es ambiguo.
No estoy de acuerdo contigo. En el libro de Diestel, mencionó el teorema de König en la página 30, y mencionó la pregunta de este sitio en la página 14. No mencionó en absoluto ninguna similitud entre los dos. Además, König habla sobre el caso general de r-paritario, por lo que si lo que dices es cierto, entonces el teorema es solo un caso especial del caso general. En este momento, no tengo ningún nombre para ello excepto que es una proposición (lo que significa algo que los matemáticos encuentran interesante pero no surge porque lo estén pensando tanto).
Mark
Puntos
53
Lo siguiente es una versión ampliada de la respuesta de Brian. La respuesta de Brian es casi perfecta, excepto que puede haber un espacio entre "si G tenía alguna arista entre dos vértices rojos o entre dos vértices azules" y "tendría un ciclo impar", lo cual no es tan obvio, al menos para mí (ya que solo podemos concluir que existe un recorrido cerrado de números impares de aristas). Primero demostramos un lema que establece que si hay un recorrido cerrado impar en un grafo, entonces hay un ciclo cerrado impar.
Lema 1 Si hay un recorrido cerrado impar en un grafo, entonces hay un ciclo cerrado impar.
Prueba$\;$ Inducimos sobre el número de aristas $k$ del recorrido cerrado impar. El caso base $k=1$, cuando el recorrido cerrado es un bucle, se cumple trivialmente. Supongamos que, para algún entero positivo $r > 1$, el Lema 1 es verdadero para todos los números impares $k\le2r-1$. Sea $W=(w_1, \dots, w_{2r+1}, w_1)$ un recorrido cerrado de $2r+1$ aristas. Si todos los vértices en $W$ son diferentes excepto por $w_1$, entonces tenemos un ciclo de longitud $2r+1$. Si existen dos vértices idénticos $w_i=w_j$ para $1, entonces $W$ puede escribirse como $(w_1, \dots,w_i, \dots, w_j,\dots, w_1)$. Así, ahora tenemos dos recorridos cerrados $W_1=(w_i,w_{i+1} \dots, w_j)$ y $W_2=(w_j,w_{j+1} \dots, w_i)$. La suma de la longitud de $W_1$ y $W_2$ es igual a la longitud de $W$. Dado que $W$ es de longitud impar, uno de $W_1$ y $W_2$ debe ser de longitud impar $\le 2r-1$. Según nuestra suposición, debe haber un ciclo impar en $W_1$ o $W_2$, y por lo tanto en $W$, lo que completa nuestra inducción. $\square$
Teorema 1 Si no hay ciclos impares en un grafo, entonces el grafo es bipartito.
Prueba$\;$ Supongamos que no hay ciclos impares en el grafo $G=(V,E)$. También se asume que, sin pérdida de generalidad, $G$ está conectado. Luego $V$ puede ser dividido en $(A,B)$, donde $$A=\{v\in V|\text{el camino más corto entre $v$ y $v_0$ es de longitud par}\}$$ $$B=\{v\in V|\text{el camino más corto entre $v$ y $v_0$ es de longitud impar}\}$$ Luego demostramos que no hay aristas entre dos vértices en $A$ o $B$. Supongamos por contradicción que existe una arista $(x,y)\in E$ tal que $x,y \in A$ o $x,y \in B$. Luego, el camino más corto desde $x$ hasta $v_0$, el camino más corto desde $y$ hasta $v_0$, junto con la arista $(x,y)$, forman un recorrido cerrado: $(v_0, \dots,x,y, \dots,v_0)$, que es de longitud impar. Por el Lema 1, $G$ contiene un ciclo impar, lo cual es una contradicción.
Por lo tanto, $G$ es un grafo bipartito entre $A$ y $B$. $\square$
¿No es suficiente notar que dos vértices $u, w$ en el mismo conjunto de la bipartición no pueden compartir una arista ya que $d(v_0,u) = d(v_0,w) \pm 1$?. Supongamos que $u$ está más cerca de $v_0$ que $w$. Entonces, un camino más corto desde $v$ hasta $w$ es el que pasa por $w$. Pero entonces las distancias a $w$ y a $u$ tienen paridad diferente, por lo que no están en el mismo conjunto.
Mishel
Puntos
21
(Por contradicción) (->) Supongamos que n es impar. Sea X={ui tal que i es impar} e Y={ui tal que i es par} como la bipartición formada en el grafo. Consideremos el ciclo C=u1 u2 u3 u4...un u1 como el ciclo en G. Si u1 es impar, un no puede ser impar porque no habría bipartición formada. Por lo tanto, n debe ser par.
rahijain
Puntos
360
Una forma relativamente simple es descomponer el "if and only if" en sus dos partes:
- Probar que si un grafo $G$ es bipartito, entonces no tiene ciclos impares, y
- Si $G$ tiene solo ciclos pares, entonces puedes dividir los vértices en dos conjuntos independientes.
No creo que esto sea un teorema nombrado, es demasiado simple.
