(4) COMPOSICIÓN_GRAFOS_ERG (1)

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 
 
 
COMPOSICIÓN DE GRAFOS 
En Matemáticas Discretas y en Ciencias de la Computación, un Grafo es un conjunto de objetos llamados 
vértices, puntos o nodos unidos por enlaces llamados aristas, arcos o segmentos (simplemente líneas), que 
permiten establecer relaciones binarias entre los elementos de un conjunto. 
Típicamente, un Grafo se representa gráficamente como un conjunto de nodos unidos por aristas. 
Un Grafo es un conjunto ordenado de vértices y aristas. 
G = (V, A) 
 
 
 
 
 
 
V: Representa conjunto de nodos y su nomenclatura es con números, círculos o puntos. 
 
 
 
 
 
 
 
A: Representa un conjunto de aristas. Las aristas tienen un inicio y un fin. 
 
 
 
 
G 
PUNTO
TO 
Círculo Círculo con Letra 
o con Número 
 
 
INICIO FIN 
 
B 
VÉRTICE 
 
M R 
ARISTA 
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 
 
 
Desde el punto de vista práctico, los Grafos permiten estudiar las interrelaciones entre unidades que 
interactúan unas con otras. Es decir, que, a manera de ejemplo, una red de ordenadores puede ser motivo de 
representarse y estudiarse mediante un Grafo, en el que los nodos representan las terminales y las aristas 
representan las conexiones, que pueden ser cables o conexiones inalámbricas. 
ÓRDEN DEL GRAFO: Se llama orden del Grafo a su número de vértices. Es igual al número de arcos que 
inciden en él. 
BUCLE: Es una arista que conecta un vértice consigo mismo, tiene su inicio y fin en el mismo nodo. Ejemplo: 
 
Cuando dos o más aristas son paralelas se dice que relacionan el mismo par de vértices. Ejemplo: 
 
 
 
 
COMPOSICIÓN DE UN GRAFO 
Aristas: son las rectas con las cuales se unen los vértices de un Grafo 
Vértice: Son los elementos que forman un Grafo. 
Aristas Cíclicas: Son las aristas que parten de un vértice para entrar en el mismo. 
Aristas Paralelas: Son aquellas aristas que tienen el mismo vértice inicial y final 
Aristas Adyacentes: Son aquellas que convergen en el mismo nodo. 
Cruce: Corresponde al punto donde se interceptan dos aristas. 
Camino: Se conoce como camino de un Grafo a un conjunto de vértices interconectados por aristas. 
 
K D 
mailto:erodriguezg@udistrital.edu.co
mailto:erogo13@hotmail.com
http://herramientaseconomia.blogspot.com/