GRAFOS

GRAFOS

DEFINICIÓN

Un grafo es una representación gráfica de diversos puntos que se conocen como nodos o vértices, los cuales se encuentran unidos a través de líneas que reciben el nombre de aristas.

TIPOS DE GRAFOS

Grafos Regulares 

Un grafo es regular si todos los vértices tiene el mismo grado.
Ejemplo

Grafos Simple

Un grafo simple es aquel que acepta una sola arista uniendo dos vértices cualesquiera.

Ejemplo

Multigrafo

Estructura donde dos vertices estan unidas por mas de un arco.

Ejemplo

Grafo Complejo

Si cada vértice tiene un grado igual a N-1 donde N es el numero de vértices del grafo.

n=6

n-1=5

 

ORDEN DE UN GRAFO

Es el numero de vértices que posee un grafo.

Grafo de un Vértice

Es el numero de arcos que inciden en el vértice

Grafo en un Dígrafo

Arco Ciclico

Si parte de un vértice y llega al mismo vertice

Adyacencia

existe adyacencia entre 2 vertices si estan unidos por otra arista

Incidencia 

los arcos inciden en los vertices si uno de sus puntos llega a ese vertice

Componentes conectadas separadamente

Grafos fuertemente conectado si desde cualquier vertice podemos llegar a los demas.

Grafo Eureliano

Si partiendo de cualquier vertice podemos recoger todos los arcos llegando de nuevo al vertice origen, se puede repetir verices cuantas veces sea necesario, los arcos se pueden recorres solamente una vez

Ejemplos

GRAFO SIMETRICO

Un grafo es simétrico si al doblar la matriz por la diagonal mayor coinciden los 0 y os 1

LISTA DE ADYACENCIA

En teoría de grafos, una lista de adyacencia es una representación de todas las aristas o arcos de un grafo mediante una lista.
Si el grafo es no dirigido, cada entrada es un conjunto o multiconjunto de dos vértices conteniendo los dos extremos de la arista correspondiente. 

MATRIZ DE ADYACENCIA 

La matriz de adyacencia es una matriz cuadrada que se utiliza como una forma de representar relaciones binarias.

Ejemplo

LISTA DE ADYACENCIA INVERTIDA

Almacena para cada vértice la lista de adjuntos desde otro vértice con la estructura se puede calcular el grado de entrada de cualquier vértice solamente cuando el numero de nodos de la lista del 

DIGRAFO FUERTEMENTE CONECTADO

Un dígrafo esta fuertemente conectado si desde cualquier vértice podemos llegar a todos los demás. 

Ejercicio: es necesario halla la matriz de caminos

                                                       

RTA