puentes de Königsberg Euler y Grafos
Problema de los puentes de Königsberg
•Su nombre se debe a Königsberg, el antiguo nombre que recibía la ciudad rusa de Kaliningrado.
•Es un célebre problema matemático, resuelto por Leonhard Euler en 1736 y cuya resolución dio origen a la teoría de grafos.
Esta ciudad es atravesada por el río Pregolya, el cual se bifurca para rodear con sus brazos a la isla Kneiphof, dividiendo el terreno en cuatro regiones distintas, las que entonces estaban unidas mediante siete puentes llamados Puente del herrero, Puente conector, Puente verde, Puente del mercado, Puente de madera, Puente alto y Puente de la miel.
Teorema chino
x ≡ a1 (mod m1)
x ≡ a2 (mod m2)
…
x ≡ an (mod mn)
x ≡ a2 (mod m2)
…
x ≡ an (mod mn)
tiene una solución única módulo m= m1m2…mn,
x ≡ a1M1y1 + a2M2y2 + … + anMnyn
donde Mk = m/mk y además Mkyk º 1 (mod mk)
Encuentre m = m1* m2 * …* mn
Encuentre Mk=m/mk, para k=1,2,…,n
Encuentre n inversos, uno para cada Mk mod mk
Establezca la solución como
Encuentre n inversos, uno para cada Mk mod mk
Establezca la solución como
X = a1M1y1 + a2M2y2 + . . . + anMnyn
Aplicaciones del Teorema Chino
El teorema chino del resto tiene importantes aplicaciones en criptografía, en especial para reducir operaciones con números enormes mediante el paso a congruencias. En el algoritmo RSA, por ejemplo, los cálculos se hacen módulo n, donde n es un producto de dos primos p y q. Tamaños habituales para n son 1024, 2048 ó 4096 bits, haciendo que los cálculos requieran una gran cantidad de tiempo. Usando el teorema chino del resto los cálculos pueden ser transportados del anillo
al anillo 
. La suma de las longitudes de bit de p y q es la longitud de bit de n, haciendo p y q considerablemente menor que n. Esto acelera mucho los cálculos. Nótese que las implementaciones del algoritmo RSA usando el teorema chino del resto son más susceptibles a ataques de "fault injection".Aritmética modular
La aritmética modular se utiliza para simplificar los problemas teóricos-numéricos sustituyendo cada entero por el resto de dividirlo entre un entero positivo fijo n. Esto produce el efecto de sustituir el conjunto infinito Z por un conjunto Zn que sólo contiene n elementos. Encontraremos que se pueden sumar, restar y multiplicar los elementos de Zn(igual que en Z), aunque encontraremos dificultades en la división. Zn hereda muchas de las propiedades de Z pero mucho más fácil de trabajar con ellos. (ax = b).
Ejemplo
17≡ 5 (mod 6), 241 ≡ 6 (mod 9), 22051946 ≡ 2(mod 4)
Teorema
Sea n un entero positivo, los enteros a y b son congruentes modulo n si solo si existe un entero k tal que
a = b + km.
a = b + km.
Teorema
Sea n un entero positivo, si a ≡ b (mod n) y c ≡d (mod n) entonces a + c ≡ b + d (mod n) y a≡c ≡ b≡d
(mod n).
(mod n).
Para cualquier entero n ≥1 se verifican las siguientes propiedades:
- Reflexiva a ≡ a (mod n) para cualquier entero a;
- Simétrica a ≡ b (mod n) )→ b ≡ a (mod n).
- Transitiva a ≡ b (mod n) y b ≡ c (mod n) )→ a ≡c (modn).
Estas propiedades definen una relación de equivalencia o de congruencia módulo n en los Z. Queda así particionado Z en clases de equivalencia o congruencias disjuntas.
[a] = fb 2 Z : a ≡ b (mod n) g = f. . ., a - 2n, a - n, a, a + n, a + 2n, . . .g para a 2 Z.
[a] = fb 2 Z : a ≡ b (mod n) g = f. . ., a - 2n, a - n, a, a + n, a + 2n, . . .g para a 2 Z.
Podemos decir que Zn forma un sistema numérico con
propiedades similares a los Z (suma, resta, multiplicación).
[a] + [b] = [a + b],(modn)
[a] - [b] = [a - b],(modn)
[a] * [b] = [a * b](modn)
propiedades similares a los Z (suma, resta, multiplicación).
[a] + [b] = [a + b],(modn)
[a] - [b] = [a - b],(modn)
[a] * [b] = [a * b](modn)
Algoritmo de Euclides
import javax.swing.JOptionPane;
public class Mcd2{
public static void main(String []args){
int num1,num2,min,max,resto,mcd=0;
num1=Integer.parseInt(JOptionPane.showInputDialog("ingrese numero 1"));
num2=Integer.parseInt(JOptionPane.showInputDialog("ingrese numero 2"));
min=Math.min(num1, num2);
max=Math.max(num1, num2);
while(min!=0)
{
resto=max%min;
max=min;
min=resto;
}
mcd=max;
JOptionPane.showMessageDialog(null,"El MCD es: "+mcd+" de "+num1+" y "+num2);
}
}
public class Mcd2{
public static void main(String []args){
int num1,num2,min,max,resto,mcd=0;
num1=Integer.parseInt(JOptionPane.showInputDialog("ingrese numero 1"));
num2=Integer.parseInt(JOptionPane.showInputDialog("ingrese numero 2"));
min=Math.min(num1, num2);
max=Math.max(num1, num2);
while(min!=0)
{
resto=max%min;
max=min;
min=resto;
}
mcd=max;
JOptionPane.showMessageDialog(null,"El MCD es: "+mcd+" de "+num1+" y "+num2);
}
}
Diagrama de Hasse
En matemáticas, un diagrama de Hasse es un represenación de un conjunto parcialmente ordenado finito. La represenación se hace mediante un grafo, o sea un diagrama que consta de nodos y aristas.
Supongamos que tenemos una relación R en A que es relación de orden. Primeramente sabemos que es reflexiva, antisimétrica y transitiva. Formamos el grafo con los elementos de A, estos son los nodos, y las aristas son conexiones entre nodos relacionados, en este caso es un grafo dirigido. La primera condición es que si dos elementos están relacionados, digamos (a,b) ∈ R entonces dibujamos b a un nivel superior de a.
Un diagrama de Hasse elimina la necesidad de representar lazos, puesto que se tiene que la relación parcialmente ordenada es reflexiva.
Puesto que la transitividad también está implicada, se puede prescindir de mostrar líneas entre elementos que tengan un elemento intermedio relacionado, pues se sobrentienden.
Con estos diagramas las relaciones de orden son muy fácil de representar y sobretodo de entender.
ejemplo
sea el conjunto A = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60} (todos los divisores de 60). Este conjunto está ordenado parcialmente por la relación de divisibilidad (D60,|). Su diagrama de Hasse puede ser representado como sigue:
Los diagramas de Hasse son útiles para darse cuenta de si dos c.p.o.’s son isomorfos o no. Por ejemplo el c.p.o. Tiene el siguiente diagrama:
lo que hace evidente el isomorfismo con ({1, 2, 3, 6}, |).
En cambio el c.p.o. ({1, 2, 3, 4}≤) tiene el diagrama:
Como ejemplo adicional observemos el diagrama de Hasse del
c.p.o. ({2, 3, 4, 5, 6, 8, 9, 25}), |):
Conjuntos parcialmente ordenados
Una relación R en un conjunto A se llama un orden parcial si R es reflexiva, antisimétrica y transitiva. El conjunto A junto con el orden parcial R se llama conjunto parcialmente ordenado y se denota por (A, R).
Utilizaremos el símbolo ≤ para las relaciones de orden.
aRb a≤b
Se lee a es anterior a b(menor o igual) o bien b es posterior a a(mayor o igual)
•Distintas relaciones sobre un mismo conjunto, dan lugar a distintos conjuntos ordenados.
•a,b∈A son comparablessi aRbo bRa
Es una relación de orden:
Notación
aRb a≤b
Se lee a es anterior a b(menor o igual) o bien b es posterior a a(mayor o igual)
•Distintas relaciones sobre un mismo conjunto, dan lugar a distintos conjuntos ordenados.
•a,b∈A son comparablessi aRbo bRa
ejemplo
En N, a ≤b ⇔∃n ∈N / b=anEs una relación de orden:
- reflexiva: a=a1 ∀a∈N
- antisimétrica: ∀a,b∈N si a ≤b y b≤a ∃n,m ∈N / b=any a=bm, entonces b= [bm]n=bn*m luego n*m =1 y como n,m ∈N m=n=1, asía=b
- transitiva: ∀a,b,c∈N si a ≤b y b≤c ∃n,m ∈N / b=any c=bm, entonces c= [an]m =an*mluego si k = n·m, ∃k∈N /c=ak, es decir, a≤c
Relaciones en conjuntos
En matemáticas, una relación binaria es una relación matemática R entre los elementos de dos conjuntos A y B. Una relación de este tipo se puede representar mediante pares ordenados, (a,b) Є A X B
Las proposiciones siguientes son correctas para representar una relación binaria R={(a,b) : a Є A ^ b Є B ^ R(a,b)= cierto}
:aRb o R(a,b) o bien (a,b) Є R
-
Propiedades de la relaciónReflexividad
- Una relaci´on binaria R sobre un conjunto A se dice que es reflexiva, cuando cada elemento de A est´a relacionado consigo mismo. Es decir, R es reflexiva ↔ᵾa (aЄ A→ aRa)
- Simétrica
- Una relaci´on binaria R sobre un conjunto A es sim´etrica si cada vez que a est´a relacionado con b se sigue que b est´a relacionado con a. Es decir, R es simetrica↔ ᵾa, b Є A(aRb → bRa)
- Asimetría
- Una relación binaria R definida en un conjunto A se dice que es asim´etrica si cada vez que aRb se sigue que bR/ a. Es decir,
- R es asimétrica↔ ᵾa, b Є A(aRb → bR/ a)
- AntisimetríaUna relaci´on binaria R sobre un conjunto A se dice antisim´etrica si cuando (a, b) 2 R y (b, a) 2 R, entonces a = b. Es decir,R es antisimétrica↔ ᵾa, b Є A(aRb ^ bRa→a=b)
TransitividadSe dice que una relaci´on R definida en un conjunto A es transitiva si cuando (a, b) 2 R y (b, c) 2 R, entonces (a, c) 2 R. Es decir,R es transitiva↔ ᵾa, b,c Є A(aRb ^ bRc→aRc)
Suscribirse a:
Entradas (Atom)