miércoles, 28 de marzo de 2012

TEORIA DE GRAFOS


RECORRIDO DE GRAFOS 
 Su objetivo es recorrer entre vértices y encontrar una trayectoria.
Su camino es la sucesión de repetir las vértices y los lados en un camino simple a la longitud n solamente en cada ciclo en la ruta que sigue.
Los circuitos o ciclos pueden pasar dos veces por la misma arista
GRAFO CONEXO
Es aquel que para cualquier paro de vértices distintos entre si existe un proyecto para ir de un vértice
GRAFO NO CONEXO
Es aquel en el que no existen vértices conectados
Ejemplo:
 imagen:http://www.cimat.mx/~amor/Omi/Entrenamiento/Grafos/Capitulo1.htm
CAMINO DE EULER
Es aquel que el camino que recorre todas las vertices pasando por todas las ramas solamente una vez
 imagen: manzanita newt  
CIRCUITO DE EULER
           Es aquel ciclo que recorre todos los vértices pasando por todos los lados solamente una vez
 
GRAFO
Tiene un circuito de Euler si y solo si es conexo y todas esas vértices tienen valencia par
CIRCUITO DE HAMILTON
Es similar al circuito de Euler con la diferencia de que en lugar de parar por todos los grafos solamente una vez.
En el circuito de Hamilton se pasa solamente una vez.
Respecto de un grafo que tiene un circuito de Euler si es conexo y todas sus vertices tienen valencia par, sin embargo no hay forma de saber con anticipacion si un grafo tiene o no un circuito de Hamilton
 


 
 
 

lunes, 26 de marzo de 2012

TEORIA DE GRAFOS


Leonhard Euler en el siglo XVlll al resolver el problema de los puentes de Konigsberg del rio Pregel.
imagen creada: manzanita newt

 Este problema consiste en recorrer 7 puentes que conectan 4 porciones de tierra, bajo la condición de pasar cada puente una sola vez.
  • Los lados paralelos:
Son las aristas que tienen relación con un mismo par de vértices
  • Los lazos:
Son aquellas aristas que salen de una vértice y regresa a la misma vértice
Valencia de un vértice:
Es el número de lados que salen o entran a un vértice. También denominando “orden de vértices” 

TIPOS DE GRAFOS
  1. GRAFOS SIMPLES
Son aquellos grafos que no tienen lazos ni lados paralelos

  1. GRAFO COMPLETO DE “N” VERTICES (KN)
Es el grafo en donde cada vértice esta relacionado con todos los demás, sin lazos ni lados paralelos. Se indica como kn en donde “n”  es el numero de vértices del grafo.

 Numero de lados=    n (n-1)
                                  2

Ejemplo:
Donde “n” es el numero de vértices del grafo completo
Ejemplo:
Kn=    k5
imagen: bajada de internet
 A= n (n-1)  = 5 (5-1)=   5 (4)  = 10  
           2               2             2




COMPLEMENTO DE UN GRAFO (G)

Es el grafo que falta al grafo Gen gorma que entre ambos forman un grafo completo de “n” vértice.este grafo no tiene lazos ni ramas paralelas.
imagen:http://docencia.udea.edu.co/regionalizacion/teoriaderedes/tiposu1.html


GRAFO BIPARTIDO
Es el grafo que esta compuesto por dos conjuntos de vértice

imagen: manzanita newt
GRAFO BIPARTIDO COMPLETO

Es el grafo que esta compuesto por dos conjuntos de vértices uno de ellos A={ a1, a2, a3,….an} a otro B={b1, b2,b3….bn} y en el que cada vértice de A esta unido con todos los vértices del B pero entre los vértices de un mismo  conjunto no existe arista que les una
K a,n


 ejemplo:

A={A, B, C}     B={D, E, F}

imagen:http://www.google.com.mx/imgres?q=GRAFO+BIPARTITO

TECNICAS DE CONTEO


TECNICAS DE CONTEO
Su objetivo es hacer combinaciones estas se forman atreves de condiciones establecidas por el Teorema Fundamental de la Condición y el Teorema Fundamental de la Multiplicación. Se pueden utilizar en arreglos, arboles y grupos.
 Hay dos tipos de condiciones:
  1. Se puede repetir
2.     Sin repetición

Ejemplo:
Digamos que tenemos cinco sabores de helado:
·         Banana (B)
·         Chocolate (CH)
·         Limón (L)
·         Fresa (F)
·         Vainilla (V)
Puedes tomar 3 sabores. ¿Cuántas variaciones hay?
Hay n=5 sabores para elegir      r=4 combinaciones
El orden no importa, ¡y sí puedes repetir!)
En este ejemplo encontramos el teorema de la multiplicación
Formula: 5x4=20 combinaciones
Podemos realizar el diagrama de árbol para estar mas seguros de que efectivamente esas son todas las posibles combinaciones
                                      chocolate
Banana                          limón
                                      Fresa
                                      Vainilla
                                      Banana
Chocolate                      Limon
                                            Fresa
                                     Vainilla

                                    Banana
Limón                         Chocolate
                                    Fresa
                                   Vainilla
      

                                       Banana
Fresa                             Chocolate
                                      Limón
                                       Vainilla

                                        Banana
Vainilla                          Chocolate
                                       Limón
                                        Fresa
·         Se puede repetir: como monedas en tu bolsillo (5,5,5,10,10)

5 x 5 x 5 x 10 x 10 = 12,500


·         Sin repetición: como números de lotería (2,14,15,27,30,33)
2 x 14 x 15 x 27 x 30 x 33 = 11,226,600



PERMUTACIONES
·         el orden sí importa
·         después lo cambiamos para que el orden no importe.
Ejemplo:
bolas de billar, digamos que queremos saber qué 3 bolas se eligieron, pero  no el orden.
Ya sabemos que 3 de 16 dan 3360 permutaciones.
Pero muchas de ellas son iguales para nosotros, porque no nos importa el orden.
Por ejemplo, digamos que se tomaron las bolas 1, 2 y 3. Las posibilidades son:
El orden importa
El orden no importa
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
1 2 3
Así que las permutaciones son 6 veces más posibilidades.
De hecho hay una manera fácil de saber de cuántas maneras "1 2 3" se pueden ordenar, y ya la sabemos. La respuesta es:
3! = 3 × 2 × 1 = 6
(Otro ejemplo: 4 cosas se pueden ordenar de 4! = 4 × 3 × 2 × 1 = 24 maneras distintas, ¡prueba tú mismo!)
FORMULA DE PERMUTACIONES
Así que sólo tenemos que ajustar nuestra fórmula de permutaciones para reducir por las maneras de ordenar los objetos elegidos (porque no nos interesa ordenarlos):
Esta fórmula es tan importante que normalmente se la escribe con paréntesis, así:
donde n es el número de cosas que puedes elegir, y eliges r de ellas
(No se puede repetir, el orden no importa)
Y se la llama "coeficiente binomial".
Notación
también usa estas notaciones:
Ejemplo
Entonces, nuestro ejemplo de bolas de billar ( sin orden) es:
16!
=
16!
=
20,922,789,888,000
= 560



3!(16-3)!
3!×13!
6×6,227,020,800
O lo puedes hacer así:
16×15×14
=
3360
= 560


3×2×1
6