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:59] 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 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
