(5 )PROPIEDADES_GRAFOS_ERG

Vista previa del material en texto

FORMACIÓN PROFESIONAL  MATEMÁTICAS DISCRETAS  GUÍAS  PROBABILIDADES Y ESTADÍSTICA 
PROFESOR ERNESTO RODRÍGUEZ GONZÁLEZ 
 
 erodriguezg@udistrital.edu.co  erogo13@hotmail.com  Blog Profesor: http://herramientaseconomia.blogspot.com 1 
 
 
PROPIEDADES DE LOS GRAFOS 
 
 Incidencia: Una arista es incidente cuando la recta o arco une un vértice con otro. 
 
 
 
 Adyacencia: Dos aristas son adyacentes si tienen un vértice en común (confluyen en el mismo vértice). 
 
 
 
 Ponderación: Corresponde a una función en la cual cada arista tiene un peso o un valor, que puede ser 
 distancia, peso en libras, gamos, etc., longitud, costo, tiempo, entre otros. 
 
 
 
 
1 3 
mailto:erodriguezg@udistrital.edu.co
mailto:erogo13@hotmail.com
http://herramientaseconomia.blogspot.com/
FORMACIÓN PROFESIONAL  MATEMÁTICAS DISCRETAS  GUÍAS  PROBABILIDADES Y ESTADÍSTICA 
PROFESOR ERNESTO RODRÍGUEZ GONZÁLEZ 
 
 erodriguezg@udistrital.edu.co  erogo13@hotmail.com  Blog Profesor: http://herramientaseconomia.blogspot.com 2 
 
 
 Etiquetado: Es la marca, nombre o distinción que se hace a los vértices o aristas de un grafo. 
 
 
 
ESTRUCTURA DE GRAFOS 
Las dos representaciones generales más usadas en los Grafos son las siguientes: 
 
1. MATRIZ DE AYACENCIA 
 Para este tipo de estructura se utiliza una matriz n x n donde las filas y las columnas hacen referencia a la 
longitud entre cada par de vértices. Relaciona dos vértices adyacentes. 
 Ejemplo: 
 
 
 
 
mailto:erodriguezg@udistrital.edu.co
mailto:erogo13@hotmail.com
http://herramientaseconomia.blogspot.com/
FORMACIÓN PROFESIONAL  MATEMÁTICAS DISCRETAS  GUÍAS  PROBABILIDADES Y ESTADÍSTICA 
PROFESOR ERNESTO RODRÍGUEZ GONZÁLEZ 
 
 erodriguezg@udistrital.edu.co  erogo13@hotmail.com  Blog Profesor: http://herramientaseconomia.blogspot.com 3 
 
2. LISTA DE ADYACENCIA 
 Para este tipo de estructura se utiliza un elemento por cada vértice. Almacena una lista de vértices 
adyacente que va de vértice en vértice adyacente. Corresponde a una Lista de Vértices Contiguos. 
 Ejemplo: 
 
 
3. LISTA DE GRADOS 
 
 
 
 
 
 
 
VÉRTICE ADYACENCIA GRADOS 
 
A 
B 
C 
 
C, B 
C, A 
B, A 
 
2 
2 
2 
 
 
 
 
A B 
C 
mailto:erodriguezg@udistrital.edu.co
mailto:erogo13@hotmail.com
http://herramientaseconomia.blogspot.com/