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 | ||
|
algoritmos-oia:grafos:grafos-bipartitos [2017/12/14 19:08] santo [Grafo Bipartito] |
algoritmos-oia:grafos:grafos-bipartitos [2017/12/26 19:12] (actual) sebach ↷ Links adapted because of a move operation |
||
|---|---|---|---|
| Línea 3: | Línea 3: | ||
| Un grafo bipartito es un grafo cuyos vértices se pueden **partir** en **2** conjuntos disjuntos, $V_1$ y $V_1$, tales que cada vértice del grafo esté en exactamente uno, y no haya dos vértices del mismo conjunto tales que comparten una arista. | Un grafo bipartito es un grafo cuyos vértices se pueden **partir** en **2** conjuntos disjuntos, $V_1$ y $V_1$, tales que cada vértice del grafo esté en exactamente uno, y no haya dos vértices del mismo conjunto tales que comparten una arista. | ||
| - | Es decir, $V_1 \cup V_2 = V$, $V_1 \cap V_2 = \varnothing$ | + | Es decir: |
| + | |||
| + | $$V_1 \cup V_2 = V$$ | ||
| + | |||
| + | $$V_1 \cap V_2 = \varnothing$$ | ||
| + | |||
| + | Algunos autores piden que $V_1$ y $V_2$ sean no vacíos. La única diferencia es que eso hace que el grafo trivial (el de un único nodo) sea o no bipartito. Aquí consideraremos al grafo trivial como bipartito. | ||
| ==== Ejemplos ==== | ==== Ejemplos ==== | ||
| Línea 13: | 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:grafos: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?). | ||
| ==== Propiedad fundamental y detección de grafos bipartitos ==== | ==== Propiedad fundamental y detección de grafos bipartitos ==== | ||
| - | Como se ve en los artículos escritos sobre [[algoritmos-oia:bfs|BFS]] y [[algoritmos-oia:dfs|DFS]], estos algoritmos son ideales para detectar si un grafo es bipartito o no. Simplemente arrancamos desde cualquier nodo, vamos pintando de colores distintos al vecino del cual vengo, y si puedo pintar todos sin tener adyacentes del mismo color, es bipartito; si no, no. | + | Como se ve en los artículos escritos sobre [[algoritmos-oia:grafos:bfs|BFS]] y [[algoritmos-oia:grafos:dfs|DFS]], estos algoritmos son ideales para detectar si un grafo es bipartito o no. Simplemente arrancamos desde cualquier nodo, vamos pintando de colores distintos al vecino del cual vengo, y si puedo pintar todos sin tener adyacentes del mismo color, es bipartito; si no, no. |
| + | |||
| + | Una propiedad fundamental de los grafos bipartitos es el siguiente teorema: | ||
| + | |||
| + | **TEOREMA**:Un grafo es bipartito si y solo si no tiene [[algoritmos-oia:grafos: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 no hay ciclos de longitud impar, el grafo es bipartito. Para verlo, basta tomar un nodo origen $s$ arbitrario y separar a todos los nodos según si están a [[algoritmos-oia:grafos:definiciones|distancia]] par (los ponemos en $V_1$) o impar (los ponemos en $V_2$) de este origen (si no es conexo el grafo, se hace lo mismo en cada [[algoritmos-oia:grafos:definiciones|componente conexa]]). **La única manera** de que esto falle, y no la propuesta dada no sea una bipartición válida, es que haya dos vértices $u$ y $v$ adyacentes, a una misma distancia $d$ del origen: | ||
| + | * Si la diferencia de distancias entre $d(s,u)$ y $d(s,v)$ fuera $1$, entonces uno tiene que estar en $V_1$ y el otro en $V_2$ (pues una distancia es par y la otra impar), y no hay problema en que sean vecinos. | ||
| + | * 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:grafos: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. | ||
| - | Una propiedad es que un grafo es bipartito si y solo si no tiene ciclos de longitud impar. Se ve trivialmente que un ciclo de longitud impar no se puede pintar con dos colores, y uno de longitud par sí. Bueno, se puede demostrar que si hay o no un ciclo de longitud impar en el grafo determino si es o no 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. |
| - | Pueden leer la demostración en FIXME (link) | + | |
algoritmos-oia/grafos/grafos-bipartitos.1513278522.txt.gz · Última modificación: 2017/12/14 19:08 por santo
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
