GRAFOS
- CAROLINA RAMIREZ
- 26 may 2016
- 2 Min. de lectura
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.
MATRIZ CAMINOS
Se utiliza para determinar si el digrafo es fuertemente conectado.
S=# de caminos de acuerdo al numero de nodos
Si la matriz de caminos resultante nos da todo es diferente de 0 es fuertemente conectada
