Abrir menú principal

Cuba-Wiki β

Recuperatorio Segundo 26/08/2009 (Algoritmos III)

Back.png Volver a la página de la materia

1) Diseñar un algoritmo que tome un grafo y devuelva un matching maximal ( no nesesariamente maximo ). Mostrar su complejidad y correctitud. El mejor algoritmo que conocemos es de O(n+m)

idea: hacer BFS agregando al matching en cada nivel el elje de mas a la derecha del arbol resultante si es que su padre no es saturado por un eje ya metido en el matching anteriormente.


raiz nivel1 nivel2 ...
             
o***o---o***o---o***o         Espero que se entienda el intento de croqui de
             ---o             croqui de AGM de un grafo tras aplicar BFS 
 ---o***o---o
         ---o
     ---o***o
     ---o

 ---o***o
     ---o***o
         ---o

Es correcto pues no agrega ejes que sean incidentes a un nodo que este saturado. Es maximal porque por cada nodo del grafo se pregunta si el padre esta saturado. Si lo esta todos los ejes incidentes en el que esten o no en el arbol no deben estar en el matching pues tiene un eje adyacente y si no lo tiene agrega a un eje de todos sus incidentes segun el criterio de el de mas a la derecham al matching. La complejidad es O(BFS) pues se realizar operaciones constantes en cada iteracion.

Hay que tener cuidado al usar BFS, ya que en la implementacion comun y corriente BFS recorre todos los nodos pero NO todas las aristas, con lo que pueden quedar ejes sin recorrer. El algoritmo mas facil y seguro es tener un flag para cada nodo marcando si esta saturado o no, y despues simplemente recorrer todas las aristas (usando las listas de adyacencias) y agregarlas al matching de ser posible.


2) Un grafo se dice outerplanar Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Longleftrightarrow} es planar y posee una representacion tal que existe una region (gralmente la exterior) que posee en su frontera a todos los nodos del grafo. Sea G un grafo outerplanar maximal Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle n \geq 3} (maximal en este caso quiere decir que no le puedo agregar otro eje al grafo sin que deje de ser outerplanar)

a) demostrar que G tiene ciclos y es coneco

b) coinsiderar la representacion de G que posee todos los nodos en la region exterior.Demostar que tiene otras regiones y que son todas ellas triangulos

c) demostrar que G tiene n-1 regiones


3) Encontrar una reduccion polinomial de p1 a p2

p1 : Dado un grafo G y un entero k < n -1 , existe un camino de k ejes en G ?

p1 : Dado un grafo G , un entero l < n -1 y dos nodos espesificos "s" y "t", existe un camino de l ejes en G de "s" a "t"?


Idea gral: Dado un G agregar dos nodos nuevos llamados s y t y unirlos a todos los nodos del grafo , eso llevaria O(n) y defino a l = k + 2 , porlo tanto si existe un camino de k + 2 ejes entre s y t , seguro es por q existe en G algun camino de k ejes



Se dice que G(V,X) es unicamente coloreable si dado cualquier coloreo optimo valido , define siempre las mismas particiones de V ( es decir Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \{V_1,V_2 \cdots V_k\}} donde Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle k = X(G)} y cada particion posee nodos de un mismo color).

Ejemplos:

Kn --> si

H5 --> no

Sea G unicamente coloreable demostrar que :

a) Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle (\forall v \in V )\ d(v) \geq X(G) - 1 } .

b) Sea Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \{V_1.V_2 \cdots V_k\}} con Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle k = X(G)} la particion resultante del coloreo. Si Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle i \neq j \Longrightarrow} el grafo inducido por Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle V_i \cup V_j} es conexo.

c) Si Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle X(G) \geq 2 \Longrightarrow } G conexo.


5) Sea G un grafo

Se llama L(G) al grafo de linea de G que tiene tantos nodos como ejes tiene G y dichos nodes se unen Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Longleftrightarrow} en G inciden en al menos un mismo nodo. Ej :

G: o--o--o  L(G):  o---o  (K3) 
      |             \ /
      o              o

Se llama T(G) al grafo de total de G que es la union entre G y L(G) de la siguiente manera : un nodo de L(G) se une con uno de G si y solo si en G eran incidentes el eje que representa el nodo de L(G) y el mismo nodo de G . Ej :


G: o--o--o  T(G):  o---o   --> representan a los ejes de G 
                  / \ / \
                  o--o--o  --> representa a los vertices de G


Sea G un grafo, demostrar las siguientes equivalencias:

a) Error al representar (MathML con SVG o PNG como alternativa (recomendado para navegadores modernos y herramientas de accesibilidad): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle (\forall v \in V)\ d(v) \equiv x _{(2)} } ( es decir que todos tiene la misma paridad, son todos pares o todos impares).

b) L(G) es euleriano.

c) T(G) es euleriano.