Izomorfismo De Grafos

República Bolivariana de venezuela
Ministerio del Poder Popular para la Educación Superior
Universidad Pedagógica Experimental Libertador
Instituto Pedagógico de Barquisimeto
“Dr. Luis Beltran Prieto Figueroa ”
Barquisimeto-Edo. Lara

Homomorfismo de Grafos, Notación de Algoritmos, Algoritmo Recursivos, Complejidad de loa Algoritmos, Algoritmo de Euclides, Otros Algoritmo de la Ruta máscorta


Alumnos:
Zoraida Cárdenas
Daniel Borrero
Luimar Abreu
Dubal Sosa
Profesora: Marina GiménezMatemática Discreta
Sección: 4IF01

Homomorfismo de grafos.
En la teoría de grafos nos topamos con una definición que rompe los esquemas y es de vital importancia para el teorema de kuratowski que dice que un grafo es plano si contiene un subgrafo que es homeomorfo a K5.o K3,3.
K5. K3,3.

Elconcepto de grafos planos no es otra cosa que un grafo cuyas aristas no se interceptan en otro punto que no sea en los vértices. Dicho todos estos para dar un concepto de homomorfismo es necesario conocer las siguientes definiciones.
Si una grafica tiene un vértice de grado 2 cuyas aristas convergen a vértices distintos podemos decir que las aristas se encuentran en serie. Una reducción de serieconsiste en la eliminación del vértice central de tal manera que v,v1 y v,v2 se transformarían en una sola arista v1,v2 dicho todo esto.
Sea b y c dos grafos diremos que son homeomorfas si b y c se pueden reducir a graficas isomorfas realizando varias reducciones de serie.

Nótese que tanto b como c se pueden reducir al grafo a.
Algoritmos
Un algoritmo es un conjunto de instrucciones oreglas bien definidas, ordenadas y finitas que permite realizar una actividad mediante pasos sucesivos que no generen dudas a quien deba realizar dicha actividad.
Para reconocer un algoritmo es necesario identificar las siguientes características:
* Precisión: cada paso debe ser enunciado con precisión.
* Unicidad: los resultados intermedios en cada paso quedan definidos de manera únicay solo dependen de las entradas y los resultados de las pasos anteriores.
* Carácter finito: el algoritmo se define después de ejecutar un número finito de instrucciones.
* Entrada: el algoritmo recibe una entrada de información.
* Salida: el algoritmo genera o produce una salida.
* Generalidad: el algoritmo se aplica a un conjunto de entradas.

Notación para los algoritmosConociendo que un algoritmo es una serie de pasos, Nace la necesidad de implementar un lenguaje más concreto el cual facilita la interacción del hombre y la maquina partiendo de esto se crea el seudocódigo que mezcla el lenguaje común con ciertas palabras claves dando una forma formar de escribir un algoritmo el cual pueda ser entendido globalmente por todos.
Es importante notar que en el primerpaso del algoritmo se es usual dar nombre al procedimiento que vamos a realizar además allí señalaremos entre paréntesis los parámetros del procedimiento. En general, en la estructura if-then donde usamos una proposición cualquiera.
Ejemplo:
If p then
Si la proposición p es verdadera, se ejecuta acción y la acción pasa a la proposición posterior a la acción, si la condición p es falsa, elcontrol pasa directamente a la proposición posterior a la acción.
Una forma alternativa es la estructura if-then-else ejemplo:
If p then
Acción 1
Else
Acción 2
Esta forma alternativa nos proporciona la opción de que si p es verdadero se ejecuta acción 1 y el control pasa a la proposición posterior a la acción 2, pero si p es falsa, se ejecuta la acción 1 y el control pasa a la proposición...