Advertencia: no has iniciado sesión. Tu dirección IP se hará pública si haces cualquier edición. Si
inicias sesión o
creas una cuenta, tus ediciones se atribuirán a tu nombre de usuario, además de otros beneficios.
Puedes deshacer la edición.
Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual |
Tu texto |
Línea 58: |
Línea 58: |
| Tomar dos conjuntos <math>A</math> y <math>B</math> de la partición inducida <math>P</math>. | | Tomar dos conjuntos <math>A</math> y <math>B</math> de la partición inducida <math>P</math>. |
|
| |
|
| Suponer que no son conexos. Entonces ... | | Suponer que no son conexos. |
| | |
| === espero que bien ===
| |
| | |
| Al no ser conexos, en el subgrafo inducido de <math>A</math> y <math>B</math> existen dos componentes conexas (como mínimo).
| |
| | |
| Llamemoslas <math>C_1</math> <math>C_2</math>, además algunos vértices de <math>C_1</math> caen en A y otros en B, y lo mismo con <math>C_2</math>.
| |
| | |
| Entonces podemos elegir todos los nodos de <math>V(C_1) \cap A</math> y swapear sus colores con <math>V(C_2) \cap B</math>.
| |
| | |
| Con lo cual, tenemos una coloración de mismo número cromático, que induce otra partición de los vértices.
| |
| | |
| Un dibujo puede ayudar a visualizar:
| |
| | |
| -------
| |
| A: -/ \- B:
| |
| / \ -------
| |
| / a(q)----\------/---d(p)\-
| |
| / \ / | \
| |
| | | / | \
| |
| | b(q)-----+--+------+ |
| |
| | | \ /
| |
| \ / \ /
| |
| \ c(q)--------------e(p)/-
| |
| \ / -------
| |
| -\ /-
| |
| -------
| |
| | |
| | |
| A: tiene 3 vértices, a, b, c con color q y B tiene 2 (d, e) con color p.
| |
| | |
| Si cambiamos c(q) y e(p) por c(p) y e(q), movimos el vértice c al conjunto B y el e al A.
| |
| | |
| Con esto demostramos la contra recíproca: si el subgrafo inducido por dos conjuntos cualesquiera de la partición inducida por los <math>\chi(G)</math>-colores *no* es un subgrafo conexo; entonces el grafo original no es coloreable de forma única.
| |
| | |
| === mal resuelto ===
| |
| | |
| (Como dice el título... esto está *mal* resuelto. Que no sean conexos *no* significa que no tengan aristas entre si y que por lo tanto se pueda usar el mismo color.
| |
| Lo dejo por si alguien pensándolo comete la misma metida de pata.)
| |
|
| |
|
| Pero entonces se les puede asignar el mismo color pues entre ellos no hay adyacencias en el grafo original y con el resto de los vértices no hay problemas pues pertenecen a otro conjunto, es decir tenían otro color. | | Pero entonces se les puede asignar el mismo color pues entre ellos no hay adyacencias en el grafo original y con el resto de los vértices no hay problemas pues pertenecen a otro conjunto, es decir tenían otro color. |