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

No hay comentarios:

Publicar un comentario