Actividad 7- GRAFOS

Introduce un texto aquí...

Actividad:

1. Definir que es un grafo

2. ¿Que uso se le dan a los grafos?

3. ¿Como se pueden clasificar los grafos?

4. ¿Como se pueden representar los grafos?

-------------------------------------------------------------

Nota: Recuerde que cada pregunta debe ir acompañada de:

Los enlaces de donde consulto la información (normas Apa) .
De un aporte personal con sus propias palabras de lo que entendió de lo consultado.
De una imagen que tenga relación con el tema o pregunta con su respectivo enlace (normas Apa)
Insertar un video video (youtube) que explique o aclare la pregunta con su enlace respectivo (normas Apa)
Debajo del video realizar un resumen de lo que dice o explica el autor del video.

Solución :

1 : ¿Qué es un grafo?

Un grafo es una estructura matemática que sirve para modelar relaciones entre objetos. Está formado por un conjunto de vértices (o nodos) y un conjunto de aristas (o enlaces) que unen pares de vértices. Formalmente se denota G = (V, E), donde V es el conjunto de vértices y E el conjunto de aristas.

APA : The MIT Press, Instituto Tecnológico de Massachusetts (MIT). (21 de octubre de 2025). Detalles del libro - MIT Press . MIT Press. https://mitpress.mit.edu/9780262033848/introduction-to-algorithms/

LINK

2: ¿Qué usos se le dan a los grafos?

Redes de transporte: rutas entre ciudades, planificación de rutas y logística.

Redes de comunicación e Internet: modelado de routers, enlaces y tráfico.

Redes sociales: relaciones entre personas (amistad, seguidores) y análisis de comunidades.

Algoritmos y teoría de la computación: búsqueda, recorrido (BFS/DFS), optimización (camino mínimo, flujo máximo).

Biología y bioinformática: redes metabólicas, redes genéticas, análisis de proteínas.

Química: modelado de moléculas (átomos como vértices y enlaces químicos como aristas).

Operaciones e investigación de operaciones: problemas de diseño de redes, ruteo y asignación.

Lingüística y procesamiento del lenguaje: grafos para relaciones semánticas, redes de palabras.

Visualización de datos y análisis de dependencias.

APA : Editores de la Enciclopedia Británica. (20 de julio de 1998). Gráfico | Matemáticas, Redes y Aplicaciones . Enciclopedia Británica. https://www.britannica.com/science/graph-mathematics

LINK

3 : ¿Cómo se pueden clasificar los grafos?

- Según la orientación:

- No dirigido (undirected): las aristas no tienen dirección; la relación es mutua.

- Dirigido o dígrafo (directed): las aristas tienen dirección (arcos), representan relaciones asimétricas.

- Según el peso:

- No ponderado: las aristas no tienen peso.

- Ponderado: cada arista tiene un peso o coste (p. ej. distancia, tiempo).

- Según militaristas:

- Simple: a lo sumo una arista entre un par de vértices y sin lazos (loops).

- Multigrafo: puede tener múltiples aristas entre los mismos vértices y/o lazos.

- Según conectividad:

- Conexo: en grafos no dirigidos, existe un camino entre cualquier par de vértices.

- Desconexo: existen componentes conectados separados.

- Fuertemente/ débilmente conectado (para dirigidos): depende de si hay caminos en ambas direcciones o al ignorar direcciones.

- Según ciclos:

- Acíclico: no contiene ciclos

- Cíclico: contiene ciclos.

- Otros tipos especiales:

- Bipartito: vértices divididos en dos conjuntos, aristas solo entre conjuntos distintos.

- Completo: cada par de vértices está conectado por una arista.

- Planar: puede dibujarse en el plano sin aristas que se crucen.

- Árbol: grafo conexo y acíclico.

APA : GeeksforGeeks. (23 de julio de 2025). Algoritmos de grafos . GeeksforGeeks. https://www.geeksforgeeks.org/dsa/graph-data-structure-and-algorithms/

LINK

4: ¿Cómo se pueden representar los grafos?

Representación visual (dibujo): nodos y aristas dibujados en el plano; útil para entender estructura y hacer análisis visual.

Lista de adyacencia:

Para cada vértice se guarda la lista de vértices adyacentes.

Ventajas: eficiente en memoria para grafos dispersos; rápido para iterar vecinos.

Desventajas: acceso directo para comprobar existencia de arista entre dos vértices puede ser más lento (O(deg(v))).

Matriz de adyacencia:

Matriz |V|×|V| donde la entrada (i,j) indica presencia (y/o peso) de arista entre i y j.

Ventajas: acceso O(1) para comprobar si existe una arista; conveniente para operaciones algebraicas.

Desventajas: costosa en memoria para grafos grandes y dispersos (O(|V|^2)).

Matriz de incidencia:

Matriz |V|×|E| que relaciona vértices con aristas; útil en ciertos problemas algebraicos y de flujos.

Lista de aristas (edge list):

Simple lista de pares (o tuplas con peso) que representan cada arista.

Útil para algoritmos que procesan aristas directamente (p. ej. Kruskal).

Otras representaciones: estructuras comprimidas para grafos grandes, representaciones orientadas a bases de datos (p. ej. grafos en Neo4j) o formatos de intercambio (GraphML, GEXF, adjacency lists en JSON, etc.)

APA : Colaboradores de Wikipedia. (29 de septiembre de 2025). Grafo (matemáticas discretas) . Wikipedia. https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)

LINK

Aporte personal

Lo que yo entiendo es que un grafo es una forma sencilla pero muy útil de representar relaciones entre diferentes cosas. Por ejemplo, uno puede pensar en los vértices como personas, ciudades o páginas web, y las aristas serían las conexiones entre ellas, como amistades, carreteras o enlaces.

Lo mejor de los grafos es que, con ellos, uno puede aplicar matemáticas y algoritmos para resolver preguntas súper prácticas, como: ¿Cuál es el camino más corto entre dos puntos?, ¿Qué nodo es el más importante en una red?, o ¿Cómo se puede desconectar una red gastando lo menos posible?

También me di cuenta de que, dependiendo del problema que uno tenga, es clave escoger bien cómo representar el grafo (ya sea con listas de adyacencia, matrices, etc.), porque eso puede afectar mucho la eficiencia de los algoritmos, sobre todo cuando se trabaja con datos grandes.

APA : Moraguez, ER (2024b, 7 de mayo). Teoría de Gráficos en Computación: Aplicaciones y Beneficios | LovTecnología . LovTecnología. https://lovtechnology.com/teoria-de-grafos-en-computacion-aplicaciones-y-beneficios/

LINK

APA : BitBoss. (2022b, 23 de abril). APRENDE GRAFOS DESDE CERO: Grafos básicos, lista y matriz de adyacencia, definiciones y propiedades. [Video]. YouTube. https://www.youtube.com/watch?v=vnNFiNVy9KM

RESUMEN EXPLICATIVO DEL VIDEO :

¿Qué es un grafo?

Un grafo es una estructura de datos que se usa para representar relaciones entre objetos, y está compuesto por:

Vértices (nodos): los elementos.
Aristas (enlaces): las conexiones entre los vértices.

Conceptos básicos:

Grado (valencia): número de aristas conectadas a un vértice.

Tipos de grafos comunes:

Grafo camino (Path - P):
Vértices conectados en línea, sin cerrar el ciclo.
Grafo ciclo (Cycle - C):
Vértices conectados formando un ciclo.
Grafo rueda (Wheel - W):
Un vértice central conectado a un grafo ciclo.
Grafo completo (Komplett - K):
Todos los vértices están conectados entre sí.
Grafo bipartito (Kₘ,ₙ):
Dos grupos de vértices; conexiones solo entre grupos, no dentro de un mismo grupo.

Formas de representar un grafo:

Formal: Conjuntos de vértices y aristas.
Lista de adyacencia: Una lista para cada vértice con los que está conectado.
Matriz de adyacencia: Matriz cuadrada con:
- 1 si hay conexión.
- 0 si no la hay.
- Diagonal nula (cero) y matriz simétrica en grafos no dirigidos.

Variaciones de grafos:

Grafo dirigido:
Las conexiones tienen dirección (flechas). Se usan paréntesis ( ) en lugar de llaves { } para representar aristas. La matriz ya no es simétrica.
Grafo ponderado:
Las aristas tienen pesos (valores numéricos). En la matriz, en lugar de 1, se colocan los pesos.
Multigrafo:
Puede tener múltiples aristas entre los mismos vértices o bucles (una arista que conecta un vértice consigo mismo). La matriz muestra el número de conexiones.

Propiedades de los grafos:

Isomorfismo:
Dos grafos son isomorfos si tienen la misma estructura, aunque los vértices estén en distinto orden o posición.
Plano:
Un grafo es plano si puede dibujarse sin que sus aristas se crucen. Ejemplo:
- K4 es plano.
- K5 no es plano.
Complementario:
Se forma al eliminar todas las aristas y agregar conexiones donde no había.
Si el grafo resultante es isomorfo al original → es autocomplementario.
Conexo:
Todos los vértices están conectados entre sí (por algún camino).
Cíclico:
Contiene al menos un ciclo (camino que empieza y termina en el mismo vértice, sin repetir vértices).
Árbol:
Es conexo y sin ciclos.

Actividad 7- GRAFOS

1 : ¿Qué es un grafo?

3 : ¿Cómo se pueden clasificar los grafos?

- Según la orientación:

- Según el peso:

- Según militaristas:

- Según conectividad:

- Según ciclos:

4: ¿Cómo se pueden representar los grafos?

Aporte personal

¿Qué es un grafo?

Conceptos básicos:

Tipos de grafos comunes:

Formas de representar un grafo:

Variaciones de grafos:

Propiedades de los grafos:

Configuración avanzada