GRAFOS

      Grafos

        GENERALIDADES

·       Son estructuras de datos

·       Conjunto de nodos , vértices, arcos , aristas

·       Son usados en diferentes campos

ü Manejo de redes

ü Circuitos eléctricos

ü Estrategia de ventas

ü Cartografía

ü Transporte

GRAFOS DIRIGIDOS

Los grafos dirigidos indican que los arcos o aristas poseen dirección

Ejemplos

ADYACENCIA

Se dice que hay adyacencia entre dos vértices si están unidos por 2 arcos 

Ejemplo

         A es adyacente a B

         A es adyacente a C

         D es adyacente a B

INCIDENCIA

Los arcos inciden en los vértices, incide si una de sus puntas llega a ese vértice 

Ejemplo

Como observamos en el ejemplo de arriba  el arco es incidente en B porque vemos es la única dirección hacia la que esta apuntando 

COMPONENTES CONECTADOS SEPARADAMENTE

Estos pueden tener varios componentes separados 

Ejemplo

Grafos y dígrafos débilmente conectados

Si por al menos desde un vértice no podemos llegar a los demás

Ejemplo

GRAFOS Y DÍGRAFOS FUERTEMENTE CONECTADOS

Si es de cualquier vértice se puede llegar a los demás

CAMINO SIMPLE

Si partiendo de cualquier vértice podemos recorrer toda la estructura sin repetir  vértices ni arcos

GRAFO EULERIANO

Si partiendo de cualquier vértice podemos recorrer todo los arcos llegando el nuevo al Vértice origen

Se pueden visitar los vértices cuantas veces sea necesario, los arcos de pueden recorrer sólo una vez

GRAFO HAMILTONIANO

Si partiendo de cualquier vértice podemos recorrer todas las vértices sin repetir ninguno y finalmente llegar al mismo vértice origen

Los arcos se pueden recorrer una o más veces

ORDEN DE UN GRAFO

Es el número de vértices que posee un grafo

GRADOS DE UN GRAFO

Es el número de arcos que inciden en ese vértice

GRAFOS REGULARES

Se dice que es regular si todos los vértices tienen el mismo grado

ARCO CÍCLICO

Es Cíclico si parte de un vértice y llega al mismo

MULTIGRAFO

Es una estructura donde los vértices están unidos por más de un arco

GRAFO COMPLEMENTO

Es complemento si cada vértice tiene un grado igual a N-1

Donde n es el número de vértices que componen el grafo

GRAFO SIMÉTRICO

Se dice que es simétrico si al doblar la matriz por  la diagonal los ceros coinciden

LISTA DE ADYACENCIA

Almacena por cada vértice la lista de adjuntos desde otros vértices

Con la estructura podemos calcular fácilmente el grado de entradas de cualquier vértice solamente contando el número de nodos de la lista de vértice requerido 

    MATRIZ DE ADYACENCIA

Todo grafo simple puede ser representado por una matriz, que llamamos matriz de adyacencia.

Se trata de una matriz cuadrada de N filas X°n  columnas (siendo N el número de vértices del grafo).

Para construir la matriz de adyacencia, cada elemento  vale {{1}} cuando haya una arista que una los vértices  y . En caso contrario el elemento  vale 0.

La matriz de adyacencia, por tanto, estará formada por ceros y unos.

MATRIZ T DE INCIDENCIA DE LOS ELEMENTOS EN LOS VÉRTICES.

En esta matriz el número de renglones igual al número de vértices, y el número de columnas igual al número de elementos.

Si un elemento está orientado saliendo de un vértice, se coloca +1 en el renglón correspondiente al vértice y en la columna correspondiente al elemento; en caso contrario, si la orientación es entrando al vértice se coloca -1. Si el elemento no es incidente con un vértice se coloca cero.

El elemento es incidente en un vértice si éste es uno de los dos terminales del elemento. En cada columna de la matriz de incidencia de los elementos en los vértices, debe existir un +1 y un -1; la suma de los valores asociados a una columna debe ser cero.

La matriz de incidencia T de los vértices en los elementos representa la misma información que el grafo. Puede dibujarse el grafo a partir de T.

En los siguientes vídeos observaremos la representación de un grafo mediante lista de adyacencia, matriz de adyacencia y matriz de caminos.