Recuperatorio Segundo 26/08/2009 (Algoritmos III)

De Cuba-Wiki
Saltar a: navegación, buscar
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 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 (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 donde y cada particion posee nodos de un mismo color).

Ejemplos:

Kn --> si

H5 --> no

Sea G unicamente coloreable demostrar que :

a) .

b) Sea con la particion resultante del coloreo. Si el grafo inducido por es conexo.

c) Si 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 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) ( es decir que todos tiene la misma paridad, son todos pares o todos impares).

b) L(G) es euleriano.

c) T(G) es euleriano.