5.4: Gráficas bipartitas
- Page ID
- 117087
Ya hemos visto cómo las gráficas bipartitas surgen de forma natural en algunas circunstancias. Aquí exploramos las gráficas bipartitas un poco más.
Es fácil ver que todas las caminatas cerradas en una gráfica bipartita deben tener una longitud uniforme, ya que los vértices a lo largo de la caminata deben alternar entre las dos partes. Sorprendentemente, lo contrario es cierto. Necesitamos una nueva definición:
Definición\(\PageIndex{1}\): Distance between Vertices
La distancia entre vértices\(v\) y\(w\),\(\text{d}(v,w)\), es la longitud de una caminata más corta entre los dos. Si no hay paseo entre\(v\) y\(w\), la distancia es indefinida.
Teorema \(\PageIndex{1}\)
\(G\)es bipartita si y sólo si todos los paseos cerrados\(G\) son de longitud par.
- Prueba
-
La dirección hacia adelante es fácil, como se discutió anteriormente.
Ahora supongamos que todos los paseos cerrados tienen incluso longitud. Podemos suponer que\(G\) está conectado; si no, tratamos con cada componente conectado por separado.
Dejar\(v\) ser un vértice de\(G\), dejar\(X\) ser el conjunto de todos los vértices a una distancia par de\(v\), y\(Y\) ser el conjunto de vértices a una distancia impar de\(v\). Afirmamos que todos los bordes de\(G\) unen un vértice de\(X\) a un vértice de\(Y\). Supongamos que no; entonces hay vértices adyacentes\(u\) y\(w\) tales que\(\text{d}(v,u)\) y\(\text{d}(v,w)\) tienen la misma paridad. Después hay una caminata cerrada de\(v\) a\(u\)\(w\) a\(v\) de longitud\(\text{d}(v,u)+1+\text{d}(v,w)\), lo cual es extraño, una contradicción.
El paseo cerrado que proporciona la contradicción no es necesariamente un ciclo, pero esto se puede remediar, proporcionando una versión ligeramente diferente del teorema.
Corolario \(\PageIndex{1}\)
\(G\)es bipartita si y sólo si todos los ciclos en\(G\) son de longitud par.
- Prueba
-
Nuevamente la dirección hacia adelante es fácil, y nuevamente asumimos que\(G\) está conectada. Como antes, dejar\(v\) ser un vértice de\(G\), dejar\(X\) ser el conjunto de todos los vértices a una distancia par de\(v\), y\(Y\) ser el conjunto de vértices a distancia impar de\(v\). Si dos vértices adentro\(X\) son adyacentes, o dos vértices adentro\(Y\) son adyacentes, entonces como en la prueba anterior, hay un paseo cerrado de longitud impar.
Para terminar la prueba, basta con mostrar que si hay un paseo cerrado\(W\) de longitud impar entonces hay un ciclo de longitud impar. La prueba es por inducción en la longitud de la caminata cerrada.
Si no\(W\) tiene vértices repetidos, ya terminamos. De lo contrario, supongamos que el paseo cerrado es
\[v=v_1,e_1,\ldots,v_i=v,\ldots,v_k=v=v_1.\nonumber \]
Entonces
\[ v=v_1,\ldots,v_i=v \quad\hbox{and}\quad v=v_i,e_i,v_{i+1},\ldots, v_k=v\nonumber \]
son paseos cerrados, ambos son más cortos que el paseo cerrado original, y uno de ellos tiene una longitud impar. Por la hipótesis de inducción, hay un ciclo de longitud impar.
Frecuentemente es fructífero considerar las propiedades gráficas en el contexto limitado de las gráficas bipartitas (u otros tipos especiales de gráficas). Por ejemplo, ¿qué podemos decir de los ciclos Hamilton en simples gráficas bipartitas? Supongamos que la partición de los vértices de la gráfica bipartita es\(X\) y\(Y\). Porque cualquier ciclo alterna entre vértices de las dos partes de la gráfica bipartita, si hay un ciclo de Hamilton entonces\(|X|=|Y|\ge2\). En tal caso, el grado de cada vértice es como máximo\(n/2\), donde\(n\) está el número de vértices, a saber\(n=|X|+|Y|\). Por lo tanto, la condición de Mineral (\(\text{d}(v)+\text{d}(w)\ge n\)cuando\(v\) y no\(w\) son adyacentes) es equivalente a\(\text{d}(v)=n/2\) para todos\(v\). Esto significa que la única gráfica bipartita simple que satisface la condición Mineral es la gráfica bipartita completa\(K_{n/2,n/2}\), en la que las dos partes tienen tamaño\(n/2\) y cada vértice de\(X\) es adyacente a cada vértice de\(Y\). El resultado es que la propiedad Mineral no da información interesante sobre las gráficas bipartitas.
Por supuesto, como ocurre con las gráficas más generales, hay gráficas bipartitas con pocos bordes y un ciclo Hamilton: cualquier ciclo de longitud par es un ejemplo.
Observamos que, en general, una gráfica bipartita completa\(K_{m,n}\) es una gráfica bipartita con\(|X|=m\),\(|Y|=n\), y cada vértice de\(X\) es adyacente a cada vértice de\(Y\). Las únicas gráficas de este tipo con ciclos Hamilton son aquellas en las que\(m=n\).