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
- GRAFOS SIMPLES
Son aquellos grafos que no tienen
lazos ni lados paralelos
- 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