FUNDACIÓN UNIVERSITARIA UNICLARETIANA
TEMA:
GRAFOS
AUTORES:
SARITH CUESTA RENTERIA
CRISTIAN CAMILO MAYORAL PALACIOS
JUAN LUIS MOSQUERA ALOMIAS
MAILON STIVEN MENA MENA
CRISTIAN CAMILO HURTADO RODRÍGUEZ
FACULTAD DE INGENIERÍA DE SISTEMAS
MATERIA:
MATEMÁTICAS DISCRETAS
DOCENTE:
NANCY GONZALES
08 DE MAYO DE 2025
QUIBDÓ-CHOCO
INTRODUCCION
Los grafos son estructuras fundamentales en las matemáticas y ciencias de la
computación, utilizadas para modelar relaciones y conexiones entre elementos.
A través de sus nodos y aristas, permiten representar desde redes sociales hasta
sistemas de transporte o circuitos eléctricos. Este documento presenta los
conceptos básicos de los grafos, sus tipos, las matrices asociadas para su
representación, y el concepto de isomorfismo, todo con el fin de facilitar su
comprensión y aplicación en diversos contextos.
OBJETIVOS GENERALES
Comprender los fundamentos teóricos y estructurales de los grafos, sus tipos,
representaciones matriciales e isomorfismo, para su correcta interpretación y
aplicación en problemas reales.
OBJETIVOS ESPECIFICOS
1. Definir los elementos básicos que componen un grafo: vértices y aristas.
2. Clasificar los diferentes tipos de grafos según dirección, peso, conexión y
estructura.
3. Explicar el uso de la matriz de adyacencia y de incidencia como
herramientas de representación de grafos.
4. Describir el concepto de isomorfismo de grafos y su importancia en la
equivalencia estructural.
5. Promover el uso de grafos como modelo para resolver problemas en
distintas áreas del conocimiento.
JUSTIFICACION
El estudio de grafos resulta esencial debido a su amplia aplicabilidad en campos
como la informática, ingeniería, biología, sociología y más. Comprender su
estructura, clasificación y formas de representación permite modelar
eficientemente relaciones y optimizar procesos. Además, el isomorfismo de
grafos ofrece una perspectiva analítica para identificar similitudes estructurales
que pueden simplificar el análisis de sistemas complejos.
CONCEPTOS BÁSICOS DE GRAFOS
Los grafos son estructuras matemáticas que consisten en un conjunto de nodos o
vértices conectados por aristas o arcos. A continuación, se muestran algunos
conceptos básicos de los grafos:
*Definiciones Básicas
1. Grafo: Un grafo es un conjunto de nodos o vértices conectados por aristas o
arcos.
2. Nodo o Vértice: Un nodo o vértice es un punto en el grafo que puede estar
conectado a otros nodos.
3. Arista o Arco: Una arista o arco es una conexión entre dos nodos.
Conceptos Básicos de los Grafos
1. Grado de un Nodo: El grado de un nodo es el número de aristas que se
conectan a él.
2. Camino: Un camino es una secuencia de nodos y aristas que conectan dos
nodos.
3. Ciclo: Un ciclo es un camino que comienza y termina en el mismo nodo.
4. Conectividad: La conectividad de un grafo se refiere a la capacidad de los
nodos para estar conectados entre sí.
TIPOS DE GRAFOS
Existen varios tipos de grafos, clasificados según diferentes características.
Aquí está la siguiente clasificación general:
1. Según la dirección de las aristas
• Grafo dirigido (dígrafo): Las aristas tienen una dirección (como una
flecha).
• Grafo no dirigido: Las aristas no tienen dirección (simple conexión entre
dos nodos).
2. Según la presencia de múltiples aristas o lazos
• Grafo simple: No tiene lazos (aristas que conectan un vértice consigo
mismo) ni múltiples aristas entre el mismo par de vértices.
• Multigrafo: Puede tener múltiples aristas entre el mismo par de vértices.
• Pseudografo: Puede tener lazos y múltiples aristas.
3. Según el peso de las aristas
• Grafo ponderado: Las aristas tienen un valor numérico (peso o costo).
• Grafo no ponderado: Todas las aristas se consideran iguales (sin peso).
4. Según la conexión entre vértices
• Grafo conexo: Existe al menos un camino entre cada par de vértices (en
grafos no dirigidos).
• Grafo fuertemente conexo: En grafos dirigidos, hay un camino en
ambas direcciones entre cualquier par de vértices.
• Grafo débilmente conexo: En grafos dirigidos, hay conexión si se
ignoran las direcciones de las aristas.
• Grafo disconexo: No todos los vértices están conectados.
5. Otros tipos especiales
• Árbol: Grafo conexo y sin ciclos.
• Bosque: Conjunto de árboles (varios grafos sin ciclos).
• Ciclo: Camino cerrado donde no se repiten vértices, excepto el primero y
último.
• Grafo completo (Kn): Todos los vértices están conectados entre sí.
• Grafo bipartito: Los vértices se pueden dividir en dos conjuntos
disjuntos donde no hay aristas entre vértices del mismo conjunto.
MATRICES ASOCIADAS A GRAFOS
Las matrices asociadas a grafos son representaciones numéricas que describen
cómo están conectados los vértices entre sí. Las dos principales son:
La matriz de adyacencia y la matriz de incidencia.
La matriz de adyacencia es una matriz cuadrada que representa las conexiones
entre vértices de un grafo. En ella, las filas y columnas corresponden a los
vértices, y cada posición indica si hay una arista entre dos vértices (con un 1 o
el peso si el grafo es ponderado). En grafos no dirigidos, esta matriz es simétrica
y en un grafo dirigidos no.
La matriz de incidencia es una matriz donde las filas representan los vértices y
las columnas las aristas. En grafos no dirigidos, se coloca un 1 en las filas
correspondientes a los dos vértices que conecta una arista. En grafos dirigidos,
se usa -1 para el vértice de origen y 1 para el de destino.
ISOMORFISMO DE GRAFOS
El isomorfismo de grafos se refiere a la equivalencia estructural entre dos
grafos, es decir, a que ambos representan la misma organización subyacente,
aunque sus elementos (vértices y aristas) puedan estar etiquetados o dispuestos
de manera diferente. Desde el punto de vista formal, dos grafos son isomorfos si
existe una correspondencia uno a uno entre sus vértices de forma que se
preserven las relaciones de adyacencia: si dos vértices están conectados por una
arista en el primer grafo, sus imágenes correspondientes también deben estar
conectadas en el segundo grafo.
Este concepto es especialmente relevante en la teoría de grafos porque permite
identificar cuándo dos estructuras, a pesar de aparentar diferencias superficiales,
comparten la misma “esencia” en términos de conectividad. De esta forma, el
isomorfismo facilita la clasificación de grafos en categorías que tienen
propiedades equivalentes, lo que resulta útil tanto en aplicaciones teóricas como
prácticas, por ejemplo, en química para identificar moléculas con la misma
estructura, o en informática para optimizar redes.
10 EJEMPLOS DE APLICACIÓN DE LA TEMÁTICA (GRAFOS) EN
LA VIDA DIARIA:
Redes eléctricas
Mapas de ciudades
Organización
Redes de comunicación
Programación de algoritmos
Electricidad
Biología
CONCLUSION
Concluimos que los grafos ofrecen una herramienta poderosa para representar y
analizar sistemas interconectados. A través de sus elementos básicos,
clasificaciones y matrices asociadas, se facilita su estudio formal. Además, el
concepto de isomorfismo refuerza la idea de que diferentes representaciones
pueden compartir la misma estructura esencial. Dominar estos fundamentos es
clave para aplicar los grafos en contextos prácticos y académicos, resolviendo
problemas de forma clara y eficiente.
BIBLIOGRAFIA
1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009).
Introduction to Algorithms (3rd ed.). MIT Press. – Referencia clásica en
teoría de algoritmos, incluye capítulos sobre grafos y sus
representaciones.
2. Diestel, R. (2017). Graph Theory (5th ed.). Springer. – Libro académico
ampliamente reconocido que cubre teoría de grafos desde un enfoque
matemático riguroso.
3. Gross, J. L., & Yellen, J. (2005). Graph Theory and Its Applications (2nd
ed.). Chapman & Hall/CRC. – Explica tipos de grafos, matrices asociadas
e isomorfismo con aplicaciones.
4. Rosen, K. H. (2012). Discrete Mathematics and Its Applications (7th ed.).
McGraw-Hill. – Introduce los conceptos básicos de grafos de forma
accesible para estudiantes.
5. West, D. B. (2001). Introduction to Graph Theory (2nd ed.). Prentice
Hall. – Excelente para comprender las bases teóricas y la clasificación de
grafos