Entradas populares

lunes, 25 de abril de 2011

GRAFOS


GRAFOS

Un grafo es una pareja de conjuntos G = (V,A), donde V es el conjunto de vértices, y A es el conjunto de aristas, este último es un conjunto de pares de la forma (u,v) tal que , tal que. Para simplificar, notaremos la arista (a,b) como ab.

»Multigrafo: Cuando hay 2 o más aristas paralelas, o cuando 2 vertices estan relacionados más veces con sigo mismo.





»Dígrafo: Hay un punto de origen y uno de destino final, es decir: no pueden ser a,b = b,a.




-QUE ES UNA ARISTA:

Son las lineas con las que se unen los vertices de un grafo, los vertices a y b son los extremos.


»Arista Adyacente: 2 aristas son adyacentes si convergen en el mismo vertice.

»Arista Paralelas: Son dos aristas conjuntas si el vertice inicial y final son el mismo.
»Arista Ciclicos: Es la arista que parte de un vertice para entrar en el mismo.
»Cruce: Son 2 aristas que cruzan en un mismo punto.




-QUE ES UN VERTICE:
Los vértices son los dos elementos que forman un grafo. Como ocurre con el resto de las ramas de las matemáticas, a la Teoría de Grafos no le interesa saber qué son los vértices.
Diferentes situaciones en las que pueden identificarse objetos y relaciones que satisfagan la definición de grafo pueden verse como grafos y así aplicar la Teoría de Grafos en ellos.



CAMINO

Un camino en un grafo es una sucesión finita en la que aparecen alternadamente vértices y aristas de dicho grafo.
»Longitud del Camino: Está dada por número de aristas, parecido al tamaño.

»CAMINO ABIERTO:
Diferente punto de partida al de llegada, Que no llega a su principio.

»CAMINO CERRADO:
Cuando su punto de llegada es el mismo de partida.

»CAMINO SIMPLE:
No tiene aristas repetidas pero si puede tener vértices repartidos

»CAMINO ELEMENTAL:
No puede repetir ni aristas ni vértices, tiene que ser abierto.
»Todo camino elemental es simple, pero no todo caminos simple es elelemntal.


-TIPOS DE GRAFOS

»GRAFO CIRCULO:
Camino simple y cerrado




»GRAFO CICLO:
Camino elemental y cerrado


»GRAFO CADENA:
Camino elemental y abierto



No hay comentarios:

Publicar un comentario en la entrada