Teoria de Grafos . Matematicas Discretas.pptx

Teoria de Grafos

1. Teoría de Grafos: Introducción y Fundamentos La teoría de grafos estudia relaciones y conexiones entre objetos. Es fundamental en informática, ciencias sociales y otras áreas. jc J honatan C ontreras Johan Ruiz Jhon Penagos Julian Valencia

2. Grafos Simples: Definición y Ejemplos Definición Conjunto de vértices unidos por aristas sin bucles ni múltiples conexiones. Propiedades No permite aristas paralelas ni bucles. Ejemplos Redes sociales básicas y mapas de carreteras simplificados.

3. Multigrafos y Pseudografos: Extensiones de Grafos Multigrafos Permiten múltiples aristas entre dos vértices. Ejemplo: redes de comunicación con enlaces redundantes. Pseudografos Permiten bucles: aristas que conectan un vértice consigo mismo. Aplicación: modelado de autorreferencias en sistemas.

4. Grafos Dirigidos (Digrafos) Definición Aristas tienen dirección, llamadas arcos. Aplicaciones Flujo de trabajo y diagramas de dependencia. Representación Matrices de adyacencia para grafos dirigidos.

5. Multigrafos Dirigidos Combinación Permite múltiples arcos dirigidos entre vértices. Usos Modela sistemas complejos con relaciones direccionales redundantes.

6. Terminología Básica de Grafos Elementos Vértices (nodos) Aristas (lados) Grado de un vértice Características Caminos y ciclos Grafos conexos y componentes Matrices y listas de adyacencia

7. Familias Distinguidas de Grafos Simples: Grafos Completos Definición Cada vértice está conectado a todos los demás. Propiedades Número elevado de aristas, alta conectividad y pequeño diámetro. Aplicaciones Modelos de redes densas y sistemas completamente interconectados.

8. Familias Distinguidas: Grafos Ciclo y Rueda Grafo Ciclo (Cn) Vértices unidos formando un solo ciclo cerrado. Ejemplo: circuitos eléctricos simples. Grafo Rueda (Wn) Grafo ciclo con un vértice central conectado a todos. Útil para modelar redes con nodo central fuerte.

9. Grafos Bipartitos: Definición y Propiedades Definición Vértices divididos en dos conjuntos disjuntos. Propiedad Aristas solo conectan vértices de conjuntos distintos. Ejemplos Asignación de tareas a empleados, relaciones cliente-producto.

10. Aplicaciones y Conclusiones Resumen Diversos tipos de grafos modelan relaciones complejas. Estos modelos son clave en muchas disciplinas. Siguientes pasos Estudio avanzado de propiedades y algoritmos Aplicación en inteligencia artificial y sistemas complejos Exploración de grafos ponderados y dinámicos