listas graficas

Download listas graficas

Post on 24-Apr-2015

48 views

Category:

Documents

4 download

Embed Size (px)

TRANSCRIPT

Universidad Simn Bolvar

Peter Olejua

Estudio sobre listas grficas

Introduccin:Una lista grfica es una lista de enteros nonegativos, para la cual existe un grafo simple tal que el grado de cada vrtice corresponde a un nico entero en dicha lista.

Estudio sobre listas grficas

Objetivos:

Responder a la interrogante Cundo una lista de enteros es grfica? Hacer un recorrido por las soluciones a este problema:

Havel[1955], Hakimi[1962] Erds-Gallai[1960] Tripathi-Venugolapan-West[2010]

Estudio sobre listas grficas

Prembulo:

Def. Un grafo G es una tripleta que consiste en un conjunto de vrtices V(G), un conjunto de lados E(G) y una relacin que asocia a cada lado dos vrtices (no necesariamente distintos y sin orden) llamados extremos. Si un lado e tiene por extremos v1 y v2, decimos que e es incidente a v1 y a v2, que v1 es adyacente a v2 y que dichos vrtices son vecinos. El conjunto de los vecinos de v en G se denotar

NG(v).

Si no existe e en E(G) que tenga por extremos a v1 y a v2, estos vrtices se llaman independientes.

Estudio sobre listas grficas

Prembulo:

Def. Un lazo es un lado cuyos extremos son iguales. Lados multiples son lados que tienen el mismo par de extremos. Def. Un grafo simple es un grafo sin lazos ni lados multiples.

Estudio sobre listas grficas

Prembulo:

Para v V(G), el grado d(v) es el nmero de lados que tienen a v como extremo (lazos cuentan doble). Si V(G)={v1,v2,...,vn}, la lista de grados de G

es (d(v1),...,d(vn)). Usualmente esta lista se escribe en orden decreciente.

Estudio sobre listas grficas

Prembulo:

Proposicin 1: Si G es un grafo, entonces d(vi)=2|E(G)|. En particular, d(vi) es par. Dem: Al sumar d(vi) contamos el nmero de lados incidentes a vi. Cada lado o es un lazo o tiene dos extremos distintos. As, cada lado suma dos unidades a d(vi).

Estudio sobre listas grficas

Lista realizable: Una lista de enteros nonegativos (d1,...,dn) es realizable si existe un grafo G que la realice, es decir, existe un grafo G y un etiquetamiento de sus vrtices V(G)={v1,v2,...,vn} tal que di=d(vi), para todo i=1,...,n.

Estudio sobre listas grficas

Ejemplo: La lista (5,4,3,3,2,1,0) es realizable.

Estudio sobre listas grficas

Lista grfica: Una lista de enteros negativos es grfica si es realizable por un grafo simple. Ejemplo: La lista (3,3,1,1) es realizable pero no grfica.

Estudio sobre listas grficas

Pregunta: Cundo una lista es realizable? Restricciones a la pregunta:

Cundo una lista es realizable por un grafo que pueda tener lazos? Cundo una lista es realizable por un grafo sin lazos pero que pueda tener lados mltiples? Cundo una lista es realizable por un grafo sin lazos ni lados lados mltiples? O lo que es igual, Cundo una lista es grfica?

Estudio sobre listas grficas

Cundo una lista es realizable por un grafo que pueda tener lazos?

Teorema 1: Una lista de enteros nonegativos (d1,...,dn) es realizable sii di es par. Dem: () Proposicin 1. () Induccin (Luego de la hiptesis inductiva, agregar otro vrtice con (dn+1-1)/2 lazos en el caso impar)

Estudio sobre listas grficas

Cundo una lista es realizable por un grafo sin lazos pero que pueda tener lados mltiples?

Teorema 2 (Hakimi 1962): Sea (d1,...,dn) una lista no-creciente de enteros no-negativos. Existe un grafo sin lazos que realiza dicha secuencia sii di es par y d1 vrvj E(G). remplazamos {uvi,vrvj} con {uvr,vivr}.

Estudio sobre listas grficas

Caracterizacin de ErdosGallai [1960] (El algoritmo: Tripathi-Venugopalan-West [2010])Cmo obtener la nueva subrealizacin en cada iteracin? Sea G la subrealizacin actual:

Caso 2) vrT E(G) y d(vj)min{r,dj} para algn j>r.

Estudio sobre listas grficas

Caracterizacin de ErdosGallai [1960] (El algoritmo: Tripathi-Venugopalan-West [2010])Cmo obtener la nueva subrealizacin en cada iteracin? Sea G la subrealizacin actual:

Caso 2) vrT E(G) y d(vj)min{r,dj} para algn j>r. En una subrealizacin, d(vj)r. En una subrealizacin, d(vj)d(vr), u N(vi)-N(vr). remplazamos {uvi} con {uvr,vivj}.

Estudio sobre listas grficas

Caracterizacin de ErdosGallai [1960] (El algoritmo: Tripathi-Venugopalan-West [2010])Cmo obtener la nueva subrealizacin en cada iteracin? Sea G la subrealizacin actual:

Caso 3) vrT E(G) y vivj E(G), para algunos i con i u,w S

Estudio sobre listas grficas

Caracterizacin de ErdosGallai [1960] (El algoritmo: Tripathi-Venugopalan-West [2010])Cmo obtener la nueva subrealizacin en cada iteracin? Sea G la subrealizacin actual:

Caso 3) vrT E(G) y vivj E(G), para algunos i con i