Teoria De Grafos

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, si todas 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. Una arista 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 es un 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 diferentes segú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 de vé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

...