Herramientas de usuario
algoritmos-oia:grafos:grafos-bipartitos
Diferencias
Muestra las diferencias entre dos versiones de la página.
| Ambos lados, revisión anterior Revisión previa Próxima revisión | Revisión previa Última revisión Ambos lados, revisión siguiente | ||
|
algoritmos-oia:grafos:grafos-bipartitos [2017/12/14 19:56] santo |
algoritmos-oia:grafos:grafos-bipartitos [2017/12/26 19:12] sebach ↷ Page moved from algoritmos-oia:grafos-bipartitos to algoritmos-oia:grafos:grafos-bipartitos |
||
|---|---|---|---|
| Línea 19: | Línea 19: | ||
| Además, resulta que muchos problemas pueden resolverse más fácilmente en un grafo bipartito, que en el caso de un grafo general, del que nada conocemos. Esto hace que a veces sea útil poder darse cuenta de que estamos ante un grafo bipartito. | Además, resulta que muchos problemas pueden resolverse más fácilmente en un grafo bipartito, que en el caso de un grafo general, del que nada conocemos. Esto hace que a veces sea útil poder darse cuenta de que estamos ante un grafo bipartito. | ||
| + | |||
| + | Otra propiedad muy útil es que los [[algoritmos-oia:definiciones|subgrafos]] de los grafos bipartitos también son bipartitos. | ||
| La bipartición (división en los dos conjuntos $V_1$ y $V_2$) no siempre es evidente del enunciado. Por ejemplo, si tenemos un grafo grilla, en el cual tenemos un nodo por cada casilla de una cuadrícula de $n \times m$, y una arista entre dos nodos exactamente cuando las correspondientes casillas comparten un lado, el grafo grilla **siempre es bipartito** (Ejercicio: ¿Por qué? ¿Cómo es la bipartición?). | La bipartición (división en los dos conjuntos $V_1$ y $V_2$) no siempre es evidente del enunciado. Por ejemplo, si tenemos un grafo grilla, en el cual tenemos un nodo por cada casilla de una cuadrícula de $n \times m$, y una arista entre dos nodos exactamente cuando las correspondientes casillas comparten un lado, el grafo grilla **siempre es bipartito** (Ejercicio: ¿Por qué? ¿Cómo es la bipartición?). | ||
| Línea 27: | Línea 29: | ||
| Una propiedad fundamental de los grafos bipartitos es el siguiente teorema: | Una propiedad fundamental de los grafos bipartitos es el siguiente teorema: | ||
| - | Un grafo es bipartito si y solo si no tiene [[algoritmos-oia:definiciones|ciclos simples]] de longitud impar. | + | **TEOREMA**:Un grafo es bipartito si y solo si no tiene [[algoritmos-oia:definiciones|ciclos simples]] de longitud impar. |
| Si un ciclo simple tiene longitud impar, es imposible formar la separación en dos conjuntos: si empezamos por un nodo cualquiera del ciclo, $v_0$, y lo ubicamos pore ejemplo en $V_1$, el siguiente del ciclo debe ser $v_1 \in V_2$. Pero luego debe ser $v_2 \in V_1$, y entonces debe ser $v_3 \in V_2$, y así siguiendo, los $v_i$ con $i$ impar van en $V_2$, y los $v_i$ con $i$ par van en $V_1$. Pero como el ciclo tiene longitud total impar, al haber pintado todos los nodos y "completar la vuelta al ciclo", el primero y el último quedan como vecinos y del mismo color, con lo cual no es posible que sea bipartito. | Si un ciclo simple tiene longitud impar, es imposible formar la separación en dos conjuntos: si empezamos por un nodo cualquiera del ciclo, $v_0$, y lo ubicamos pore ejemplo en $V_1$, el siguiente del ciclo debe ser $v_1 \in V_2$. Pero luego debe ser $v_2 \in V_1$, y entonces debe ser $v_3 \in V_2$, y así siguiendo, los $v_i$ con $i$ impar van en $V_2$, y los $v_i$ con $i$ par van en $V_1$. Pero como el ciclo tiene longitud total impar, al haber pintado todos los nodos y "completar la vuelta al ciclo", el primero y el último quedan como vecinos y del mismo color, con lo cual no es posible que sea bipartito. | ||
| Línea 35: | Línea 37: | ||
| * Es imposible que la diferencia de distancias entre $d(s,u)$ y $d(s,v)$ sea de 2 o más, pues de lo contrario se violaría automáticamente la [[algoritmos-oia:definiciones|desigualdad triangular]] entre los vértices $s,u,v$. | * Es imposible que la diferencia de distancias entre $d(s,u)$ y $d(s,v)$ sea de 2 o más, pues de lo contrario se violaría automáticamente la [[algoritmos-oia:definiciones|desigualdad triangular]] entre los vértices $s,u,v$. | ||
| - | Pero entonces, tomando esa arista $(u,v), junto con caminos mínimos $P_1$ de $s$ a $u$, y $P_2$ de $s$ a $v$, entre los 3 se forma un ciclo, de longitud total $2d+1$, que es impar. De cualquier ciclo impar se puede extraer un ciclo simple impar, así que en este caso se concluye que si esto pasa es porque el grafo directamente no era bipartito. | + | Pero entonces, tomando esa arista $(u,v)$, junto con caminos mínimos $P_1$ de $s$ a $u$, y $P_2$ de $s$ a $v$, entre los 3 se forma un ciclo, de longitud total $2d+1$, que es impar. De cualquier ciclo impar se puede extraer un ciclo simple impar, así que en este caso se concluye que si esto pasa es porque el grafo directamente no era bipartito. |
| FIXME: Hablar del algoritmo de bipartición basado en "duplicar los nodos", guardando en cada uno la paridad con que se llegó. Esa idea general es importante en otros problemas. | FIXME: Hablar del algoritmo de bipartición basado en "duplicar los nodos", guardando en cada uno la paridad con que se llegó. Esa idea general es importante en otros problemas. | ||
algoritmos-oia/grafos/grafos-bipartitos.txt · Última modificación: 2017/12/26 19:12 por sebach
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
