GRAFOS

Grafos

En este tema veremos a continuación diferentes puntos de vista de los grafos particulares como:

generalidades

          ¿Qué es un grafo particular?

Cuantas clases de grafos particulares hay

Representación

Algoritmos

-Un grafo es un conjunto de nodos o también llamados vértices, conectados por una línea llamada aristas, que permiten representar relaciones binarias entre elementos de un conjunto.

-Son objeto de estudio de la teoría de grafos.

-Los grafos se utilizan en distintos campos.

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