teoria de grafos

22 DE FEBREERO DE 2014.
SAN CRISTÓBAL DE LAS CASAS, CHIAPAS.

TEORÍA DE GRAFOS

En una red de comunicación, no es necesario que toda estación pueda comunicarse directa- mente con otra, puesto que las estaciones pueden actuar de posta para un mensaje entre otras dos estaciones. Si una estación, o una línea de datos, dejan de funcionar, queremos saber si la red queda conexa, es decir, sitodas las estaciones que siguen funcionando pueden comunicarse entre sí. Para preguntas como ésta, no nos interesa la ubicación física de las estaciones, sino sólo su conectividad, y es así que surge la noción matemática de grafo, que es simplemente unos nodos con algunas conexiones que se llaman aristas. Una arista puede conectar dos nodos, o, como en algunas aplicaciones, un nodo consigo mismo. Unaarista está anclada en sus dos extremos a nodos, o posiblemente al mismo nodo en los dos extremos. Formalmente: Definición 3.1. Un grafo es (N, A, P) donde N es un conjunto de nodos, A es un conjunto de aristas, y P es una función de las aristas tal que cada P(a) = {p, q} donde p, q son nodos (posiblemente con p = q, así que podemos decir que P(a) es un conjunto de 1 o 2 elementos). Cuando G esun grafo, GN denota sus nodos, GA sus aristas, y GP su función de aristas.

ARISTA
NODO
LAZO








NODOS

En informática y en telecomunicación, de forma muy general, un nodo es un punto de intersección, conexión o unión de varios elementos que confluyen en el mismo lugar. Ahora bien, dentro de la informática la palabra nodo puede referirse a conceptos diferentessegún el ámbito en el que nos movamos:
En redes de computadoras cada una de las máquinas es un nodo, y si la red es Internet, cada servidor constituye también un nodo. El concepto de red puede definirse como:
En estructuras de datos dinámicas un nodo es un registro que contiene un dato de interés y al menos un puntero para referenciar (apuntar) a otro nodo. Si la estructura tiene sólo un puntero,la única estructura que se puede construir con él es una lista, si el nodo tiene más de un puntero ya se pueden construir estructuras más complejas como árboles o grafos.


RAMAS Y LAZOS
Las ramas son las aristas que unen a los vértices que en este caso unen a los nodos.
Aristas.- Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos.ARISTA
NODO
LAZO






Lazo: es una arista cuyos extremos inciden sobre el mismo vértice
ARISTA
NODO
LAZO





RAMAS PARALELAS: Se dice que dos aristas son paralelas si el vértice inicial y el final son el mismo


VALENCIA

Valencia de un vértice.- Es el número de lados que salen o entran a un vértice.

CAMINOS

Un camino es una sucesión devértices tal que de cada uno de sus vértices existe una arista hacia el vértice sucesor. Un camino simple es aquel que no repite vértices en su recorrido.








Camino euleriano
Un camino euleriano en un grafo es un camino que usa cada arista una y sólo una vez. Si existe tal camino decimos que el grafo es euleriano. Esta definición es dual a la de camino hamiltoniano.Camino hamiltoniano

Existe un concepto dual al de camino/ciclo Euleriano. Un camino hamiltoniano en un grafo es un camino que "visita" cada vértice una y sólo una vez











GRAFOS SIMPLES
En matemáticas y ciencias de la computación, un grafo (del griego grafos: dibujo, imagen) es un conjunto de objetos llamados vértices o nodosunidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto. Son objeto de estudio de la teoría de grafos.
Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas).
Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre unidades que...