Archivo

Archive for 21 mayo 2011

Otra Pelicula Relacionada Con Las Matematicas !!!

Matt Damon encarna el personaje de Will, este joven superdotado en el campo de las ciencias. Él es consciente de sus facultades extraordinarias pero como no es algo que le reporte esfuerzo alguno, no lo ve como algo meritorio de elogios.

Will ha leído todo tipo de libros desde su infancia, y es capaz de memorizar su contenido al mismo tiempo que se va formando culturalmente de modo siempre autodidacta.

Trabaja en los servicios de limpieza de una prestigiosa Universidad de matemáticas y un día resuelve un problema del que ningún alumno es capaz de dar respuesta. Su anonimato se romperá por un profesor de la Universidad, quien intentará que Will saque el máximo provecho de sus facultades; unas facultades con las que este maestro siempre soñó y que ahora no le permiten conciliar el sueño, porque ve como el muchacho no sabe valorarlas del mismo modo que él.

Hasta aquí la historia no presenta ningún atisbo dramático, pero es que todavía no hemos llegado al por fin oscarizado Robin Williams, que o nos hace reir o llorar. En este caso, le tocará representar un papel muy similar al de “El club de los poetas muertos”.

Will tiene unos amigos, que como él, proceden de los barrios bajos. Ellos están contentos con su situación y no hacen nada para mejorarla. Su filosofía de la vida consiste en realizar un trabajo sencillo, comer, pelearse en la calle y sobretodo, beber.

Como consecuencia de una de estas peleas en la que Will se ensaña brutalmente contra un joven, será juzgado y condenado y esta vez su elocuencia no le servirá para librarse del cumplimiento de la pena, y será el profesor que ha depositado toda su fe y su esperanza en este joven de espíritu rebelde e indomable, quien adquirirá su custodia mediante el pago de la fianza, a lo que el Juez accederá bajo la condición de que Will realice con regularidad visitas a un psiquiatra.

Robin Williams, es Sean, el psiquiatra al que debe acudir Will, para reconciliarse con su pasado: un pasado triste y desolador en el que hay que indagar para poder llegar a comprender la personalidad del muchacho.

Sólo uno de los amigos de Will (papel intepretado por Ben Affleck), intentará hacerle comprender que él no pertenece a ese tipo de vida; que debido a sus cualidades puede aspirar a algo con lo que todos sueñan y que estaría tirando por la borda un futuro más que prometedor si sigue al lado de ellos, ya que según este amigo, todos ellos están destinados al fracaso.

A todos estos personajes hay que sumar la presencia de “la chica de la película”: Minnie Driver, quien despertará en Will el sentimiento de estar enamorado por primera vez.

Will es sólo un muchacho asustado que de repente se ve sometido a varias presiones exteriores:

  • la del profesor que le atosiga para que acceda a los mejores puestos del mercado laboral, ante la esperanza de que llegue a convertirse en un genio capaz de ayudar a la humanidad con su potente intelecto para crear nuevas fórmulas o desvirtuar teorías de reconocidos científicos que hasta ahora nos servían como método de estudio;
  • la de la chica, que pretende establecer con él una relación de compromiso al poco tiempo de conocerse, provocándole una sensación de inseguridad y miedo a la que deberá hacer frente si pretende seguir con ella;
  • la de Sean, que le enfrentará con su pasado, un pasado que le convirtió en una víctima de los malos tratos y del que no logra desprenderse. Esos recuerdos que Will guarda en su interior, le impiden el abrir su corazón a las personas, porque él de pequeño aprendió que las personas eran malvadas, y no se da oportunidad a sí mismo de demostrarse que donde menos se lo espera, puede encontrarse con un verdadero amigo, capaz de orientarle y ayudarle, de hacerle sonreir y llorar, pero sobretodo de hacerle entender que no puede seguir viviendo encerrado en su mundo de ficción, que debe demostrarse a sí mismo lo fuerte que puede llegar a ser, que debe tomar las decisiones que más le convengan, porque antes que un genio, es una persona, con unos sentimientos a los que debe prestar atención; y sobretodo nunca rendirse si realmente estás enamorado de alguien.
    Todo esto lo aprenderá de este entrañable
    psquiatra traumatizado por la muerte de su esposa, que al mismo tiempo que intenta descubrir la personalidad de Will, nos irá mostrando los secretos más ocultos de su gran corazón.

Esta película, soprende por los diálogos, por su originalidad, por la correcta interpretación de los actores. En ella hay escenas realmente emocionantes, carentes de acción, pero con unos buenos diálogos.

Quizá el mejor momento de la película es aquel en el que Sean y Will se sientan en un banco a contemplar el lago, cuando en realidad lo que están contemplando es lo que ambos esconden en su interior.

Lo único que no me resulta acorde al resto de la película es el final de la historia, que nos lleva de nuevo a un final típico del cine americano, ese final al que siempre nos conducen cuando no saben como finalizar una historia, y ésta era una buena historia.

http://www.labutaca.net/films/colabora/elindoma.htm

http://www.youtube.com/watch?v=V3qomma7TKc

Trailer de la Pelicula

Para Ver la Pelicula Online solo tiene que hacer click Aqui

Categorías:Uncategorized

Algoritmo de Euclides

Un Video Muy Util Acerca Sobre El Algotritmo de Euclides,  explicado paso a paso.

Categorías:Uncategorized

Teoria Elemental de Los Numeros.

NUMEROS ENTEROS
La Teoría de Números es la parte de la Matemática que trata de los números enteros y sus propiedades. Estudia la
divisibilidad y la congruencia de números enteros, los números primos y su distribución, las operaciones algebraicas
entre ellos y las soluciones enteras de ecuaciones diofánticas. Se designará a los conjuntos de números naturales y
enteros por N y Z respectivamente.
N = { 1, 2, 3, 4, 5, … }
Z = { …, -4, -3, -2, -1, 0, 1, 2, 3, 4, … }
El número 0 no es un número natural. El conjunto de los números enteros no negativos se designa por N U {0}. Uno
de los principios más importantes en la Teoría de Números es:
· Principio de la buena ordenación: todo subconjunto no vacío de números enteros no negativos tiene un primer
elemento, es decir, tiene un elemento que es menor que todos los demás.
Operaciones con números enteros
Sean a y b dos números enteros. A partir de las operaciones suma (a + b) y producto (a · b), es fácil definir las
siguientes operaciones:
· Diferencia (d = a – b): otro entero que satisfaga la igualdad a = b + d.
· Divide a (a | b): si a # 0 y b = a · q, diremos que a divide a b, a es un divisor de b, a es un factor de b, o que b
es un múltiplo de a.
· Mayor que (b > a): si existe un número natural n tal que b = a + n.
Propiedades de los números enteros
Sean a, b, c, x e y números enteros:
· a · 0 = 0
· a · (-b) = -a · b
· Si a # 0 y a · b = a · b, entonces b = c
· Si a # 0 y a | b, entonces a | b · x
· Sean a # 0 y b # 0, si a | b y b | c, entonces a | c
· Sea a # 0, si a | b y a | c, entonces a | (b · x + c · y)
· Sean a y b positivos, si a | b, entonces a <= b
· Sean a # 0 y b # 0, si a | b y b | a, entonces a = b o a = -b
Valor absoluto
Llamaremos valor absoluto a la aplicación | | : Z -> Z, tal que todo número entero tiene imagen mediante | | y esta
imagen es única. Queda definida por:
· Si n >= 0, entonces | n | = n
· Si n < 0, entonces | n | = -n

Propiedades del valor absoluto

· | n | pertenece a N U {0}
· | n | = 0 si y sólo si n = 0
· | a · b | = | a | · | b |
· | a + b | <= | a | + | b |
· Si a # 0, b # 0 y a | b, entonces | a | <= | b |
Algoritmo de la División
Sean a entero y b natural. Entonces existen números enteros q y r tales que:
a = b · q + r
con 0 <= r < | b |. Además q y r son únicos. A los números a, b, q y r se les llama respectivamente dividendo,
divisor, cociente y resto.
Módulo
Sean a y b números enteros con b # 0. Sea a = b · q + r donde 0 <= r < | b |. Definimos el operador módulo
(MOD) por:
a MOD b = r
Propiedades del operador MOD
Sean a, b, c, d y m números enteros con m # 0. Si a MOD m = c MOD m y b MOD m = d MOD m,
entonces:
· (a + b) MOD m = (c + d) MOD m
· (a · b) MOD m = (c · d) MOD m
Máximo común divisor
Sean a y b enteros. Un entero d # 0 es un divisor común de a y b si d | a y d | b. Un divisor común de a y b se llama
máximo común divisor de a y b si d > 0 y cada común divisor de a y b divide también a d. Se designa por:
m.c.d.(a, b) = d
Algoritmo de Euclides
El Algoritmo de Euclides se basa en sucesivas divisiones de dos números hasta obtener su máximo común divisor. Es
decir, si m.c.d.(a, b) = d y a = b · q + r, entonces tendremos:
d = rn-1 = m.c.d.(rn-2, rn-1) = m.c.d.(rn-3, rn-2) = … = m.c.d.(b, r1) = m.c.d.(a, b)
Si hacemos la divisiones sucesivas partiendo del Algoritmo de la División original:
· a = b · q1 + r1
· b = r1 · q2 + r2
· r1 = r2 · q3 + r3
· …
· rn-4 = rn-3 · qn-2 + rn-2

· rn-3 = rn-2 · qn-1 + rn-1
· rn-2 = rn-1 · qn + 0
Cálculo del máximo común divisor de dos números mediante el Algoritmo de Euclides de la división
Se procede con la división de tal forma que cumpla a = b · q + r donde q = a DIV b y r = a MOD b. A
continuación, si el resto es distinto de cero, se toma en la siguiente división: a = b y b = r, es decir, el divisor y el
resto de la división anterior. Cuando se llegue a una expresión con el resto igual a cero, el término b será el máximo
común divisor.
· m.c.d.(1312, 800) = d
· 1312 = 800 . 1 + 512
· 800 = 512 . 1 + 288
· 512 = 288 . 1 + 224
· 288 = 224 . 1 + 64
· 224 = 64 . 3 + 32
· 64 = 32 . 2 + 0
· d = 32

NUMEROS PRIMOS

Dado un número entero p > 1, diremos que p es un número primo si 1 y p son los únicos divisores positivos de p. Un
entero a > 1 que no es primo le denominaremos número compuesto. Dos números, a y b, son primos entre sí, si se
tiene que m.c.d.(a, b) = 1.
Lema de Euclides
Sean a, b y c números enteros. Supongamos que a y c son primos entre sí y que c | a · b. Entonces c | b.
Teorema Fundamental de la Aritmética
Sea n un número mayor que 1. Entonces existen números primos p1, … , pr tales que:
n = p1 · p2 · … · pr
donde p1 <= p2 <= … <= pr.
Teoremas
· Sea p un entero mayor que 1 y primo. Para cualquier a y b enteros, si p | a · b entonces p | a o p | b.
· El número de primos es infinito.
· Si pn es el n-ésimo número primo entonces pn <= 2^(2^n-1).
· Sea a un entero mayor que 1, entonces si para todo número primo p menor o igual que la raíz de a, p no divide al
número a, se verifica que a es primo.
Comprobar que un número es primo utilizando la criba de Erastóstenes
La criba de Erastóstenes dice que un número es primo si no es divisible por otro primo menor que la raíz cuadrada
entera del primero. Primero se desarrolla la criba y a continuación se divide el número por cada uno de los primos
contenidos en la criba.

· n = 811
· p < Raíz( 811 ) = 29
· Criba: 2, 3, 5, 7, 11, 13, 17, 19, 23 = i
· División: 29 MOD i # 0
· 811 sí es primo
Mínimo común múltiplo
Sean a y b dos números enteros. Llamaremos mínimo común múltiplo de a y b al menor entero positivo que sea
múltiplo de ambos. Lo designaremos por m.c.m.(a, b).
· Sean a y b enteros no nulos, entonces | a · b | = [ m.c.d.(a, b) ] · [ m.c.m.(a, b) ]
EL PRINCIPIO DE INDUCCION
En las Matemáticas aparecen muchos problemas que tienen la siguiente forma general:
· Sea P(n) una determinada propiedad acerca de un número natural n.
· Se trata de probar que P(n) es verdadero para todo n que sea natural.
Teorema del Principio de Inducción
Sea S un conjunto de números naturales que satisface las dos condiciones siguientes:
· El número 1 pertenece a S.
· Para cada número k >= 1, si k pertenece a S entonces k + 1 también pertenece a S.
Entonces el conjunto S es igual a N.
Pasos a seguir
· Definir el conjunto S = { n pertenecientes a N tales que P(n) es verdadera }.
· Probar que 1 pertenece a S.
· Suponer que k pertenece a S para k >= 1 arbitrario.
· Demostrar entonces que k + 1 pertenece a S.
Principio Fuerte de Inducción
Sea S un conjunto de enteros positivos tales que:
· 1 pertenece a S.
· Para cada entero n > 1, si k pertenece a S para todo entero k tal que 1 <= k < n entonces n pertenece a S.
Entonces S = N.
Demostrar una propiedad por el Principio de Inducción
Sea S el conjunto de los valores. Según dicho principio, la propiedad se debe cumplir para el elemento 1 y para
cualquier elemento k + 1 dado un k. Se presentan dos expresiones separadas con el signo igual, donde se les
añade un término k + 1 a ambas y se resuelve por la segunda expresión.

Para todo n natural:
· 1^2 + 2^2 + … + n^2 = n · (n + 1) · (2n + 1) / 6
Primera propiedad: P(1) pertenece a S
· 1^2 = 1 · (1 + 1) · (2 · 1 + 1) / 6 = 1 · 2 · 3 /6 = 6 / 6 = 1
Segunda propiedad: P(k) y P(k + 1) pertenecen a S
· 1^2 + 2^2 + … + k^2 + (k + 1)^2 = k · (k + 1) · (2k + 1) / 6 + (k + 1)^2 = k · (k + 1) · (2k + 1) +
6 · (k + 1)^2 / 6 = (k + 1) · (2k^2 + k + 6k + 6) / 6 = (k + 1) · (k + 2) · (2k + 3) / 6
Por lo tanto, se cumple la propiedad para todo natural
ECUACIONES DIOFANTICAS

Ecuaciones lineales de dos variables enteras
Sean a, b y n números enteros. La ecuación lineal a · x + b · y = n tiene solución entera x0 e y0 si y sólo si d =
m.c.d.(a, b) divide a n.
· Dada la ecuación a · x + b · y = n se calcula el m.c.d.(a, b) llegando a escribir d = a · q1 + b · q2 (a = b ·
q1 + r1 y b = r1 · q2 + r2), siendo una solución x0 = n · q1 / d e y0 = n · q2 / d.
· Supongamos que a, b y n son enteros no nulos y d = m.c.d.(a, b) divide a n. Entonces la solución general de la
ecuación a · x + b · y = n tiene la forma: {x0 + t · b / d , y0 – t · a / d} donde t es cualquier entero.
Calcular los valores de dos incógnitas para que se cumpla la expresión d = ax + by
Se calcula el máximo común divisor de los coeficientes por el Algoritmo de Euclides de la división y se sitúan los restos
desde el último hasta el primero que sean distintos de cero:
r = a – b · q
Se comienza desde la primera expresión y se sustituye b por su equivalente en la ecuación siguiente. A continuación
pasamos a la siguiente ecuación y sustituimos a, y así sucesivamente. Cuando se llegue al final debe quedar:
d = m.c.d.(a, b)= ax + by
· d = 322x + 406y
· m.c.d.(322, 406)
· 322 = 406 · 0 + 322
· 406 = 322 · 1 + 84
· 322 = 84 · 3 + 70
· 84 = 70 · 1 + 14
· 70 = 14 · 5 + 0
· 1º Resto: 14 = 84 – 1 · 70
· 2º Resto: 70 = 322 – 3 · 84
· 3º Resto: 84 =406 – 1 · 322
· 4º Resto: 322 = 322 – 0 · 406
· Se toma el 1º Resto: 14 =84 – 1 · 70
· Se sustituye 70: 14 = 84 – 1 · (322 – 3 · 84) = -322 + 4 · 84
· Se sustituye 84: 14 = -322 + 4 · (406 – 1 · 322) = -5 · 322 + 406 · 4
· Se sustituye 322: 14 = -5 · (322 – 0 · 406) + 4 · 406 = -5 · 322 + 4 · 406
· x = -5 || y = 4

Hallar todas las soluciones de ecuaciones diofánticas del tipo ax + by = n
Primero se calcula el máximo común divisor de a y b, al que se le llamará d. Después se comprueba que d divide a n,
para saber si la ecuación tiene solución. Si es así, existen a’ y b’ tales que:
d = a’ · a + b’ · b
A continuación se averiguan a’ y b’ tomando la primera ecuación de los restos obtenidos del máximo común divisor de
a y b, y sustituyendo los b y los a:
r = a – b · q
Una solución de la ecuación sería:
x0 = n · a’ / d
y0 = n · b’ / d
Y la solución general del sistema sería:
{x0 + b · t / d , y0 – a · t / d}
para todo t que sea entero.
· 28x + 36y = 44
· 28 = 36 · 0 + 28 => 3º Resto: 28 = 28 – 0 · 36
· 36 = 28 · 1 + 8 => 2º Resto: 8 = 36 – 1 · 28
· 28 = 8 · 3 + 4 => 1º Resto: 4 = 28 – 3 · 8
· 8 = 4 · 2 + 0 => Ultima división
· m.c.d.(28, 36) = 4
· Como 4 divide a 44 (44 / 4 = 11), la ecuación tiene solución
· 28a’ + 36b’ = 4
· Se toma el 1º Resto: 4 = 28 – 3 · 8
· Se sustituye 8: 4 = 28 – 3 · (36 – 1 · 28) = 4 · 28 + (-3) · 36
· Se sustituye 28: 4 = 4 · (28 – 0 · 36) + (-3) · 36 = 4 · 28 + (-3) · 36
· a’ = 4 | b’ = -3
· Una solución sería: x0 = 44 · 4 / 4 = 44 , y0 = 44 · (-3) / 4 = -33
· Y la solución general: {44 + 36t/4, -33 – 28t/4 } = { 44 + 9t, -33 – 7t}
Ecuaciones cuadráticas
La ecuación diofántica x^2 – y^2 = n con n > 0, tiene solución si y sólo si n se puede factorizar como producto de
dos números de la misma paridad, es decir, ambos pares o ambos impares. Si existen, las soluciones de esta ecuación
tienen la forma:
x = a + b / 2 || y = a – b / 2
donde x + y = a y x – y = b.
Hallar todas las soluciones de ecuaciones de la forma x^2 – y^2 = n
La ecuación tiene solución si n se puede factorizar como producto de dos números de la misma paridad. Las soluciones tendrán la forma:
x = a + b / 2
y = a – b / 2
donde n = a · b , a = x + y y b = x – y. Primero se averiguan todos los factores primos y se divide el número entre
cada uno de ellos. Se toman aquellas parejas con la misma paridad. Se aplican las fórmulas anteriores y se obtienen
todas las soluciones, para a >= b.
· x^2 – y^2 = 120
· 120 = 2 · 2 · 2 · 3 · 5 = 2^3 · 3 · 5
· 120 = 60 · 2 = 30 · 4 = 20 · 6 = 12 · 10
· Se toman todas las parejas en las que a >= b
a b x = a + b / 2 y = a – b / 2
======================
60 2 31 29
30 4 17 13
20 6 13 7
12 10 11 1
Las soluciones serán: { 31, 29 } , { 17, 13 } , { 13, 7 } y { 11, 1 }.
Algoritmo de factorización de Fermat

· Determinar el mínimo entero positivo q que satisfaga que q^2 >= n.
· Estudiar si alguno de los números q^2 – n, (q + 1)^2 – n, (q + 2)^2 – n, … es un cuadrado.
· Si para alguno de estos números m, m^2 – n es un cuadrado, entonces n será primo.
Estudiar si un número es compuesto mediante el Algoritmo de factorización de Fermat
Un número es compuesto si es producto de dos números impares. Primero se hace la raíz cuadrada entera y se toma el
valor entero mayor q y un intervalo:
[q^2 ... n + 1 / 2)
Después se van haciendo operaciones q^2 - n y se va incrementando q hasta obtener un número cuadrado. Entonces
se sustituyen el q resultante y el número cuadrado en x^2 e y^2:
x^2 = q || y^2 = número cuadrado || n = x^2 - y^2
Y a continuación, se despejan a y b:
a = x + y || b = x - y || n = a · b
· n = 22733
· q >= Raíz( 22733 ) = 151
· El intervalo será: [151^2...22733 + 1 / 2) = [151^2...11367) = 151 <= q < 11367
· 151^2 - 22733 = 22801 - 22733 = 68 no es cuadrado
· 152^2 - 22733 = 23104 - 22733 = 371 no es cuadrado
· 153^2 - 22733 = 23409 - 22733 = 676 = 26^2 sí es cuadrado
· x = 153 || y = 26

· a = 153 + 26 = 179
· b = 153 - 26 = 127
· 22733 = 179 · 127 sí es compuesto
Ecuaciones pitagóricas

Las soluciones de la ecuación pitagórica x^2 + y^2 = z^2 que satisfacen las condiciones m.c.d.(x, y, z) = 1, 2 | x
y x, y, z > 0, vienen dadas por las fórmulas x = 2 · s · t, y = s^2 - t^2, z = s^2 + t^2, para naturales s, t con s > t
tales que m.c.d.(s, t) = 1, y s y t tienen distinta paridad.
CONGRUENCIAS

Sea m > 0. Dados a y b enteros se dice que a y b son congruentes módulo m si a - b es divisible por m.
Simbólicamente esta relación se escribe:
a == b mód (m) si y sólo si m | (a - b)
Fijado m > 0, cada número entero a es congruente con uno de los enteros 0, 1, 2, ... , m - 1. Entonces a == r mód
(m), el número r se denomina menor resíduo no negativo de a módulo m, que no es otra cosa que a MOD m = r.
Teoremas
Sean a, b, c, d, h y m enteros con h # 0 y m > 0 entonces:
· a == b mód (m) si y sólo si al dividir a y b por m el resto obtenido es el mismo
· a == a mód (m)
· Si a == b mód (m) entonces b == a mód (m)
· Si a == b mód (m) y b == c mód (m) entonces a == c mód (m)
· Si a == b mód (m) y c == d mód (m) entonces a + c == b + d mód (m) y a · c == b · d mód (m)
· Si a == b mód (m) entonces h · a == h · b mód (m)
· Si h | a, h | b, m.c.d.(h, m) = 1 y a == b mód (m) entonces a / h == b / h mód (m)
Ecuación de la forma ax == b mód (m)
La ecuación ax == b mód (m) tiene solución si y sólo si d divide a b donde d es el m.c.d.(a, m). Además el
número de soluciones no congruentes módulo m es exactamente d.
Resolver una congruencia del tipo ax == b mód (m)
Una congruencia ax == b mód (m) es equivalente a una ecuación diofántica ax + mk = b. Se calcula el máximo
común divisor de a y m, se le llama d y se comprueba que d divida a b. Por el Algoritmo de Euclides de la división se
halla a' en:
a' = b - m / a
y se sustituye en:
x0 = n · a' / d
x = x0 - a · t / d
Si x0 es negativo se halla una solución t hasta que x sea positivo.

· 2x == 6 mód (10)
· Ecuación diofántica: 2x + 10k = 6
· m.c.d.(2, 10) = 2
· Se comprueba que 2 divide a 6
· a' = 6 - 10 /2 = -4
· x0 = 6 · (-4) / 2 = -12
· x = -12 - 10t / 2 = -12 - 5t
· Una solución positiva es t = -3: x = -12 - 5 · (-3) = -12 + 15 = 3
· La solución general es: x = 3 + 5k
Teorema chino del resto

El sistema de congruencias aix == bi mód (mi), i = 1, 2, ..., k donde m.c.d.(mi, mj) = 1 si i # j y m.c.d.(ai,
mi) = 1 para 1 <= i <= k, tiene una única solución x0 módulo m1m2...mk y las demás soluciones son de la forma x
= x0 + zm1m2...mk, donde z es un entero.
Resolver un sistema de congruencias y presentar la ecuación general
Se comprueba que los módulos sean primos, es decir, que el máximo común divisor entre ellos sea uno. Si se cumple,
la ecuación tendrá la forma:
ax = bi mód (mi)
donde las soluciones xi serán igual a bi. Se hace el producto de los módulos y se divide entre cada uno de ellos:
producto de mi = m, donde ti = m / mi
Tendremos un nuevo sistema de ecuaciones con la forma general:
tiyi = 1 mód (mi)
Se averiguan las respectivas yi y se procede a averiguar el valor buscado:
x0 = suma de i [ 1 ... n ] en xi · ti · yi
La ecuación general será:
x = x0 + mk
· x = 2 mód (5)
· 2x = 1 mód (7)
· 3x = 4 mód (11)
· m.c.d.(5, 7) = 1 || m.c.d.(7, 11) = 1 || m.c.d.(5, 11) = 1
· x1 = 2 || x2 = 1 || x3 = 4 || m = 5 · 7 · 11 = 385
77y1 = 1 mód (5) 55y2 = 1 mód (7) 35y3 = 1 mód (11)
-75y1 = 0 mód (5) -49y2 = 0 mód (7) -33y3 = 0 mód (11)
======================================
2y1 = 1 mód (5) 6y2 = 1 mód (7) 2y3 = 1 mód (11)
y1 = 3 || y2 = 6 || y3 = 6

El valor buscado es: x0 = 2 · 77 · 3 + 1 · 55 · 6 + 4 · 35 · 6 = 462 + 330 + 840 = 1632
La ecuación general será: x = 1632 + 385k
Pequeño Teorema de Fermat
Si p es un número primo que no divide al número a entonces a^p-1 == 1 mód (p).
Hallar el resto de dividir una potencia entre un número por el pequeño Teorema de Fermat
Se trata de hallar x en la siguiente expresión:
a^n = x mód (p)
Se comprueba que p sea primo y que no divida a la base de la potencia. Si se cumple, se aplica el teorema: a^p-1 = 1
mód (p). Se desglosa el exponente de la potencia como una división entre p – 1 y se toma el resto como r1.
Quedaría:
n = (p – 1) · q + r1 || a^n = a^(p-1) · q · a^r1
Se halla el resto de la base sin exponente y se aplica en la siguiente fórmula a r2:
a = y mód (p) || a^p-1 = y^p-1 mód (p) = r2 mód (p)
Por último, sabiendo que x = r1 + r2, se aplica:
a^n = x mód (p)
· x = 113^34291 MOD 7
· 113^34291 = x mód (7)
· Se comprueba que 7 es primo y no divide a 113
· Como (p – 1) = 6: 34291 = 6 · 5715 + 1
· 113^34291 = 113^6 . 5715 + 113^1
· 113 = 1 mód (7) || 113^6 = 1^6 mód (7) = 1 mód (7)
· 113^34291 = (1 + 1) mód (7) = 2 mód (7)
· x = 2
Teorema de Wilson

Si p es un número primo entonces (p – 1)! = -1 mód (p).
SISTEMAS DE NUMERACION

En la vida diaria el sistema de numeración empleado para escribir números naturales es el decimal. Las unidades se
agrupan de 10 en 10 para unidades de segundo orden, que se llaman decenas. Estas, a su vez, se agrupan de 10 en 10
para formar unidades de tercer orden o centenas y así sucesivamente. Sea b >= 2 un número natural (llamado base).
Entonces todo número natural n puede escribirse de manera única en base b de la forma:
n = ak · b^k + ak-1 · b^k-1 + … + a1 · b + a0
De ahora en adelante cuando tengamos un número en base b, escribimos simplemente:

n = ( ak ak-1 … a1 a0 ) · b
Cuando la base es mayor que 10, se necesitan nuevos símbolos. Usualmente se utilizan las letras del alfabeto. Así A =
10, B = 11, etc.
Criterio de divisibilidad por k

Un número n es divisible por k si y sólo si:
Suma de i [ 0 ... t ] en ai . ri = 0 mód (k)
siendo t el último dígito del número n.
Resolver una ecuación mediante un cambio de base y efectuar la suma con otro número de la misma base
Comprobar si la incógnita está en el número o en la base. Si está en el número, se convierte el número contrario en
decimal y se efectúa la división entre la base que sí se conoce. Si está en la base, se convierte el número contrario en
decimal y se desglosa el número contrario en una ecuación de grado igual al número de dígitos menos uno. Se
resuelve la ecuación y se toma el valor positivo. En general, para sumar dos números de la misma base, primero se
convierten a decimal, se suman y se vuelven a dividir por la base anterior.
· 124¬5 = x¬9 || 132¬x = 330¬5 || 124¬5 + 330¬5
· 124¬5 = 4 · 5^0 + 2 · 5^1 + 1 · 5^2 = 4 + 10 + 25 = 39¬10
· 39 = 9 · 4 + 3 || 4 = 9 · 0 + 4 || 4 · 9^1 + 3 · 9^0 = 43¬9 || x = 43
· 330¬5 = 0 · 5^0 + 3 · 5^1 + 3 · 5^2 = 0 + 15 + 75 = 90¬10
· 132¬x = 90¬10 || x^2 + 3x + 2 = 90 || x = 8 , x = -11 || 132¬8 =330¬5
· x = 8
· 124¬5 = 39¬10 || 330¬5 = 90¬10 || 39 + 90 = 129¬10
· 129 = 5 · 25 + 4 || 25 = 5 · 5 + 0 || 5 = 5 · 1 + 0 || 1 = 5 · 0 + 1
· 1 · 5^3 + 0 · 5^2 + 0 · 5^1 + 4 · 5^0 = 1004¬5 || 129¬10 = 1004¬5

Texto Tomado de : http://wainu.ii.uned.es:8081/WAINU/iti_gestion/primero/MaDi/apuntes/tema4a.pdf

Categorías:Uncategorized

Bibliografia Recomendada Para Las Matematicas Discretas.

Libros básicos de referencia

  • Rosen, K.: “Matemática Discreta y sus Aplicaciones”. 5ª Ed. McGraw-Hill. 2004.
  • Biggs, N. L. : “Matemática Discreta”. Vicens Vives. 1994

Libros de consulta

  • Abellanas,  M. y Lodares, D. : “Análisis de Algoritmos y Teoría de grafos”. Ed. Ra-ma. 1990.
  • Anderson, I. : “Introducción a la combinatoria”. Ed. Vicens Vives, 1993
  • Anderson, I. : “A First Course in Discrete Mathematics”. Ed. Springer, 2001.
  • Barnett, S. : “Discrete Mathematics”. Ed. Addison-Wesley, 1998.
  • COMAP : “Las matemáticas en la vida cotidiana “.Addison-Wesley/Universidad Autónoma de Madrid , 1998.
  • García Merayo, F. : “Matemática Discreta”. Ed. Paraninfo, 2001.
  • Goodaire,  E. y Parmenter, M. : “Discrete Mathematics with Graph Theory”. Ed. Prentice Hall. 1998.
  • Grimaldi, R. P. : “Matemática Discreta y combinatoria”. Ed. Addison-Wesley Iberoamericana. 1989.
  • Hernández, G. : “Grafos. Teoría y algoritmos”. Facultad de Informática. UPM. 2003.
  • Jonhsonbaugh, R. : “Matemáticas Discretas”. Ed. Prentice Hall,. 1999.
  • Matousek, J. y Nesetril, J.: “Invitación a la Matemática Discreta”. Editorial: Reverte 2008.

Libros de problemas

  • Bujalance, E. ; Bujalance, J.A. ; Costa,  A.F. y MartínezE. “Problemas de Matemática Discreta.”. Ed. Sanz y Torres, 1993.
  • García Merayo, F. ; Hernández,  G. y Nevot, A. : “Problemas resueltos de Matemática Discreta”. Ed. Thomson-Paraninfo, 2003
  • García, C. ; López, J. y Puigjaner, D. : “Matemática Discreta. Problemas y ejercicios resueltos”. Ed. Prentice Hall, 2002.
  • Lipschutz, S. : “Matemática Discreta. Teoría y 600 problemas resueltos”. Serie Schaum. Ed. Mc-Graw-Hill. 1990.

http://www.dma.fi.upm.es/docencia/primerciclo/matdiscreta/

Categorías:Uncategorized

Los Grafos y Las Redes Sociales.

A ustedes no les ha dado curiosidad esto ?

Lo Vemos Todos los dias cuando nos conectamos al Facebook, pero nosotros jamas caemos en cuenta que ese loguito tiene mucha relacion con el area que nosotros manejamos, y vaya que si lo tiene, entonces retrocedamos un poco y volvamos a retomar acerca de lo que significa un Grafo.

Un grafo es un conjunto de vértices y aristas o arcos. Cada arista es una línea o arco que unen dos vértices del grafo o un vértice a si mismo.

Ahora muchos se preguntaran, que relacion hay entre una cosa y la otra ? , para alla vamos, entonces.

Para Comenzar se tiene:

  • La presencia, la gente que participa en un determinado evento.
  • La identidad o filiación de los participantes.
  • La interacción entre los participantes.

    La comunicación que tiene lugar entre ellos.

Tratandose de Una Red Social nos enfocaremos mas en el sentido en el cual la interaccion entre participantes es ideal dado a:

  • Todos pertenecemos a una o más de ellas.
  • Las redes sociales son los vehículos de la influencia y el poder en las organizaciones.
  • Las propiedades inherentes a las redes determinan sus posibilidades. (Hay cosas que se pueden hacer en una red y otras que no)
  • El advenimiento de Internet, la red por excelencia, ha propiciado la aparición de miles de redes, con muchos miembros cada una.

existe una teoría matemática, la teoría de grafos, que permite estudiar el comportamiento de las redes y conocer sus propiedades.

Un ejemplo de dicha teoria con grafos.

Relaciones de capital en Alemania en 1996

Como se pueden dar cuenta hay una interrelacion entre todos ellos, segun los tipos de industria que hayan, bien sean financieros o industriales.

<p id="Construir un grafo de una red social y visualizarlo puede ser un factor de decisión importante. En todas las redes hay nodos que acumulan enlaces mientras que otros apenas están ligados a los demás. Obviamente los nodos preponderantes, con más enlaces, son también los nodos más influyentes. No siempre es fácil ni, sobre todo, rápido detectarlos.

<p id="Para ello es necesario disponer de la información sobre

  • qué nodos existen
  • cómo están conectados entre si.

<p id="Con ello podemos construir el grafo, representarlo y estudiar los indicadores que nos permitan valorar la estructura de la red y conocer qué nodos tiene un papel decisivo y cuáles no.

Se Ha Citado Muchas Partes de : http://www.infovis.net/printMag.php?num=136&lang=1

Categorías:Uncategorized

El Cine Y Las Matematicas Discretas

Por Increible que Parezca si hay Cine Relacionado a Nuestra Area, y queremos hacer muestra de ello con este Film, que muestra increibles realidades sobretodo en los aspectos economicos de nuestra sociedad.

  1. Las matemáticas son el lenguaje de la naturaleza
  2. Todo puede representarse y entenderse con números
  3. Al graficar cualquier sistema surgen patrónes

Por lo tanto, hay patrones en toda la naturaleza.

En este sitio web, en donde se habla bastante del Cine y las Matematicas , se toma una opinion bastante interesante acerca de este tema:

Se trata de que el alumno razone sobre el papel que juegan la repetición de patrones en el establecimiento de modelos matemáticos y la relación con el concepto de un universo causal.

Y Como la Idea es que la Gente la Pueda ver para tomar sus propias decisiones aqui se la enviamos completica, solo es que haga Click Aqui para que la pueda ver completica


Categorías:Uncategorized

Algoritmos para Grafos.

Dado a la Complejidad de los Algoritmos hemos decidido Simplificarlo Mediante Videos, cortesia del Infaltable Youtube, la utilidad es Impresionante, ya que explica paso a paso la funcion del recorrido de los Grafos

Dikjstra

Prim

Bellman-Kabala

Floyd Parte 1

Floyd Parte 2

Fleury


Kruskal

Categorías:Uncategorized

Video Tutorial Sobre La Teoria de Grafos

Otro Video Cortesia de las Video Conferencias y YouTube, bastante comprensible, bastante Util

Categorías:Uncategorized

Teoria de Grafos

Conceptos fundamentales

Un grafo G es un par G = (V,E), donde V es un conjunto finito (vértices,
nodos) y E es un multiconjunto de pares no ordenados de vértices, denotados
por {x, y}, que se denominan lados, aristas, etc. En este caso decimos que x
y y son extremos de {x, y}. Denotamos V (G) por el conjunto de vértices del
grafo G y por E(G) el conjunto de lados del grafo G. Además º(G) y “(G)
denotan el número de vértices y el número de aristas de G respectivamente.
Puesto que E es un multiconjunto es posible que existen pares repetidos,
en este caso G tiene lados múltiples. También es posible que algún par no
ordenado de E tenga el mismo vértice repetido, en este caso decimos que
el lado es un lazo (loop) o bucle . Cuando existen lados múltiples y/o lazos
decimos que G es un multigrafo. Si no hay lados múltiples ni lazos decimos
que es un grafo simple. Un digrafo G es un par G = (V,E) donde V es un
conjunto de vértices y E es un multiconjunto de pares ordenados. Los lados
se denotan por pares ordenados, (u, v) denota el lado dirigido que tiene como
vértice inicial a u y como vértice terminal a v.
A continuación damos unas definiciones que provienen del libro de Matemá-
ticas Discreta y sus aplicaciones de Rosen [2]. Se deja al lector comparar las
diferentes definiciones.
Definición 1

Un grafo simple G(V,E) consta de V , un conjunto no vacío
de vértices, y de E, un conjunto de pares no ordenados de elementos
distintos de V . A esos pares se les llama aristas o lados.

Definición 2

Un multigrafo G(V,E) consta de un conjunto V de vertices,
un conjunto E de aristas y una función f de E en {{u, v}|u, v ∈ V, u 6= v}. Se
dice que las aristas e1, e2 son aristas múltiples o paralelas si f(e1) = f(e2).

Los multigrafos definidos no admiten bucles o lazos (aristas que conectan
un vértice consigo mismo). Usamos en este caso, pseudografos que son más
generales que los multigrafos.
Definición 3

Un pseudografo G(V,E) consta de un conjunto V de vertices,
un conjunto E de aristas y una función f de E en {{u, v}|u, v ∈ V }. Se
dice que una arista e es un bucle o lazo si f(e) = {u, u} = {u} para algún
u ∈ V .
La diferencia entre grafo y digrafo es que el último tiene los lados dirigidos
y se entiende como un grafo dirigido.
Definición 4

Un grafo dirigido o digrafo G = (V,E) consta de un conjunto
V de vertices, un conjunto E de aristas, que son pares ordenados de
elementos de V .
Definimos los multigrafos dirigidos de la siguiente manera

Definición 5

Un multigrafo dirigido G(V,E) consta de un conjunto V de
vertices, un conjunto E de aristas y una función f de E en {(u, v)|u, v ∈ V }.
Se dice que las aristas e1, e2 son aristas múltiples o paralelas si f(e1) =
f(e2).

Adyacencia de Vértices, Incidencia de Aristas y Grado de los Vértices
Dos vertices u, v de un grafo G = (V,E) se dicen adyacentes si {u, v} ∈ E, asimismo dos aristas son adyacentes si tienen un mismo vértice como
extremo; análogamente si e = {u, v} decimos que el lado e es incidente a
los vértices u y v. El grado de un vértice es el número de lados incidentes a
él. El grado de un vértice u se denota gr(u). Denotamos con ±(G) y ¢(G) el
mínimo y el máximo grado de los vértices de G respectivamente.

Teorema 1

Pruebe que en un grafo la suma de los grados de los vértices es
el doble del número de lados. Es decir, si G = (V,E) es el grafo, entonces
X
u∈V
gr(u) = 2|E|

Teorema 2

Si G = (V,E) es un digrafo, entonces
X
u∈V
gr−(u) =
X
u∈V
gr+(u) = |E|

Teorema 3

Pruebe que el número de vértices de grado impar es par.

Representaciones de los grafos
Sea G = (V,E) un grafo con º vértices y ” aristas, entonces le corresponde
una matrizº × ” denominada la matriz de incidencia de G. Si denotamos
los vértices de G por v1, v2, . . . , vº y las aristas por e1, e2, . . . , e”. Entonces la
matriz de incidencia de G es la matriz M(G) = [mij ] donde mij es el número
de veces que la arista ej incide en el vértice vi; los valores son 0,1 ó 2 (2 en
el caso que la arista sea un lazo).
Otra matriz asociada a G es la matriz de adyacencia, esta es una matriz
º ׺ A(G)[aij ], en donde aij es el número de aristas que van de vi hasta vj .
A continuación damos un ejemplo de un grafo con su correspondiente matriz
de incidencia y matriz de adyacencia.

Caminos y Ciclos
En algunos textos, e.g Brualdi [1] se distingue entre cadenas (chains) y
caminos (path), usando el primer término para grafos y el segundo para
digrafos. Una sucesión alternada de vértices y lados u1, e1, u2, e2, . . . , ek, uk+1
tal que ei = [ui, ui+1] se denomina cadena en un grafo y camino en un digrafo.
Los caminos deben realizarse de acuerdo a la dirección de los lados. Si no
existen lados multiples podemos denotar sin ambigüedad la cadena como
una sucesión de vértices (vértices consecutivos adyacentes). Una cadena es
cerrada si el vértice inicial y final es el mismo. La cadena cerrada es un ciclo
si todos los vértices (excepto los extremos) son distintos. El camino cerrado
es un circuito si todos los vértices (excepto los extremos) son distintos.

Teorema 4

Si en un grafo G todos los vértices tiene grado mayor a 1, pruebe
que existe un ciclo.

Grafos Etiquetados y Ponderados
Aunque ya hemos usado los grafos etiquetados, damos una definición en
esta sección. Un grafo G es un grafo etiquetado si sus aristas y/o vértices
tienen asignado alguna identificación. En particular, G es un grafo ponderado
si a cada arista e de G se le asigna un número no negativo w(e)
denominado peso o longitud de e. El peso (o longitud de un camino en
un grafo ponderado G se define como la suma de los pesos de las aristas del
camino. Un importante problema en teoría de grafos es encontrar el camino
más corto (liviano), esto es, el camino con el peso (longitud) mínimo entre
dos vértices dados.

Grafos Etiquetados y Ponderados
Aunque ya hemos usado los grafos etiquetados, damos una definición en
esta sección. Un grafo G es un grafo etiquetado si sus aristas y/o vértices
tienen asignado alguna identificación. En particular, G es un grafo ponderado
si a cada arista e de G se le asigna un número no negativo w(e)
denominado peso o longitud de e. El peso (o longitud de un camino en
un grafo ponderado G se define como la suma de los pesos de las aristas del
camino. Un importante problema en teoría de grafos es encontrar el camino
más corto (liviano), esto es, el camino con el peso (longitud) mínimo entre
dos vértices dados.

Grafos Regulares
Un grafo G = (V,E) es regular de grado k o k-regular si cada vértice tiene
grado k; es decir, un grafo es regular si todos los vértices tienen el mismo
grado.

Isomorfismo de Grafos
Definición 6

Los grafos G1 = (V1,E1) y G2 = (V2,E2) son isomorfos si
existe una función biyectiva f de V1 en V2 con la propiedad de que, para cada
par de vértices u, v ∈ V1, u, v son adyacentes en G1 si y sólo si f(u), f(v)
son adyacentes en G2. Es decir {u, v} ∈ E1 ⇔ {f(u), f(v)} ∈ E2. Si G1 y
G2 son isomorfos lo denotamos G1 ∼= G2.
Si dos grafos G1 y G2 son isomorfos, tienen el mismo número de vértices, el
mismo número de aristas, el mismo número de vértices de cualquier grado,
el mismo número de ciclos de cualquier longitud, etc. Esto nos provee de
algunos criterios para determinar si dos grafos no son isomorfos.

Grafos complementarios
Dado un grafo simple G = (V,E) el grafo complementario denotado por Gc es el grafo simple que tiene los mismos vértices y el conjunto de aristas, son todas aquellas que le faltan a G para que sea completo. De manera más formal, si E = {{u, v}|u, v ∈ V, u 6= v} es el conjunto de todas las aristas posibles y Ec = E \ E denota el complemento respecto a E, entonces
Gc = (V,Ec).

Subgrafos
Sea G = (V,E) un grafo. Si H = (W, F) es un grafo tal que W ⊆ V y
F ⊆ E decimos que H es un subgrafo de G. Si F contiene todos los lados de
E que unen a los puntos de W en G se dice que H es un subgrafo completo
de G generado por W. Si W = V decimos que H es un subgrafo extendido
de G (spanning subgraph).

Grafos Bipartitos
Definición 8

Se dice que un grafo simple G = (V,E) es bipartito si el
conjunto de vértices V se puede dividir en dos conjuntos disjuntos V1, V2,
(V1 ∪ V2 = V, V1 ∩ V2 = ∅, de tal manera que toda arista e ∈ E conecta un
vértice de V1 con un vértice de V2.
Esto significa que el subgrafo completo generado por V1 es libre de lados;
asimismo el subgrafo completo generado por V2.

Conexidad
Un grafo (multigrafo, digrafo) G es conexo si existe una cadena (camino)
entre cualesquiera par de vértices.
H es una componente conexa de G si H es un subgrafo conexo com-
pleto maximal. Es decir no existe un subgrafo completo de G que contenga
propiamente a H y sea conexo.
Definimos en G una relación sobre los vértices de esta manera: u ∼= v si
u = v, o existe una cadena que los une.

Pruebe que ∼= es una relación de equivalencia.
Pruebe que cada clase de equivalencia es una componente conexa de G.
Denotamos el número de componentes conexas de G con !(G).
Sea G un grafo y v ∈ V (G) un vértice de G, se define G − v como el
subgrafo de G que se obtiene al borrar el vértice v del grafo G y todos los
lados incidentes a v.

Definición 9

Si G es un grafo simple no trivial, entonces v es un vértice
de corte si y sólo si !(G − v) > !(G).
Sea G un grafo y e ∈ E(G) un lado de G, se define G−e como el subgrafo
de G que se obtiene al borrar el lado e del grafo G. Así V (G) = V (G − e) y
E(G − e) = E(G) \ {e}.

Grafos Planares
Decimos que un grafo G es planar si se puede dibujar en el plano sin que
los lados se crucen fuera de sus extremos. Las regiones en una representación
de un grafo planar, están limitadas por los lados. Dos puntos se encuentran
en la misma región si existe una linea continua que los une sin cruzar ningún
lado o vértice. El grado de una región es el número de lados que son frontera
de dicha región; cuando un lado pertenece por completo a una región este
lado aporta 2 al grado de la región
Teorema 9 (Euler) Si G es un grafo planar conexo, entonces cualquier
representación planar de G tiene r = e−v+2 regiones donde e es el número
de lados y v el número de vértices.

Árboles
Un árbol T es un grafo en el cual cada par de vértices distintos esta unidos
por una única cadena simple.

Definición 12

Sea G un grafo, decimos que T es un árbol extendido (spanning
tree) de G si es un subgrafo extendido (spanning subgraph) que es un
árbol.

Coloración de Grafos
Tenemos un grafo G y un conjunto de colores C = {a, b, . . . }. Una co-
loración de G con los colores de C es una asignación a los vértices de G de
elementos de C (” colores”) de manera que los extremos de cada arista reci-
ban colores distintos. Formalmente, una coloración de G con colores de C es
una aplicación
° : V (G) → C
tal que si {v,w} ∈ E(G) entonces °(v) 6= °(w) Observación. En algunos
libros estas coloraciones se denominan coloraciones admisibles; aquí, por
comodidad, las denominamos coloraciones.
Definición 13

El número cromático de un grafo G, Â(G), es el número
mínimo de colores necesario para colorear G.
Algunas observaciones inmediatas sobre el número cromático son las siguien-
tes:
1. Para todo grafo G, Â(G) ≤ |V | , porque siempre podremos colorear
con |V | colores, asignando a cada vértice un color distinto. Ésta es,
obviamente, la forma menos efectiva de colorear.
2. Si el grafo contiene al menos una arista, necesitaremos dos colores como
mínimo; es decir, si |A| ≥ 1, entonces Â(G) ≥ 2.
3. Si G contiene a G′ como subgrafo, entonces
Â(G) ≥ Â(G′)
4. Si G tiene k componentes conexas, G1,G2, . . . ,Gk que tienen números
cromáticos Â(G1), Â(G2), . . . , Â(Gk) respectivamente, entonces
Â(G) = m´ax
1≤i≤k{Â(Gi)}
5. Si G y G′ son isomorfos, entonces Â(G) = Â(G′).

Relaciones con listas y particiones en bloques
Una coloración de un grafo G es equivalente a una lista con ciertas res-
tricciones. Supongamos que V (G) = {v1, v2, · · · , vn}, entonces una coloración
usando los k colores C = {a1, a2, . . . , ak} es una lista (n-upla) con repetición
(ai1 , ai2 , . . . , ain) tal que si vs y vt son adyacentes entonces ais 6= ait .
Dada una coloración ° : V (G) → C definimos la relación entre los vértices
de G de la siguiente manera: u ≡° v si °(u) = °(v), es decir, dos vértices están
relacionados si tienen el mismo color. Esta es una relación de equivalencia
(¡Verificarlo!). Esta relación induce una partición sobre el conjunto V (G)

cuyos bloques son las clases de equivalencia. Cada bloque está constituido
por vértices que tienen el mismo color. Es importante notar que los vértices
que están relacionados no son adyacentes; si dos vértices son adyacentes se
encuentran en bloques distintos.
Recíprocamente, si particionamos el conjunto de vértices de un grafo G
de tal manera que vértices adyacentes se encuentran en bloques distintos,
entonces esta partición induce una coloración de los vértices de G. Se colo-
rean los vértices del mismo bloque con un mismo color y bloques distintos
con colores distintos. Estas observaciones son útiles para resolver problemas.
Como ejemplo, recordemos los grafos bipartitos. El conjunto de vértices se
puede particionar en dos conjuntos V1(G) y V2(G) de tal manera que vérti-
ces adyacentes se encuentran en conjuntos distintos, así es posible usar dos
colores para colorear los vértices de dicho grafo. A los vértices de V1(G) se
les asigna un color y a los vértices de V2(G) se les asigna otro color, y resulta
una coloración de G.

Algoritmo austero para colorear
Damos un procedimiento para colorear los vértices de un grafo siguiendo
un orden impuesto a los vértices, usando la menor cantidad de colores posi-
bles. Supongamos que C = {c1, c2, . . . } es el conjunto de colores; procedemos
a describir el algoritmo que denominamos algoritmo austero1 y consta de
los siguientes pasos:
Paso inicial. Ordenamos los vértices del grafo. Es importante notar
que la eficiencia del algoritmo depende del orden que elijamos. Hacemos
una lista de los vértices del grafo
(v1, v2, . . . , vn)
Primer paso. Le asignamos el primer color c1 al vértice v1.
Segundo paso. Procedemos a asignar un color al vértice v2 así: si es
adyacente al vértice v1 le asignamos el siguiente color c2, en otro caso
le asignamos c1
k-ésimo paso. Para colorear el vértice vk buscamos todos los vértices
del conjunto {v1, v2, . . . , vk−1} que son adyacentes a vk y determinamos
los colores que han sido usados en sus coloraciones; luego usamos el
primero disponible en el orden de C que no haya sido usado en la
coloración de los vértices adyacentes a vk.

Ciclos de Hamilton
Un camino simple que contiene cada vértice de G se denomina camino
Hamiltoniano de G; análogamente, un ciclo Hamiltoniano de G es un
ciclo que contiene todos los vértices de G. Tales caminos y ciclos son así
llamados después que Hamilton (1856) describió, en una carta a su amigo
Graves, un juego matemático sobre el dodecaedro en el cual una persona
coloca cinco alfileres en cinco vértices consecutivos y a otra se le exige com-
pletar un camino simple hasta completar un ciclo. Un grafo es hamiltoniano

El Resto del Texto se encuentra en : http://webdelprofesor.ula.ve/ciencias/jlchacon/materias/discreta/grafos.pdf

Categorías:Uncategorized

Curioso Tutorial Acerca de las Relaciones de Recurrencia.

Un Curioso Video Tutorial acerca de las Relaciones de Recurrencia.

Muy Curioso pero bastante interesante :)

Categorías:Uncategorized
Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.