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 20:00] santo [Propiedad fundamental y detección de grafos bipartitos] |
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?). | ||
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
