paper_emparejamiento de grafos

5/11/2018 Paper_Emparejamiento de Grafos - slidepdf.com

http://slidepdf.com/reader/full/paperemparejamiento-de-grafos 1/8

ALGORITMO VORAZ PARA EMPAREJAMIENTO MAXIMO DE GRAFOS

Sánchez Enriquez Heider Isaías [email protected] Rodríguez Maysundo Eduardo [email protected]

Ruiz Campos Johnatan Eric [email protected]

Universidad Nacional De Trujillo

Escuela Profesional De Informática

RESUMEN

El presente trabajo de investigación trata de abarcar un temanuevo e impactante que es el Emparejamiento de Grafos,

dado a sus diversas aplicaciones en la vida real. Nuestro problema es realizar un algoritmo deoptimización para hallar un emparejamiento máximo entretodos los vértices de un grafo.

El método mas usado para resolver este problema, usael concepto del Árbol Alternado, a través de un algoritmoformal pero laborioso (para el caso de un grafo no

bipartido). Nosotros en este trabajo desarrollamos unalgoritmo voraz (basado en los grados de los vértices) conun tiempo de cómputo eficiente y eficaz para grafos simples.Para ello daremos a conocer algunos conceptos previos,claves para poder entender el desarrollo del algoritmo, y larepresentación en ejemplos reales.

La referencia principal usada en este trabajo es [1], dedonde pudimos obtener información enriquecida yactualizada.

Palabras Claves: Algoritmo voraz, optimización,emparejamiento máximo, grafo simple, grafo bipartido.

1. INTRODUCCION

En la actualidad muchos problemas de la vida real han sidoesquematizados a través de grafos, para poder hallarles unasolución a través de la optimización. Uno de estos

problemas es el emparejamiento máximo de vértices en ungrafo, que se presentan en problemas que describiremos enuna de nuestras secciones.

Como habíamos ya hablado en el resumen, el algoritmoque se va a desarrollar es de tipo Voraz, que trata de hallar la solución mas optima, a través de unos pasos generales enel estudio de un algoritmo voraz. Este algoritmo es eficaz

para todo tipo de grafos simples y lo mas importante fácil de

entender y poder programar en un computador; talvez desdeel punto de vista matemático no parezca tan formal ya quese trata de un algoritmo voraz y por lo general estos tipos dealgoritmos son heurísticos.

2. CONCEPTOS PREVIOS GENERALES

A continuación se detallarán varias definiciones básicassobre grafos de una forma genérica, independientemente delalgoritmo que desarrollaremos mas adelante:

2.1 Grafo

Un grafo es un par (V, A) donde V es un conjunto finito novacío (llamado conjunto de vértices) y A un subconjuntofinito de pares (V x V) no ordenados de vértices (llamadoconjunto de aristas). Gráficamente, los vértices se

representan por puntos y las aristas por líneas que los unen.Un vértice puede tener 0 o más aristas, pero toda arista

debe unir exactamente dos vértices.

El orden de un grafo es el número de vértices que locompone |V|.

2.2. Adyacentes e Incidentes

Dos vértices son adyacentes si son extremos de una mismaarista. Dos aristas son adyacentes si tienen un extremocomún, así que los vértices adyacentes a un vértice dado sontodos los vértices que están al otro extremo de las aristasque tienen como origen o destino el vértice dado.

Un vértice aislado no tiene vértices adyacentes. Unvértice y una arista son incidentes si el vértice es extremo dela arista.



2.3. Grafo simple

Un grafo simple es un par G = (V, A) donde V es unconjunto finito, no ordenado y no vacío y A es un conjuntofinito de pares no ordenados de vértices distintos de V, esdecir, no debe haber ni aristas múltiples ni bucles.

Fig. 1. Ejemplo de un Grafo simple

2.4. Grafo bipartido o bipartito

Un grafo bipartido es un grafo simple donde se puedeencontrar una partición de V tal que V = X ∪ Y con X ∩ Y

= φ tal que toda arista uv ∈ A une vértices de distinta parte,es decir, une un vértice u de la capa X con un vértice v de lacapa Y.

A continuación se expone un teorema para poder saber si un grafo es o no bipartido.

Teorema: Un grafo G es bipartido si y solo si nocontiene ciclos impares.

1 2 3 4

5 6 7 Fig. 2. Grafo Bipartido

2.5. Grafo completo

Un grafo completo es un grafo simple en el que todo par devértices está unido por una arista, es decir, todos los vérticesestán unidos entre sí. Se representa con K n al grafo completode n vértices. Los grafos completos K n son regulares degrado r = n-1.

1 2

3 4

5 Fig. 3. Grafo Completo K5

2.6. Grafo bipartido completo

Un grafo bipartido completo se designa por K r,s donde|X| = r e |Y| = s, y hay una arista que conecta cada vértice deX con cada vértice de Y.

1 2 3 4

5 6 7 Fig. 4. Grafo Bipartido Completo K4,3

3. CONCEPTOS PREVIOS ESPECIFICOS

A continuación se detallarán varias definiciones sobregrafos más específicos que las anteriores, especializados enemparejamientos. Las siguientes definiciones son necesarias

para comprender correctamente el algoritmo sobr

emparejamiento.

3.1. Emparejamiento

Un emparejamiento (matching) en un grafo no dirigido ysimple g = (v, a) es un subconjunto de aristas M ⊆ A tal quedos aristas cualesquiera de M no tengan un extremo común.Evidentemente un subconjunto de un emparejamiento estambién un emparejamiento aunque de menor cardinal.

Fig. 5. Emparejamiento M

3.2. Vértice saturado y vértice libre

Dado un emparejamiento M en G, los vértices incidentescon alguna arista de M se denominan vértices saturados por M o M-saturados. El resto de los vértices que no cumplendicha condición se llaman vértices no saturados o

insaturados por M, aunque el nombre más común que se lesasigna es el de vértice libre.

3.3. Pareja de un vértice

Se denomina como pareja de un vértice (v1) al vértice (v2)del extremo opuesto en la arista perteneciente alemparejamiento M que tiene como extremo al primero delos vértices, otra forma de decirlo es que el vértice v1 estáemparejado con el vértice v2.



3.4. Emparejamiento perfecto

Un emparejamiento es perfecto cuando todos los vértices deG son extremo de alguna arista de M, es decir, cuando todoslos vértices del grafo son vértices saturados por M.

3.5. Emparejamiento Máximal

Un emparejamiento máximal en un grafo es unemparejamiento que no puede ser ampliado agregando unaarista. Un emparejamiento es máximal si y solo si toda aristade G comparte extremos con alguna arista de M.

Fig. 6. Emparejamiento Máximal

3.6. Emparejamiento máximo

Un emparejamiento máximo es un emparejamiento quetiene el mayor número posible de aristas. Todoemparejamiento máximo es también máximal, pero nonecesariamente al revés, ya que un emparejamiento seamáximal no implica que sea máximo.

Fig. 7. Emparejamiento máximo y Perfecto

Fig. 8. Emparejamiento Máximo – No Perfecto

3.6. Árbol alternado

Es una clase de árbol con raíz específico que se usa para lacreación de caminos alternados utilizados para encontrar

emparejamientos lo más grandes posibles de un grafo. Lascaracterísticas que tienen son:

La raíz del árbol debe ser un vértice libre, acontinuación se definirá que es.

Las ramas del árbol estarán formadas por aristasque, alternativamente, están o no en elemparejamiento M, también se detallarán lascaracterísticas de un emparejamiento acontinuación.

rama que está en el emparejamiento

rama que no está en el emparejamiento

Fig. 9. Ejemplo de árbol alternado

3.6. Camino alternado o alternante

Dado un emparejamiento M en un grafo G, un caminoalternado o M-alternado es un camino donde se alternanaristas de M y aristas que no están en M. Más formalmente

se puede expresar como sigue:

Si vi vi+1 ∈M entonces vi+1 vi+2 ∉M ∀i ∈ {i,....,k-2}.

Si vi vi+1 ∉M entonces vi+1 vi+2 ∈M ∀i ∈ {i,....,k-2}.

Fig. 10. Ejemplo camino M-Alternado

3.7. Camino de aumento

Dado un emparejamiento de M en un grafo G, un camino esaumentador para M o de M-aumento si además de ser

camino alternado sus extremos son vértices libres o nosaturados por el emparejamiento M. Esta definición es muyimportante para comprender el método tradicional.

Fig. 10. Ejemplo camino M-Aumento



4. EVOLUCION DE LOS ALGORITMOS Y SUCOMPLEJIDAD

El primer algoritmo polinómico para determinar unemparejamiento máximal lo dio Edmonds en 1965. Utilizó,como todos los que habían tratado el problema en aquellaépoca, caminos aumentadores. Edmonds dijo que sualgoritmo tenía complejidad O(n4), aunque él no entró endetalles. Sin embargo Gabon y Lawer en 1976 probaronque si se implementaba el algoritmo convenientemente sereducía a O(n3).

Por otra parte, el primer algoritmo que resolvió el

problema de emparejamiento máximo con una complejidadinferior a la cúbica fue el algoritmo de Even-Kariv en 1975con una complejidad de o(n5/2).

El mejor algoritmo en estos momentos se ejecuta en untiempo de o(n1/2m) para un grafo con n vértice y m aristas,es decir, más rápido que el anterior para grafos dispersos.

Este algoritmo es bastante complicado y es el algoritmo deMicali-Vazirani.

5. MÉTODO TRADICIONAL USANDO ÁRBOLALTERNADO

El método mas usado para el emparejamiento máximo degrafos, usa el concepto del Árbol Alternado. Este métodoutiliza dos algoritmos, uno para grafos bipartidos y otro paragrafos generales. La complejidad computacional para el

primero es más eficiente y legible, por esta razóndescribiremos los pasos generales que considera estealgoritmo, pero antes mencionaremos dos teoremas

importantes que utiliza el algoritmo:

Teorema de Hall: Un grafo bipartido G con biparticiónX, Y, tiene un emparejamiento que satura X si y solo si|N(S)| ≥ |S| para todo S ⊆ X. A esto se le conoce como lacondición de Hall

Teorema de Berge: Un emparejamiento M en un grafoG es máximo si y solo si G no tiene ningún M- camino deaumento.

A continuación se detallará el algoritmo encargado de buscar un emparejamiento en grafos bipartidos, pero antes

se enunciarán varias observaciones interesantes que seaplican sobre el algoritmo que se detallará seguidamente.

Si G = (V, A) es un grafo bipartido con V = X ∪ Y, yM es un emparejamiento maximal de G; se tiene que |M| ≤ min {|X|, |Y|}.

Sea G = (V, A) un grafo bipartido con V = X ∪ Y. Sedice que M es un emparejamiento completo de G si |M| =min {|X|, |Y|}.

ENTRADA: Un grafo simple y bipartido G conuna bipartición X, Y.

PROCESO: 1. Tomar un emparejamiento cualesquiera M. En

este paso se da la opción al usuario de elegir interactivamente el emparejamiento inicial, elcual se tomará como paso inicial para realizar el algoritmo. También está la opción de noseleccionar ningún emparejamiento inicial, eneste caso se generará un emparejamientoinicial según un algoritmo que se explicará acontinuación.

2. Buscar un camino de M-aumento, mediante laconstrucción del árbol alternado, acontinuación también se explicará el algoritmoque construye el árbol alternado y encuentraun camino de M-aumento.

Si existe un camino M- aumento ir al paso 3. Sino existe ir al paso 4.

3. Construir un emparejamiento M’ con |M’| = |M|+ 1, asignar a M el nuevo emparejamientoampliado M’ y volver al paso 2.

4. Devolver el emparejamiento M comoemparejamiento máximo.

SALIDA: Un emparejamiento de cardinal máximo.

La complejidad de este algoritmo es analizado en [1] y

es de orden O(n3

).

Para desarrollar el algoritmo para un grafo general, seañade otros conceptos mas, y el tiempo de procesamientocrece aunque la complejidad sigue siendo O(n3).

6. DESARROLLO DEL ALGORITMO

6.1 Presentación del algoritmo como voraz:

Para desarrollar este algoritmo tomamos el concepto deestabilidad de grafos, en donde el vértice que tiene menos

probabilidad de ser escogido (menor grado), es quien escogesu pareja, quien también cumple con la condición (debe ser el vértice adyacente con menor grado posible). De esamanera, emparejando desde los vértices con menor grado,se trata de formar el emparejamiento máximo en un grafo.

A continuación presentamos el algoritmo que resuelveel problema del emparejamiento máximo, teniendo encuenta los pasos estándar de un algoritmo voraz:



Paso 1: inicializar los grados de cada vértice, y loscandidatos con todas las aristas del grafo

Paso 2: sea v1 el vértice de menor grado que no estesaturado por M.

Paso 3: y v2 su pareja de menor grado posible.Paso 4: si los vértice son factibles ir al paso 5, si no

rechazar dicho vértice y retornar al paso 2.Paso 5: agregar a la solución. La arista (v1,v2).Paso 6: sacar de los candidatos todas las aristas

incidentes con dichos vértices (v1, v2).Paso 7: retornar al paso 2, si aun hay aristas para valuar

en los candidatos; si no lo hay, ir al paso 8.Paso 8: retornar el conjunto solución, y fin del

algoritmo.

Como se puede observar en este algoritmo, hacemención a dos conjuntos: el conjunto solución y el conjuntode candidatos; y también escoge un par de vértice y si sonfactibles la añade a la solución y los rechaza del conjunto decandidatos, y esto continúa hasta que el cardinal del

conjunto de candidatos sea 0, y al final retorna la poluciónque contiene al emparejamiento máximo.

Por las características del algoritmo presentadoanteriormente, sin duda es un algoritmo voraz.

A continuación presentamos el pseucodigo para ser programado en un computador:

6.2 Pseucodigo del Algoritmo:

ENTRADA: Un grafo simple G (V, A) SALIDA: Un emparejamiento máximo M, donde

M A.⊂ PROCESO:1. Se inicializan variables importantes como:

VG[ ] un vector de tamaño |V|, en donde sealmacenaran los grados de cada vértice; C es elconjunto de candidatos, y M la solución (C yM almacenan aristas).

2. C← A.3. M← Ф.4. VG[0...n]=[0,..,0].5. para i:=0 hasta i=|E| hacer

5.1 tomar una arista de C; (v1,v2)← C[ i ] 5.2 VG[v1]← VG[v1]+1;

5.3

VG[v2]←

VG[v2]+1;6. mientras ( | C | Ф)≠6.1 v1=vértice no saturado por M y de menor

grado en VG,6.2 v2= vértice no saturada por M y pareja de

V1, tomada de C, con menor grado detodos los adyacentes a V1

6.3 si (v1, v2) es factible, ósea si sonincidentes a una arista no saturada por M,entonces:

• M = M + (v1, v2)• C = C - (v 1, v 2)• C = C - {a=(vi, v j)\ v1 ∈a ó v2

∈a }7. Retornar M, como emparejamiento máximo

de G, y Fin del pseucodigo.

COMPLEJIDAD:Si analizamos la complejidad computacional deeste algoritmo, vemos que depende de dos factores

primordiales: el número de Vértices y el número dearistas. Entonces su tiempo de procesamientoaproximado es el siguiente: T(n) =2n+nlog(m)+log2(m), donde n es el numero devértices y m es el numero de aristas, por lo tanto elOrden del tiempo de complejidad se aproxima aO(n)=(nlog(m)), pero se puede convertir en O(n2)si el grafo es mas denso.

6.3. Para Grafo Bipartido:

El algoritmo por ser general se aplica también para grafos bipartidos, pero se puede reducir la complejidad cambiandociertos pasos:

Paso 1: inicializar los grados de cada vértice, y loscandidatos con todas las aristas del grafo

Paso 2: sea v1 el vértice de grado 1 que no estesaturado por M.

Paso 3: y v2 su única pareja.Paso 4: si los vértice son factibles (si existe un vértice

de grado 1) ir al paso 5; si no fuera así: sacar la primera arista=(v1,v2) de los candidatos (no

hay ninguna problema en hacer esto ya que losciclos en un grafo bipartido son pares), y pasar al siguiente paso.

Paso 5: agregar a la solución. La arista (v1,v2).Paso 6: sacar de los candidatos todas las aristas

incidentes con dichos vértices (v1, v2).Paso 7: retornar al paso 2, si aun hay aristas para

valuar en los candidatos; si no lo hay, ir al paso 8.

Paso 8: retornar el conjunto solución, y fin delalgoritmo.

Pues el pseucodigo se regiría a los cambios aquí

realizados.

6.4. Ejemplo grafico del algoritmo:

Tomemos el siguiente grafo:



Fig. 11. Grafo de aplicación

Donde:V = {0, 1, 2, 3, 4, 5, 6, 7}.A = {(0,1), (0,2), (0,3), (1,2), (1,3), (2,6), (2,7), (3,4), (3,5),

(4,5), (6,7)}

Aplicando el algoritmo:Paso 1:

C= {(0,1), (0,2), (0,3), (1,2), (1,3), (2,6), (2,7), (3,4), (3,5),(4,5), (6,7)}M={ }

Los grados de todos los vértices son:gra(0)=3, gra(1)=3, gra(2)=4, gra(3)=4, gra(4)=2, gra(5)=2,gra(6)=2, gra(7)=2.

Entonces el vector de grados es como sigue:VG= {3, 3, 4, 4, 2, 2, 2, 2}, cada posición se almacenan losgrados da cada vértice siguiendo el orden.

Paso 2:Ahora se escoge el vértice de menor grado, en este caso

hay cuatro vértices de grado 2, entonces por ordenlexicografito escojo el vértice V1=4. Su menor adyacenteseria el vértice V2=5, entonces emparejamos dichos vérticesy añadimos a M. y posteriormente le quitamos de C y todaslas aristas incidentes a los vértices 4 y 5.

M = { (4,5) }C= {(0,1), (0,2), (0,3), (1,2), (1,3), (2,6), (2,7), (3,4), (3,5),(4,5), (6,7)}

Entonces C={(0,1), (0,2), (0,3), (1,2), (1,3), (2,6), (2,7),(6,7)}

El vector de grados se actualiza:VG= {3, 3, 4, 2,-1, -1, 2, 2},

se coloca con -1 a la posición del vértice 4 y 5 paraindicar que ya son saturados por M y no deben considerarse

para la siguiente iteración.

Regresamos al bucle puesto que todavía hay elementosen la lista de candidatos.

Paso 3:

Tomamos ahora el vértice de menor grado 6 y su menor adyacente 7. Entonces añadimos a la solución:

M = {(4,5), (6,7)}C= {(0,1), (0,2), (0,3), (1,2), (1,3), (2,6), (2,7), (6,7)}.Entonces C={(0,1), (0,2), (0,3), (1,2), (1,3),}

El vector de grados se actualiza:VG= {3, 3, 2, 2,-1, -1, -1, -1},Regresamos al bucle puesto que todavía hay elementos

en la lista de candidatos.

Paso 4:Solo nos quedan 4 vértices no saturados, escogemos el

de menor grado, y es el vértice 2 y su menor adyacente seria0, por orden lexicografito.

M = {(4,5), (6,7) , (0,2)}C= {(0,1), (0,2), (0,3), (1,2), (1,3)}.Entonces C={(1,3)}

El vector de grados se actualiza:VG= {-1, 1, -1, 1,-1, -1, -1, -1},

Regresamos al bucle puesto que todavía hay elementosen la lista de candidatos.

Paso 5:Y solo nos queda una arista como forma un

emparejamiento es tomada por M:

M = {(4,5), (6,7) , (0,2), (1,3)}C= {}.Entonces C= Ф. Y termina el bucle:

→ El emparejamiento M encontrado es máximo y perfecto ya que consume todos los vértices del Grafooriginal.

Gráficamente el emparejamiento M quedaríarepresentado de la siguiente manera:

Fig. 12. Emparejamiento M

7. ALGUNAS APLICACIONES REALES

Después de presentarles todo lo concerniente al algoritmo,ahora es momento de contestar la pregunta que siempre nos



hacemos: ¿En que se aplica este algoritmo?, las aplicacionesque hemos recopilado y que les vamos a presentar acontinuación, son problemas de la vida real.

Son muchas las situaciones en las que hay que realizar asignaciones o emparejamientos sujetos a restricciones, por ejemplo, profesores y cursos a impartir, pilotos y horarios devuelo, mujeres y posibles maridos. Así que a continuaciónse detallarán algunas de estas situaciones:

7.1. Trabajos y aspirantes:

El problema se presenta en una empresa que tiene ciertonúmero de vacantes de trabajo y un grupo de aspirantesdesean cubrirlos, cada aspirante esta cualificado paraalgunos de estos trabajos; entonces nace el problema: puedecolocarse a todos los aspirantes en puestos para los queestén preparados? (a esto se le llama el problema deasignación).

Podemos representar este problema en un grafo bipartido, al grupo de aspirantes le llamamos A, y al grupode vacantes P:

P

A

p1 p2 p3 p4 p5

a1 a2 a3 a4

Fig. 13. Grafo que representa el problema.

El algoritmo para grafos bipartidos escogería elemparejamiento máximo y de esa manera resolvería el

problema.

7.2. Comités:

Otro ejemplo sería en una clase de una escuela hay un ciertonúmero de comités, cada uno de estos n comités debe tener un secretario. Con el fin de evitar que un grupo pequeño

pueda ejercer una influencia excesiva, se ha estipulado queno se permitirá a ningún m miembro ser secretario de másde un comité. ¿Bajo qué condiciones es esto posible? No

siempre lo es; si hay demasiados comités en una claserelativamente pequeña, es más complicado. Para resolver el

problema volvemos a crear un grafo bipartido siendo uno delos conjuntos de vértices los n comités y el otro conjunto devértices de los alumnos que hay en la clase, dibujaríamosuna arista desde un comité hasta un alumno a si a esmiembro de ese comité. Así que la condición de diversidaden este caso será: cualquier grupo de k comités tiene queincluir al menos a k alumnos distintos, para que se puedanelegir secretarios diferentes.

7.3. Emparejamientos todos contra todos:

Es el caso de los torneos donde se debe elegir como ir emparejando a los participantes a medida que avanza lacompetición. En el caso de un torneo jugado por el sistemade eliminatorias, el problema es muy sencillo: todos los

perdedores se retiran en cada ronda y se empareja a losganadores que van quedando, dando eventualmentedescanso a un jugador si es que queda un número impar de

jugadores.

El problema sería más complicado cuando el torneo se juega por un sistema todos contra todos o liguilla, el tipo detorneo que suele seguirse en un campeonato de ajedrez. Enél, cada jugador ha de enfrentarse con cada uno de losdemás jugadores; nuestro objetivo es planificar el torneo deantemano, fijando las parejas de oponentes en cada una delas rondas.

Esta situación se puede modelizar de nuevo con grafos.Suponemos que hay n jugadores, de modo que cada uno deellos juega n-1 partidos con los otros participantes. Cada

partido se representa por una arista ab conectando dos jugadores que serán los vértices. El total de los partidoscorresponde al grafo completo de n vértices.

Una ronda del torneo consiste en emparejar a los jugadores de dos en dos. Normalmente el número idóneo para planificar estos torneos deberá ser par, ya que en estecaso todos los jugadores se pueden emparejar entre sí, en elcaso de que el número de jugadores fuera impar se pudieraañadir un jugador ficticio y el jugador emparejado con este

último le tocará descansar en esa ronda.

7.4. El Problema de Idiomas

Todos los ejemplos que hemos citado anteriormente semodelizan con grafos bipartidos, pero el problema deemparejamiento es más general, como hemos vistoanteriormente cuando hemos dividido los algoritmosdependiendo del tipo de grafo que se deba tratar. Haysituaciones que no se pueden ser modelizadas con este tipode grafos. El siguiente ejemplo es uno de ellos.

En un grupo de personas, donde cada una habla varios

idiomas, se quiere formar el mayor número posible de parejas, de modo que los dos integrantes de una misma pareja conozcan un idioma común. Los idiomas que hablacada persona se reflejan en la tabla siguiente:



Tabla 1. Representación del problema de idiomas.

Las relaciones establecidas se representan por el grafo G dela siguiente figura que no es bipartido. Pero en este caso, lasolución del problema también es un subgrafo cuyosvértices tengan grado uno, y que tengan el mayor número

posible de aristas. Dos posibles soluciones entre todas lasque hay vienen dadas por los subgrafos M1 y M2 que semuestran a continuación.

A

B

CD

E

A

B

CD

E

M1M2

Fig. 14. Modelización y solución al problema de los

idiomas.

* La búsqueda de emparejamientos en grafos se haconvertido en los últimos años en un destacado campo deestudio apareciendo en gran número de importantesaplicaciones prácticas. Además de problemas relativos aasignación de trabajos, hay muchas otras aplicacionesindustriales, que incluyen el transporte de mercancías desdelas fábricas hasta los almacenes o mercados.

8. CONCLUSIONES

• El emparejamiento de grafos es un tema de estudionuevo pero de grandes aplicaciones, por ello nenecitade un algoritmo eficiente y efectivo para la resoluciónde los diversos problemas sobre emparejamientos.

• El algoritmo voraz para resolver el problema delemparejamiento máximo de vértices en un grafo, es unasolución adecuada por su efectividad y legibilidad.

• La complejidad computacional promedio del algoritmovoraz es de O(nlog(n)), pero puede llegar hasta O(n2)

para grafos mas densos.

• Para el caso de grafos bipartidos el tiempo de procesamiento es mejor ya que el algoritmo paraeste caso modifica algunos pasos, para hacerlomas eficiente.

Francés Inglés Alemán Ruso

Ana X X

Berta X X

Carlos X X

Daniel X X

Enrique X X

9. REFERENCIAS

[1] Pérez Martín Raquel, Emparejamiento de Grafos, Trabajode fin de Carrera, Santiago de Chile, Diciembre 2004.

[2] Hernández Peñalver Gregorio, Emparejamientos y flujos,UPM, 2005.

[3] Ore, Oystein. Grafos y sus aplicaciones. Euler 1995.

[4] West, Douglas B. Introduction to graph theory. PrenticeHall 2001.

paper_emparejamiento de grafos

Documents