Teoria De Grafos

TEORÍA DE GRAFOS

Definición: Para las matemáticas y las ciencias de la computación, un grafo es el principal objeto de estudio de la teoría de grafos. De esta forma, un grafo se representa gráficamente como un conjunto de puntos (llamados vértices o nodos), unidos por líneas (aristas). Los grafos permiten estudiar las interrelaciones entre unidades que se encuentran en interacción.

Son diagramas que si se interpretan en forma adecuada proporcionan información, como por ejemplo los mapas, diagramas de circuitos o de flujos, entre otros

Aplicaciones de los Grafos

Las aplicaciones más importantes de los grafos son las siguientes:

 Rutas entre ciudades.

 Determinar tiempos máximos y mínimos en un proceso.

 Flujo y control en un programa.

Un grafo está compuesto por dos conjuntos finitos.

 Un conjunto de |A| aristas,

 Un conjunto de |V| vértices

J es la relación de incidencia, que asocia a cada elemento de |A| un par de elementos de |V|

Se denota G= {A, V, j}

Vértices: Son los objetos representados por punto dentro del grafo

Aristas: son las líneas que unen dos vértices

Aristas Adyacentes: dos aristas son adyacentes si convergen sobre el mismo vértice

Aristas Múltiples o Paralelas: dos aristas son múltiples o paralelas si tienen los mismos vértices en común o incidente sobre los mismos vértices

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

Arista Incidente

Una arista es incidente a un vértice si ésta lo une a otro vértice.

La arista a, es Incidente en los Vértices A Y B.

Vértice Aislado: Es un vértice de grado cero

Vértice Pendiente: Es aquel grafo que contiene sólo una arista, es decir tiene grado 1

Cruce: Son intersecciones de las aristas en puntos diferentes a los vértices

Grafo Sencillo o Simple: Se dice que un Grafo G es simple si no tiene aristas cíclicas y existe una sola arista entre dos vértices.

Grafo Completo: Un grafo es completo si cada vértice tiene un grado igual a n-1, donde n es el número de vértice que compone el grafo.

Para saber el número máximo de aristas que posee un grafo completo se aplica la formula.

A=(n*(n-1))/2

Tipos de Grafos

Existen dos tipos de grafos los no dirigidos y los dirigidos.

No dirigidos: son aquellos en los cuales los lados no están orientados (no son flechas).

Dirigidos: son aquellos en los cuales los lados están orientados (flechas

Grafo no Simple:

Grafo no dirigido que tiene lados paralelos y lazos.

Grado o Valencia de un Vértice: Es el número de aristas que inciden sobre un vértice

Grado Regular: Un grafo G simple, se dice que es K-regular, si todo vértice de G incide exactamente K-aristas, donde K es una constante.

Es decir, tiene igual número de arista en todos sus vértices.

CICLO DE EULER

Recorrer todas las aristas del grafo sin repetirlas.

CICLO DE HAMILTON

Recorrer todos los vértices del grafo sin repetirlos, excepto el V0 y Vn que son el mismo

MATRIZ DE ADYACENCIA

Una matriz de adyacencia es aquella que muestra de la forma más rustica cómo está compuesto un grafo, esto es que dónde se coloque un uno se representa como una arista que una los dos nodos y con cero donde no hay unión.

Propiedades

Es cuadrada y simétrica

La suma de cada fila o columna es el grado del vértice correspondiente

La diagonal es nula

MATRIZ DE INCIDENCIA

Una matriz que está compuesta por unos y ceros, en la que se representan los nodos unidos por las aristas. Cada arista une dos y nada más que dos nodos.

En general, las matrices de incidencia

...