viernes, 27 de mayo de 2011

EJERCICIO #1

/*Autora: Camacho Bolaños Angélica Miriam 2293
Descripción del programa: 1. Dada un cantidad en pesos, obtener la equivalencia en dólares, asumiendo que
la unidad cambiaría es un dato desconocido.*/

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

float main(void){
    float val_dolar, pesos, valor_total;
    printf("\n\t ::Bienvenido al programa de equivalencia de pesos en dolares::");
    printf("\n\n\t Ingrese el valor del dolar:   ");
    scanf("%2f", &val_dolar);
   
    printf("\n\t Ingrese la cantidad de pesos:  ");
    scanf("%2f", &pesos);
   
    printf("_____________________________________");
   
    valor_total = val_dolar*pesos;
   
    printf("\n\t Pesos= %.2f, su equivalencia en dolares= %.2f", pesos, valor_total);
  }

sábado, 21 de mayo de 2011

CIFRADO DE CESAR

/*Autora: Camacho Bolaños Angelica Miriam 2293
Descripcion: cifrado de cesar*/
#include <stdio.h>
#include <string.h>


// cadenas referenciadoras para el mensaje original y cifrado
char *alfabeto="abcdefghijklmnñopqrstuvwxyz";
char *cifrado ="DEFGHIJKLMNÑOPQRSTUVWXYZABC";

//Prototipo de funciones para cifrar y decibrar el texto
char* cifra(char*);
char* descifra(char*);

//Funcion principal para probar el uso de las funciones
int main(void)
{
  char cadena[300];
  char *res;
  printf("\n\t Bienvenido al programa de cifrado\n\t");
  fprintf(stdout,"\n\t Ingrese texto a cifrar\t:  ");
  fscanf(stdin,"%s",cadena);
  res=cifra(cadena);
  fprintf(stdout,"\n\t La cadena Cifrada es\t:%s\n\n", res);
  res=descifra(res);
  fprintf(stdout,"\n\t La cadena Descifrada es: %s ",res);
  getchar();
  getchar();
  return 0;
}

//Funcion que cifra el mensaje
char* cifra(char *text)
{
    int i,j;
    for(j=0;j<strlen(text);j++)
    {
      for(i=0;i<strlen(alfabeto);i++)
      {
         if(*(text+j)==*(alfabeto+i))
         {
         *(text+j)=*(cifrado+i);
         }
      }
    }
    return text;
}

//Funcion que descifra el mensaje
char* descifra(char *text)
{
    int i,j;
    for(j=0;j<strlen(text);j++)
    {
      for(i=0;i<strlen(alfabeto);i++)
      {
         if((*(text+j))==*(cifrado+i))
         {
         *(text+j)=*(alfabeto+i);
         }
      }
    }
    return text;
}

ALGORITMOS DE GRAFOS


El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959.
La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene. El algoritmo es una especialización de la búsqueda de costo uniforme, y como tal, no funciona en grafos con aristas de costo negativo (al elegir siempre el nodo con distancia menor, pueden quedar excluidos de la búsqueda nodos que en próximas iteraciones bajarían el costo general del camino al pasar por una arista con costo negativo).
Algoritmo
Teniendo un grafo dirigido ponderado de N nodos no aislados, sea x el nodo inicial, un vector D de tamaño N guardará al final del algoritmo las distancias desde x al resto de los nodos.
1.     Inicializar todas las distancias en D con un valor infinito relativo ya que son desconocidas al principio, exceptuando la de x que se debe colocar en 0 debido a que la distancia de x a x sería 0.
2.     Sea a = x (tomamos a como nodo actual).
3.     Recorremos todos los nodos adyacentes de a, excepto los nodos marcados, llamaremos a estos vi.
4.     Si la distancia desde x hasta vi guardada en D es mayor que la distancia desde x hasta a sumada a la distancia desde a hasta vi; esta se sustituye con la segunda nombrada, esto es:
si (Di > Da + d(a, vi)) entonces Di = Da + d(a, vi)
5.     Marcamos como completo el nodo a.
6.     Tomamos como próximo nodo actual el de menor valor en D (puede hacerse almacenando los valores en una cola de prioridad) y volvemos al paso 3 mientras existan nodos no marcados.
Una vez terminado al algoritmo, D estará completamente lleno.
Complejidad
Orden de complejidad del algoritmo: O(|V|2+|E|) = O(|V|2) sin utilizar cola de prioridad, O((|E|+|V|) log |V|) utilizando cola de prioridad (por ejemplo un montículo).
Podemos estimar la complejidad computacional del algoritmo de Dijkstra (en términos de sumas y comparaciones). El algoritmo realiza a lo más n-1 iteraciones, ya que en cada iteración se añade un vértice al conjunto distinguido. Para estimar el número total de operaciones basta estimar el número de operaciones que se llevan a cabo en cada iteración. Podemos identificar el vértice con la menor etiqueta entre los que no están en Sk realizando n-1 comparaciones o menos. Después hacemos una suma y una comparación para actualizar la etiqueta de cada uno de los vértices que no están en Sk. Por tanto, en cada iteración se realizan a lo sumo 2(n-1) operaciones, ya que no puede haber más de n-1 etiquetas por actualizar en cada iteración. Como no se realizan más de n-1 iteraciones, cada una de las cuales supone a lo más 2(n-1) operaciones, llegamos al siguiente teorema.
TEOREMA: El Algoritmo de Dijkstra realiza O(n2) operaciones (sumas y comparaciones) para determinar la longitud del camino más corto entre dos vértices de un grafo ponderado simple, conexo y no dirigido con n vértices.
Pseudocódigo
   DIJKSTRA (Grafo G, nodo_fuente s)      
       para u V[G] hacer
           distancia[u] = INFINITO
           padre[u] = NULL
       distancia[s] = 0
       Encolar (cola, grafo)
       mientras que cola no es vacía hacer
           u = extraer_minimo(cola)
           para v adyacencia[u] hacer
               si distancia[v] > distancia[u] + peso (u, v) hacer
                   distancia[v] = distancia[u] + peso (u, v)
                   padre[v] = u
                   Actualizar(cola,distancia,v)
Otra versión en pseudocódigo sin cola de prioridad
función Dijkstra (Grafo G, nodo_salida s)
  //Usaremos un vector para guardar las distancias del nodo salida al resto
  entero distancia[n] //Inicializamos el vector con distancias iniciales
  booleano visto[n] //vector de boleanos para controlar los vertices de los que ya tenemos la distancia mínima
  para cada w V[G] hacer
     Si (no existe arista entre s y w) entonces
         distancia[w] = Infinito //puedes marcar la casilla con un -1 por ejemplo
     Si_no
         distancia[w] = peso (s, w)
     fin si
  fin para
  distancia[s] = 0
  visto[s] = cierto
  //n es el número de vertices que tiene el Grafo
  mientras que (no_esten_vistos_todos) hacer
     vertice = coger_el_minimo_del_vector distancia y que no este visto;
     visto[vertice] = cierto;
     para cada w sucesores (G, vertice) hacer
         si distancia[w]>distancia[vertice]+peso (vertice, w) entonces
            distancia[w] = distancia[vertice]+peso (vertice, w)
         fin si
     fin para
  fin mientras
fin función

Ciclo euleriano

Un ciclo euleriano es aquel camino que recorre todas las aristas de un grafo pasando una y sólo una vez por cada arco (arista) del grafo, siendo condición necesaria que regrese al vértice inicial de salida (ciclo = camino en un grafo donde coinciden vértice inicial o de salida y vértice final o meta). Una definición más formal lo define como: "aquel ciclo que contiene todas las aristas de un grafo solamente una vez".
En relación con los ciclos eulerianos Carl Hierholzer publicó la primera caracterización completa de los grafos eulerianos en 1873, probando matemáticamente que de hecho los grafos eulerianos son exactamente aquellos grafos que están conectados con todos y donde cada uno de los vértices tienen grado par.
En la imagen,  C=\{ 1,2,3,4,6,3,5,4,1\}\,es un ciclo euleriano, luego es un grafo euleriano.
Un grafo es una representación, un modelo, compuesto por un número determinado de vértices (nodos) y un número de arcos (aristas) que los relacionan, cada arista o arco tiene la capacidad de relacionar dos nodos. La palabra ciclo se emplea en teoría de grafos para indicar un camino cerrado en un grafo, es decir, en que el nodo de inicio y el nodo final son el mismo, como contrapartida un camino hamiltoniano es un camino que recorre todos los vértices de un grafo sin pasar dos veces por el mismo vértice. Si el camino es cerrado se dice un ciclo hamiltoniano.
Si un grafo admite un ciclo euleriano, se denomina grafo euleriano.
Historia
El origen de la teoría de los ciclos eulerianos fue planteado y resuelto por el propio Leonhard Euler en 1736 en un problema que tiene el nombre de Siete puentes de la ciudad de Königsberg (Prusia oriental en el siglo XVIII y actualmente, Kaliningrado, provincia rusa) dando origen a la Teoría de los grafos.
Puentes Konigsberg.jpgEl problema se enuncia de la siguiente forma: Dos islas en el río Pregel, en Königsberg se unen entre ellas y con la tierra firme mediante siete puentes. ¿Es posible dar un paseo empezando por una cualquiera de las cuatro partes de tierra firme, cruzando cada puente una sola vez y volviendo al punto de partida?

Euler enfocó el problema representando cada parte de tierra por un punto y cada puente, por una línea, uniendo los puntos que se corresponden. Entonces, el problema anterior se puede trasladar a la siguiente pregunta: ¿se puede recorrer el dibujo sin repetir las líneas?
Konigsburg graph.svgEuler demostró que no era posible puesto que el número de líneas que inciden en cada punto no es par (condición necesaria para entrar y salir de cada punto, y para regresar al punto de partida, por caminos distintos en todo momento).
Teorema
Dado G(V,E\,)no orientado y conexo (no existen nodos aislados) valen las siguientes expresiones.
1) G\,es euleriano;
2)  \forall v\in\ Vcon grado (v) \ge 2y par.
3) G=\coprod_{i=1}^n C_itodos disjuntos en los arcos, es decir  C^E_i \cap \; C^E_j =  \emptyset\;con {i \not\ne \; j}
Propiedades
  • Un grafo conexo y no dirigido se dice que es euleriano si cada vértice tiene un grado par.
  • Un grafo no dirigido es euleriano si es conexo y si se puede descomponer en uno con los vértices disjuntos.
  • Si un grafo no dirigido G es euleriano entonces su gráfo-línea L(G) se dice que es también euleriano.
  • Un grafo dirigido es euleriano si es conexo y cada vértice tiene grados internos iguales a los externos.
  • Un grafo no dirigido se dice que es susceptible de ser recorrido (en inglés: traversable) si es conexo y al menos dos vértices en el grafo tienen grado impar.
Contando circuitos eulerianos en digrafos
El número de circuitos euleriano en los digrafos puede ser calculado mediante el teorema denominado en Inglés: BEST-theorem, procedente de los nombres de sus fundadores: de Bruijn, van Aardenne-Ehrenfest, Smith y Tutte.
En dicho teorema se menciona que dado un dígrafo euleriano G := (VE), el número ciclos eulerianos no-equivalentes en el grafo es
C \prod_{v \in V}(\deg^+(v)-1)!   o equivalentemente C \prod_{v \in V}(\deg^-(v)-1)!
siendo C cualquier cofactor de la matriz laplaciana de G.
Camino hamiltoniano
En el campo matemático de la teoría de grafos, un camino hamiltoniano en un grafo es un camino, una sucesión de aristas adyacentes, que visita todos los vértices del grafo una sola vez. Si además el último vértice visitado es adyacente al primero, el camino es un ciclo hamiltoniano.
El problema de encontrar un ciclo (o camino) hamiltoniano en un grafo arbitrario se sabe que es NP-completo. Los caminos y ciclos hamiltonianos fueron nombrados después que William Rowan Hamilton, inventor del juego de Hamilton, lanzara un juguete que involucraba encontrar un ciclo hamiltoniano en las aristas de un grafo de un dodecaedro. Hamilton resolvió este problema usando cuaterniones, pero esta solución no se generaliza a todos los grafos.
Definición
Un camino hamiltoniano es un camino que pasa por cada vértice exactamente una vez. Un grafo que contiene un camino hamiltoniano se denomina un ciclo hamiltoniano o circuito hamiltoniano si es un ciclo que pasa por cada vértice exactamente una vez (excepto el vértice del que parte y al cual llega). Un grafo que contiene un ciclo hamiltoniano se dice grafo hamiltoniano.
Estos conceptos se pueden extender para los grafos dirigidos.
Ejemplos
 Notas
Cualquier ciclo hamiltoniano puede ser convertido en un camino hamiltoniano si se remueve cualquiera de sus aristas, pero un camino hamiltoniano puede ser extendido en ciclo sólo si los vértices de los extremos son adyacentes.
Teorema de Bondy-Chvátal
La mejor caracterización de los grafos hamiltonianos fue dada en 1972 por el teorema de Bondy-Chvátal que generalizaba los resultados anteriormente encontrados por G. A. Dirac. Básicamente dice que un grafo es hamiltoniano si existen suficientes aristas. Primero debemos definir lo que es la cerradura de un grafo.
Dado un grafo G con n vértices, la cerradura (cl(G)) es construida de manera única a partir de G agregando toda arista u-v si el par no adyacente de vértices u y v cumple que grado(v) + grado(u) ≥ n
Un grafo es hamiltoniano si y sólo si su grafo cerradura es hamiltoniano.

Como todos los grafos completos son hamiltonianos, todos los grafos cuya cerradura sea completa son hamiltonianos. Este resultado se basa en los teoremas de Dirac y Ore.
Un grafo con n vértices (n > 3) es hamiltoniano si cada vértice tiene grado mayor o igual a n/2.

Dirac (1952)

Un grafo con n vértices (n > 3) es hamiltoniano si la suma de los grados de 2 vértices no adyacentes es mayor o igual que n.

Ore (1960)
Sin embargo, existe un resultado anterior a todos estos teoremas.
Un grafo con n vértices (n ≥ 2) es hamiltoniano si la suma de los grados de 2 vértices es mayor o igual que n-1.

L.Redei (1934)
Como puede verse, este teorema pide más hipótesis que los anteriores ya que la propiedad de los grados debe cumplirse para todo vértice en el grafo.
4.7 ISOMORFISMO DE GRAFOS
Comparación de grafos: Dados dos grafos G=(Vg, Ag) y F=(VF, AF), determinar si son iguales o no.
  • La comparación se puede realizar fácilmente, comprobando si se cumple que Vg= VF y Ag= AF.
  • Isomorfismo de grafos: Dos grafos G=(Vg, Ag) y F=(VF, AF) se dice que son isomorfos si existe una asignación de los nodos de Vg con los nodos de VF tal que se respetan las aristas.
  • El isomorfismo de grafos es también un problema NP-completo, la solución consistiría básicamente en comprobar todas las posibles asignaciones.

Dos Grafos son Isomorfos si existe una correspondencia biunívoca entre sus vértices tal que dos vértices quedan unidos por una arista en uno de los grafos, si y solo si, los vértices correspondientes del otro grafo quedan unidos por una arista.

Dados los Grafos G = { A; V; j } y G’ = { A’; V’; j’} es necesario que cumpla con las siguientes condiciones:
 Si el número de elementos de G = G’     |V| = |V'|
  • Si hay una correspondencia biyectiva    |A| = |A'|
 
  • Si conserva la relación de incidencia y adyacencia entre los elementos de los conjuntos V y A.

Se dice que dos grafos G1 y G2 son isomorfos si existe una correspondencia biunívoca entre los vértices de G1 y los de G2, con la propiedad de que el número de aristas que unen cada dos vértices de G1 es igual al número de aristas que unen los vértices correspondientes de G2.Los grafos son como granos de arena en la playa. Experimentando un poco nos damos cuenta de que el número de gráficas distintas que podemos construir con sólo algunos vértices y aristas es enorme y de hecho este número se transforma en un número enorme , rápidamente incrementamos el número de vértices y de aristas permitidas . Si½ V(G)½ = n y ½ A(G)½ = m , entonces ½ V(G) z V(G) ½ y hay funciones g de A(G) a V(G) x V(G) cada una de las cuales determina una digráfica. Para n=4 y m=5 este número ya es mayor que un millón .
Si tuviéramos alguna manera de elegir de entre más de un millón de digráficas que obtenemos de nuestras y pudiéramos eliminar las que son esencialmente duplicados , esperaríamos llegar a una lista más manejable que tuviera un ejemplo de cada uno de los tipos de digráficas con 4 vértices y 5 aristas . De una manera mucho mas práctica este plan no resultará , si no para 4 y 5 entonces para números más grandes , pero sigue siendo un enfoque práctico cuando buscamos digráficas con propiedades especiales.
Decimos que dos grafos son isomorfos y escribimos G ~ H si hay correspondencias uno a uno a :V(G) ® V(H) y b :A(G)® A(H) tales que siempre que una arista e en A(G) una los vértices u y v en V(G) , la arista correspondiente b (e) una los puntos correspondientes a (u) y a (v) en V(H) . La figura 1 ilustra el concepto .  El lado izquierdo de la flecha es parte del dibujo de G si y sólo si el correspondiente lado derecho de la flecha es parte del dibujo de H. En símbolos , si G y H están descritas por g 1 y g 2 respectivamente , y si entonces Dos gráficas isomorfas son esencialmente la misma excepto por las etiquetas de sus vértices y aristas .
 Hablando en general , se dice que dos conjuntos con alguna escritura matemática son isomorfos si existe una correspondencia uno a uno entre ellos que preserve [ es decir, se compatible con ] la estructura . Ahora bien las clase de equivalencia son llamadas también clases de isomorfismo.
 Si G y H no tienes aristas paralelas , hemos visto que si podemos considerar a A(G) como un subconjunto de V(G) x V(G) , y A(H) es un subconjunto de V(H) x V(H) . En esta situación la condición de isomorfismo es particularmente sencilla : G es isomorfa a H si hay una correspondencia uno a uno a :V(G) ® V(H) tal que á u,v ñ está en A(G) si y sólo si á a (u) y a (v) ñ está en A(H) . Una a que cumpla con esto se llama un isomorfismo de G sobre H.
Ahora , dadas dos digráficas , ¿ Como determinar cuándo son isomorfas ?, bueno , en general, buscaremos probablemente primero las diferencias obvias o las semejanzas obvias , pero el problema puede no ser de fácil solución . La figura 2 muestra dibujos de 4 digráficas . Todos los dibujos parecen muy diferentes , por lo que intentaríamos encontrar en que son esencialmente distintas las digráficas mismas . Nosotros podemos atacar el problema de muchas maneras distintas y cambiar de un enfoque a otro ; en cambio , un programa de computación o un algoritmo debe descifrar instrucciones anticipadamente y no puede ser tan flexible .
 Hasta el momento no hay ningún algoritmo detector de isomorfismos que sea cualitativamente mucho más rápido que el esquema sencillo que se ha considerado . El trabajo en teoría de complejidad ha mostrado , que la existencia de algoritmos con tiempo polinomial para isomorfismos de digráficas es equivalente a la existencia de algoritmos a tiempo polinomial para resolver otros tipos importantes de problemas , por lo que buscar algoritmos para isomorfismos de digráficas es algo muy activo.
Una cantidad , como el número de vértices o de aristas se llama invariante bajo isomorfismos si su valor es el mismo para cualesquiera dos digráficas isomorfas . Un conjunto de invariantes son de especial utilidad para demostrar que dos digráficas no son isomorfas. Un conjunto de invariantes es completo si siempre que dos digráficas no sean isomorfas al menos hay un invariante en el conjunto , cuyos valores sean distintos para las dos digráficas. Un conjunto completo de invariantes nos mostraría que dos digráficas son isomorfas mostrándonos que cada invariante es el mismo valor para las dos digráficas .
Todas las digráficas de la figura 2 tienen 8 vértices y 12 aristas , así que los invariantes ½ V(G)½ y ½ A(G)½ no son una buena ayuda en este caso , por lo que se necesitaría hacer un análisis más profundo.
 EJEMPLO
a.     Para las digráficas de la figura 3 estos invariantes son como mostraremos a continuación [ omitiremos los pares para los cuales es vacío para toda G que consideremos ]

Podemos ver de un solo golpe que las únicas digráficas que pueden ser isomorfas son y De hecho , basta revisar alguno de los tres siguientes números , para tener toda esa información .
La tabla de valores de ½ ½ no nos dice que y sean isomorfas . Para mostrar isomorfismos seguimos necesitando dar una función a .
Ahora consideremos las digráficas de la figura 2 , dibujadas de nuevo en la figura 4 . Sus invariantes ½ ½ son los siguientes .
Resulta que y son isomorfas , pero podemos demostrar que y no son isomorfas examinando estas digráficas cerca de sus fuentes . También la misma idea nos mostrará que no es isomorfa a ninguna de las otras 3 , por lo que de las 4 las únicas isomorfas son y .
Otra manera de separar a de las demás es observar que cada una de las otras digráficas tienen 3 aristas e,¦ ,g tales que el camino e ¦ va del vértice inicial de g a su vértice terminal. [ Por ejemplo en sea e = yz,¦ = zx y g = yx ] . La digráfica no tiene tales aristas .
Resulta que y serían isomorfas si invirtiéramos todas las de una de ellas . Las digráficas que están relacionadas de esta manera se llaman anti-isomorfas .
La idea de isomorfismo es también útil como una manera de describir la simetría de una digráfica dada.

DIGIOGRAFÍA: