GRAFOS

CONCEPTO

Conjunto de nodos o vértices , conectados por arcos.

Se utilizan en manejos de redes, circuitos electricos, estrategia de ventas , cartografia , transporte.

GRAFO DIRIGIDO (DIGRAFO)

Es cuando los arcos tienen direccion

adyancencia= existen adyacencia entre dos vertices , si estan unidos por un arco existe adyancencia desde y adyacencia hacia .

INCIDENCIA

Los arcos inciden en los vertices si una de sus puntas llega a ese vertice.

GRAFOS DEBILMENTE CONECTADOS

Se dice que es debilmente conectados si por lo menos desde un vertice no puede llegar a los demas

GRAFOS FUERTEMENTE CONECTADOS

Si desde cualquier vertice se puede llegar a los demas

CAMINO SIMPLE

Si partimos de un vertice podemos recorrer la estructura sin repetir vertices ni arcos .

GRAFO EURELIANO

Si partimos desde cualquier vertice podemos recorrer todos los arcos llegando de nuevo al vertice de origen .

Se pueden visitar los vertices cuantas veces sea necesario.

Los arcos solo se pueden recorrer 1 vez.

GRAFO HAMILTONIANO

Si partimos de cualquier vertice podemos recorrer todos los vertices podemos recorrer todos los vertices sin repetir ninguno y finalmente llegar al mismo vertice de origen, los arcos se pueden repetir una o mas veces.

ORDEN DE UN GRAFO

Es el numero de arcos que inciden en ese vertice .

GRAFO REGULAR

Se dice que es regular si todos los vertices tienen el mismo grado.

ARCO CICLICO

Un arco ciclico es si parte de un vertice y llega al mismo.

MULTIGRAFO

Es una estructura donde 2 vertices estan unidas por mas de un arco .

GRAFO COMPLETO

Es completo si cada vértice tiene un grado igual a n-1 , donde n es el numero de vértices que componen el grafo.

LISTA DE ADYACENCIA INVERTIDA

Almacena para cada vertice la lista de adjuntos desde otros vertices.

Con la estructura podemos calcular facilmente , el grado de entrada de cualquier vertice solamente contando el numero de nodos de la lista del vertice requerido.