Revisión actual |
Tu texto |
Línea 23: |
Línea 23: |
| == Ejercicio 4 == | | == Ejercicio 4 == |
|
| |
|
| Un grafo G es coloreable en forma única si todo coloreo con <math>\chi(G)</math> colores induce la misma partición de los vértices. Mostrar que si G es coloreable en forma única, el subgrafo inducido por dos conjuntos cualesquiera de la partición inducida por los <math>\chi(G)</math>-colores es un subgrafo conexo. | | Un grafo G es coloreable en forma única si todo coloreo con <math>\chi(G)</math> colores induce la misma partición de los vértices. Mostarr si G es coloreable ne forma única el subgrafo inducido por dos conjuntos cualesquiera de la partición inducida dpor los <math>\chi(G)</math>-colores es un subgrafo conexo. |
|
| |
|
| == Ejercicio 5 == | | == Ejercicio 5 == |
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. |
Línea 108: |
Línea 70: |
| a) F | | a) F |
| b) V | | b) V |
| c) F | | c) V |
| d) F | | d) F |
| e) F | | e) F |
|
| |
| === a ===
| |
|
| |
| [[Archivo:A.png]]
| |
|
| |
| <math>S=\{s\}, S'=\{s, a, b\}</math>
| |
|
| |
| <math>c(S) = 3, c(S') = 1+2 = 3</math>
| |
|
| |
| todas las aristas tienen distintas capacidades y sin embargo hay más de un corte mínimo.
| |
|
| |
| === b,c ===
| |
|
| |
| usando la definición, un corte mínimo S es aquel tal que <math>c(S) \leq c(S')</math> con <math>S'</math> cualquier otro corte mínimo.
| |
|
| |
| Entonces se puede escribir esta condición:
| |
|
| |
| <math> \sum\limits_{e \in SS_c} c(e) \leq \sum\limits_{e' \in S'S_c'} c(e') </math>
| |
|
| |
| con <math>S_c = V\backslash S</math> es decir, el complemento.
| |
|
| |
| si multiplicamos por una constante mayor que cero, no cambia nada:
| |
|
| |
| <math> \sum\limits_{e \in SS_c} \lambda c(e) \leq \sum\limits_{e' \in S'S_c'} \lambda c(e') </math>
| |
|
| |
| por distributiva:
| |
|
| |
| <math> \lambda \sum\limits_{e \in SS_c} c(e) \leq \lambda \sum\limits_{e' \in S'S_c'} c(e') </math>
| |
|
| |
| por ser != 0
| |
|
| |
| <math> \sum\limits_{e \in SS_c} c(e) \leq \sum\limits_{e' \in S'S_c'} c(e') </math>
| |
|
| |
| Si bien, la desigualdad no cambia, el valor de cada corte mínimo, si.
| |
|
| |
| === d, e ===
| |
|
| |
| Planteamos lo mismo que en b pero esta vez ...
| |
|
| |
| <math> \sum\limits_{e \in SS_c} c(e) + \lambda \leq \sum\limits_{e' \in S'S_c'} c(e') + \lambda </math>
| |
|
| |
| <math> \sum\limits_{e \in SS_c} c(e) + \sum\limits_{e \in SS_c} \lambda \leq \sum\limits_{e' \in S'S_c'} c(e') + \sum\limits_{e' \in S'S_c'} \lambda </math>
| |
|
| |
| es decir, se suman las constantes, tantas veces como aristas hay en los conjuntos <math>SS_c \text{y} S'S_c'</math> respectivamente.
| |
|
| |
| entonces podemos re escribir:
| |
|
| |
| <math> \sum\limits_{e \in SS_c} c(e) - \sum\limits_{e' \in S'S_c'} c(e') \leq |S'S_c'|\lambda - |SS_c|\lambda </math>
| |
|
| |
| si llamamos dc a la diferencias de las capacidades, a la parte izquierda de la inecuación:
| |
|
| |
| <math> \frac{\text{dc}}{\lambda} \leq |S'S_c'| - |SS_c| </math>
| |
|
| |
| Tenemos una condición para saber cuando un corte puede dejar de ser mínimo al sumar las capacidades por una constante mayor a 0.
| |
|
| |
| <math> \frac{\text{dc}}{\lambda} > |S'S_c'| - |SS_c| </math>
| |
|
| |
| es decir, si encontramos una constante que no compence la diferencia en capacidades vs la diferencia de aristas para un corte mínimo y algún otro corte cualquiera, vamos a tener un cambio en el orden y por lo tanto al menos <math>S</math> dejará de ser un corte mínimo.
| |