Introducción a la Teoría de Grafos

Conceptos básicos para estudiantes de secundaria

1. ¿Qué es un grafo?

Un grafo es una estructura formada por un conjunto de vértices y un conjunto de aristas que indican qué vértices están conectados. En una representación gráfica, los vértices se dibujan como puntos y las aristas como segmentos que unen esos puntos.

Podemos escribir un grafo como G = (V, E), donde V es el conjunto de vértices y E es el conjunto de aristas.

Los grafos permiten representar situaciones como conexiones entre personas, carreteras entre lugares, redes de computadores, rutas o relaciones entre objetos.

2. Elementos básicos

Vértice

Es un punto del grafo. Puede representar una persona, lugar, computador, objeto, etc.

Arista

Es una conexión entre dos vértices. En un grafo simple no tiene dirección.

Incidencia

Una arista es incidente en los vértices que conecta.

Adyacencia

Dos vértices son adyacentes si existe una arista que los conecta.

3. Grado de un vértice

El grado de un vértice, escrito deg(v), es el número de aristas que inciden en él. En los grafos simples de esta clase, basta con contar cuántas conexiones llegan al vértice.

Ejemplo: si el vértice A está conectado con B, C y D, entonces deg(A) = 3.

Una propiedad importante es que, en un grafo, la suma de los grados de todos los vértices es igual al doble del número de aristas: Σ deg(v) = 2|E|.

4. ¿Qué es un grafo simple?

Un grafo simple es un grafo que no tiene bucles ni aristas paralelas. Por tanto, una arista conecta dos vértices distintos y no puede haber dos aristas diferentes conectando el mismo par de vértices.
✓ Sí es simple:
A — B
B — C
A — C
✗ No es simple:
A ↺ (bucle)
A — B y otra A — B (paralelas)

5. Cinco ejemplos de grafos simples

Cada ejemplo muestra su representación en <canvas>, el conjunto de vértices, el conjunto de aristas y las relaciones/conexiones.

Ejemplo 1 · Camino

V = {A, B, C, D}

E = {{A,B}, {B,C}, {C,D}}

Relaciones: A–B, B–C, C–D

Grados: 1, 2, 2, 1

Ejemplo 2 · Triángulo

V = {A, B, C}

E = {{A,B}, {B,C}, {A,C}}

Relaciones: A–B, B–C, A–C

Grados: 2, 2, 2

Ejemplo 3 · Estrella

V = {A, B, C, D, E}

E = {{A,B}, {A,C}, {A,D}, {A,E}}

Relaciones: A con B, C, D y E

deg(A)=4 · mayor grado

Ejemplo 4 · Cuadrado

V = {A, B, C, D}

E = {{A,B}, {B,C}, {C,D}, {D,A}}

Relaciones: A–B, B–C, C–D, D–A

Todos los grados = 2

Ejemplo 5 · Red con centro

V = {A, B, C, D, E, F}

E = {{A,B}, {A,C}, {A,D}, {B,E}, {C,E}, {D,F}}

Relaciones: A–B, A–C, A–D, B–E, C–E, D–F

deg(A)=3 · grado destacado

6. Conjunto de vértices, conjunto de aristas y relaciones

Para describir un grafo con precisión podemos separar la información:

GrafoVértices VAristas E / relaciones
Ejemplo 1{A,B,C,D}{A,B}, {B,C}, {C,D}
Ejemplo 2{A,B,C}{A,B}, {B,C}, {A,C}
Ejemplo 3{A,B,C,D,E}{A,B}, {A,C}, {A,D}, {A,E}
Ejemplo 4{A,B,C,D}{A,B}, {B,C}, {C,D}, {D,A}
Ejemplo 5{A,B,C,D,E,F}{A,B}, {A,C}, {A,D}, {B,E}, {C,E}, {D,F}

7. ¿Cuál es el vértice de mayor grado?

Precisión importante: el grado pertenece al vértice. Se obtiene contando cuántas aristas inciden en ese vértice. Por tanto, cuando buscamos la conexión "más destacada", primero identificamos el vértice de mayor grado. Las aristas que llegan a ese vértice son sus aristas incidentes.

Por ejemplo, en el Ejemplo 3, el vértice A tiene grado 4, por lo tanto A es el vértice de mayor grado. Las cuatro aristas {A,B}, {A,C}, {A,D}, {A,E} son incidentes en él.

8. Cinco grafos simples aplicados a problemas prácticos

Los grafos permiten representar situaciones reales mediante vértices (personas, lugares, equipos o dispositivos) y aristas (relaciones o conexiones). En los siguientes ejemplos se mantiene la condición de grafo simple: no hay bucles ni dos aristas diferentes entre el mismo par de vértices.

Aplicación 1 · Grafo del colegio

Situación: representar espacios del colegio y conexiones directas entre ellos.

V = {Portería, Patio, Biblioteca, Laboratorio, Cafetería}

E = {{Portería,Patio}, {Patio,Biblioteca}, {Patio,Cafetería}, {Biblioteca,Laboratorio}, {Cafetería,Laboratorio}}

Vértice de mayor grado: Patio, con grado 3.

Aplicación 2 · Transporte urbano

Situación: representar estaciones o paraderos y conexiones directas de una ruta.

V = {A, B, C, D, E}

E = {{A,B}, {A,C}, {B,D}, {C,D}, {D,E}}

Vértice de mayor grado: D, con grado 3.

Aplicación 3 · Grafo de amistades

Situación: representar relaciones de amistad entre estudiantes.

V = {Ana, Beto, Carla, Diego, Elena}

E = {{Ana,Beto}, {Ana,Carla}, {Ana,Diego}, {Beto,Elena}, {Carla,Elena}}

Vértice de mayor grado: Ana, con grado 3.

Aplicación 4 · Red de Internet

Situación: representar dispositivos conectados dentro de una red local.

V = {Router, PC1, PC2, Servidor, Impresora}

E = {{Router,PC1}, {Router,PC2}, {Router,Servidor}, {PC1,Impresora}}

Vértice de mayor grado: Router, con grado 3.

Aplicación 5 · Entrega de mensajería

Situación: representar puntos de entrega y conexiones directas entre zonas.

V = {Centro, A, B, C, D, E}

E = {{Centro,A}, {Centro,B}, {Centro,C}, {A,D}, {B,E}, {C,D}}

Vértice de mayor grado: Centro, con grado 3.

Idea clave: en todos estos casos, el vértice de mayor grado es el que tiene mayor cantidad de conexiones directas. Esto puede ayudar a identificar lugares, personas o dispositivos que ocupan una posición especialmente conectada dentro de la red.

9. Actividad rápida de comprensión

  1. ¿Cuántos vértices tiene el Ejemplo 4?
  2. ¿Cuántas aristas tiene el Ejemplo 4?
  3. ¿Cuál es el grado del vértice A en el Ejemplo 1?
  4. ¿Cuál es el vértice de mayor grado en el Ejemplo 3?
  5. ¿Por qué el Ejemplo 3 es un grafo simple?
  6. Escribe el conjunto V y el conjunto E del Ejemplo 2.

10. Resumen para recordar

Grafo
Vértices + aristas.
Vértice
Representa un punto u objeto.
Arista
Representa una conexión.
Grado
Número de aristas que inciden en un vértice.
Grafo simple
Sin bucles y sin aristas paralelas.
G = (V,E)
V = vértices; E = aristas.