Son diagramas o dibujos con
un par de conjuntos G se define como un conjunto E de pares no
ordenados,
El conjunto V es el conjunto
de vértices del grafo, se denota por V (G).
El conjunto E es el conjunto
de aristas del grafo, se denota por E (G).
TIPOS
DE GRAFOS:
GRAFOS
SIMPLES
Son aquellos grafos que no
tienen lazos ni lados paralelos.
GRAFOS
COMPLETOS
Es el grafo en donde cada vértice
está relacionado con todos los demás sin lazos ni lados paralelos. Se indica Kn
en donde n es el número de vértices del grafo.
Su fórmula se representa
Kn a=n(n-1)/2
GRAFO
BIPARTIDO
Es el grafo que está
compuesto por dos conjuntos de vértices, uno de ellos es:
A= {a1, a2, a3…an} y B= {b1,
b2, b3…bn}
En el que cada vértice de
A esta unido con todos los vértices de B
pero entre los vértices de un mismo conjunto no existen aristas que los unan.
Su fórmula es: knm.
GRAFO
CONEXO: Es aquel que para cualquier par de vértices distintos
entre sí existen un trayecto para ir de un vértice a otro.
GRAFO
NO CONEXO: Es aquel que no existen vértices conectados.
RECORRIDOS
DE GRAFOS
El objetivo es de recorrer
sobre los vértices y encontrar una trayectoria para eso existen tres tipos de
recorridos los cuales son:
*CAMINO: Es
una sucesión de lados que se pueden repetir los lazos y lados.
*CIRCUITOS: Es
un recorrido que realizan los lazos para llegar a dicha trayectoria.
*CIRCUITO
SIMPLE: Este ciclo solamente puede realizar la ruta que sigue y
puede pasar dos veces por la misma arista.
CAMINO
DE EULER: Es aquel camino que recorre todos los vértices pasando
por todas las ramas.
CIRCUITO
DE EULER: Es aquel circuito que recorre todos los vértices pasando
solo una vez.
CIRCUITO
DE HAMILTON: Es similar al circuito de Euler con la
diferencia de que en lugar de pasar por todos los grafos solamente una vez en
el circuito de Hamilton pasa por el vértice una vez.
Colocar las referencias bibliográficas y/o ligas de Internet sobre donde esta la información...
ResponderEliminar