Mapa mental de la Primera Unidad

Aquí les dejo un mapa mental acerca de primera unidad de la materia teoría de gráficas, saludos

Tarea 2: Biografia de Havel y Hakimi

Seifollah Louis Hakimi: 

Seifollah Louis Hakimi es un iraní-estadounidense matemático nacido en Irán, profesor emérito de la Universidad de Northwestern , donde presidió el departamento de ingeniería eléctrica 1973-1978.

Hakimi recibió su Ph.D. de la Universidad de Illinois en Urbana-Champaign , en 1959, bajo la supervisión de Mac Van Valkenburg . Cuenta con más de 100 descendientes académicos, la mayoría de ellos a través de su alumno Narsingh Deo.

Se unió al equipo de la Northwastern University, Evanston, como profesor asociado de Ingenieria eléctrica en 1961. 

Él es conocido por la caracterización de las secuencias de grado de grafos no dirigidos,  para la formulación del Árbol de Steiner en redes,  y por su trabajo en la ubicación instalación problemas en las redes, asi como el Algortimo de Havel-Hakimi en 1962.

Vaclam Havel

Václav J. Havel es un matemático checo, especializado en teoría de grafos, cuyo trabajo más importante es la resolución del problema de la secuencia de enteros gráfica en 1955, resuelta independientemente por Hakimi en 1962.

Problema de la secuencia de enteros gráfica

El problema de la secuencia de enteros gráfica consiste en determinar si una secuencia de enteros no-negativos cualquiera es o no gráfica, es decir, es una secuencia de grados de un grafo. Havel publica en 1955 el paper «Poznámka o existenci konečných grafů » en la revista de matemática checa Časopis pro pěstování matematiky donde da solución al problema a través del siguiente teorema:

Teorema de Havel-Hakimi

Una secuencia de enteros d1>=d2>=... >=dv>=0 es gráfica sí, y sólo sí también lo es la lista: d1-1, d3-1, ..., dd1+1 -1, dd1+2, ..., dv  que resulta de eliminar el primer elemento y restar una unidad a los siguientes d1 valores de la lista.

Contribución

Havel publicó alrededor de 90 artículos matemáticos entre los años 1955 y 1994, siendo uno de los primeros Harmonical quadruplet in Moufang plane en la revista Czechoslovak Mathematical Journal y el último: Kdo poprvé užil ve fyzice delta funkci? (Who first used the delta-function in physics?) en la revista Pokroky matematiky, fyziky a astronomie.

Referencias:

·         Wikipedia Foundation (2005). S. L. Hakimi, 2015, http://en.wikipedia.org/wiki/S._L._Hakimi

·         Fotografía de Seifollah Louis Hakimi Recuperado de http://content.cdlib.org/ark:/13030/kt500040nj/

·         Wikipedia Foundation (2005). Václav J. Havel, 2015, http://es.wikipedia.org/wiki/V%C3%A1clav_J._Havel

·         Fotografía de Vaclav J. Havel Recuperado de http://hechosyvidas.blogspot.mx/2014/10/vaclav-havel.html

Tarea 1: Algoritmo de Havel-Hakimi

Este método es gráfico y esta basado en la reconstrucción del grafo, el cual se obtiene al estar insertando vértices y aristas.

Las condiciones para llevar a cabo dicho algoritmo son los siguientes:

1.- La suma debe ser par.

2.- El valor máximo debe ser menor que la longitud. Por ejemplo la sucesión 6, 4, 4, 2, 1, 1 no es gráfica pues el valor mayor de la sucesión (6) es igual que la longitud de esta (6).

3.- Si la sucesión t₁-1, t₂-1, t₃-1,....., ts-1, d_1, d_2,......, d_k es gráfica entonces también lo es la sucesión s, t₁, t₂, t₃,....., ts, d_1, d_2,......, d_k.

Si dos grafos son isomorfos entonces tienen la misma sucesión de grados, pero que dos grafos tengan la misma sucesión de grados no quiere decir que sean isomorfos. Por ejemplo los dos siguiente grafos tienen la misma sucesión 4,4,3,2,2,2,1. Pero no son isomorfos porque por ejemplo en el grafo G los nodos de grado 4 no están unidos, mientras que en el grafo G' los nodos de grado 4 si lo están.

                                                        G                                   G´

     Caracterización:

Recordando una de las condiciones era que la sucesión s, t₁, t₂, t₃,....., ts, d_1, d_2,......, d_k es gráfica entonces tambien lo es la sucesión t₁-1, t₂-1, t₃-1,....., ts-1, d_1, d_2,......, d_k.  

     Demostracion:

Sea G el grafo cuya sucesión es s, t1, t2, … , ts, d1, … ,dk y sean S, T1, T2, …Ts , D1, … , Dk los vértices correspondientes entonces:

1.- Si S es adyacente a T1, T2, …Ts, borramos S y el grafo H=G-{S} es el grafo buscado.

2.-   Si no es así, S no es adyacente a un Ti pero SÍ es adyacente a un vértice Dj con  ti >/dsdsd dj

3.- Si ti= dj , basta intercambiar los papeles de Ti y de Dj. Si ti >dj,

Ti tiene más vecinos que Dj. Sea Z vecino de Ti pero no vecino de Dj. Eliminamos las aristas dibujadas con líneas continuas ( SD_j, ZT_i ) y creamos las discontinuas ( ST_i, ZD_j). Este grafo G1 tiene la misma sucesión grados en el vértice S pero tiene un vecino entre los Ti más que en el grafo G. 

Si en G' ya es S adyacente a T1, T2,…Ts, se procede como antes. Y si no lo es se repite el cambio discontinuas-continuas. Como s es finito se alcanza en algún momento un grafo Gm cuya sucesión es la dada.

Algoritmo:

Partiendo de una sucesión no creciente de enteros positivos o nulos para decidir si ésta es gráfica o no, lo que hay que hacer es aplicar la caracterización vista en el apartado anterior 2.2.2.2 hasta que suceda alguna de las dos situaciones siguientes:

·        Se alcanza una sucesión de 0's Þ la sucesión si es gráfica.

Se obtiene un número negativo Þ la sucesión no es gráfica.

Cita: Peñalver, Gregorio H. "Matematicas." Http://www.dma.fi.upm.es/gregorio/. Http://www.dma.fi.upm.es/gregorio/grafos/SucGrafCertifArboles/html/Sucesiones%20graficas.htm, 2 June 2004. Web. 13 Feb. 2015.