Conceptos Clave de la Clase

Vértice (Nodo) Es un punto del grafo. Representa los elementos del sistema: V = {A, B, C...}.
Arista (Línea) Es el par de vértices relacionados: E = {(A, B), (B, C)...}.
Grado de un Vértice Es el número de conexiones o líneas que se unen a un punto específico.
Grafo Simple Grafo sin bucles (línea de un nodo a sí mismo) ni múltiples conexiones entre el mismo par.

2. Cinco Ejemplos Prácticos Ilustrados con Pares de Relaciones

Ejemplo 1: Grafo del Colegio

Conexión entre diferentes áreas físicas mediante pasillos directos.

Vértices: V = {8A, Biblio, Café, Cancha}

Grado destacado: El punto Café tiene grado 3 (se conecta con 8A, Biblio y Cancha).

Pares de Relaciones entre Vértices:

E = {(8A, Biblio), (8A, Café), (Biblio, Café), (Café, Cancha)}
  • (8A, Biblio): Pasillo entre el Salón 8A y la Biblioteca.
  • (8A, Café): Pasillo entre el Salón 8A y la Cafetería.
  • (Biblio, Café): Pasillo entre la Biblioteca y la Cafetería.
  • (Café, Cancha): Pasillo entre la Cafetería y la Cancha.
Ejemplo 2: Grafo de Amistades (Red Social)

Relaciones de amistad estrecha entre estudiantes de un curso.

Vértices: V = {Ariel, Beatriz, Carlos, Diana}

Grado destacado: El estudiante Carlos tiene grado 3 (es amigo de Ariel, Beatriz y Diana).

Pares de Relaciones entre Vértices:

E = {(Ariel, Beatriz), (Ariel, Carlos), (Beatriz, Carlos), (Carlos, Diana)}
  • (Ariel, Beatriz): Amistad directa entre Ariel y Beatriz.
  • (Ariel, Carlos): Amistad directa entre Ariel y Carlos.
  • (Beatriz, Carlos): Amistad directa entre Beatriz y Carlos.
  • (Carlos, Diana): Amistad directa entre Carlos y Diana.
Ejemplo 3: Grafo de Transporte Urbano

Rutas directas de transporte de bus entre estaciones clave.

Vértices: V = {Norte, Sur, Este, Oeste, Centro}

Grado destacado: La estación Centro tiene grado 4 (es el punto con más conexiones).

Pares de Relaciones entre Vértices:

E = {(Centro, Norte), (Centro, Sur), (Centro, Este), (Centro, Oeste), (Norte, Este), (Sur, Oeste)}
  • (Centro, Norte): Ruta directa Centro — Norte.
  • (Centro, Sur): Ruta directa Centro — Sur.
  • (Centro, Este): Ruta directa Centro — Este.
  • (Centro, Oeste): Ruta directa Centro — Oeste.
  • (Norte, Este): Ruta perimetral Norte — Este.
  • (Sur, Oeste): Ruta perimetral Sur — Oeste.
Ejemplo 4: Grafo de Internet y Computadores

Cableado físico de red en la sala de sistemas (Topología Estrella).

Vértices: V = {Servidor, Switch, PC1, PC2, Impresora}

Grado destacado: El equipo Switch tiene grado 4 (distribuye señal a todos los dispositivos).

Pares de Relaciones entre Vértices:

E = {(Servidor, Switch), (Switch, PC1), (Switch, PC2), (Switch, Impresora)}
  • (Servidor, Switch): Cable de red entre Servidor y Switch.
  • (Switch, PC1): Conexión del Switch al Computador 1.
  • (Switch, PC2): Conexión del Switch al Computador 2.
  • (Switch, Impresora): Conexión del Switch a la Impresora de red.
Ejemplo 5: Grafo de Entregas de Mensajería

Conexiones transitables entre casas para reparto de domicilio.

Vértices: V = {Casa A, Casa B, Casa C, Casa D, Casa E}

Grado destacado: La Casa C tiene grado 3 (punto clave de cruce de calles).

Pares de Relaciones entre Vértices:

E = {(A, B), (A, C), (B, C), (C, E), (D, E)}
  • (A, B): Calle directa entre Casa A y Casa B.
  • (A, C): Calle directa entre Casa A y Casa C.
  • (B, C): Calle directa entre Casa B y Casa C.
  • (C, E): Calle directa entre Casa C y Casa E.
  • (D, E): Calle directa entre Casa D y Casa E.
Recordatorio Importante: Grafos No Dirigidos

En un grafo simple no dirigido, el orden del par de vértices no altera la relación: la arista (A, B) representa exactamente la misma conexión que (B, A).