APRENDE GRAFOS DESDE CERO: Grafos básicos, lista y matriz de adyacencia, definiciones y propiedades.
Introducción a los Grafos
Definición de Grafos
- Los grafos son estructuras de datos utilizadas para representar y resolver problemas, fundamentales en aplicaciones como redes sociales.
- Un grafo se compone de un conjunto de vértices y otro de aristas que los conectan.
Tipos de Grafos
- Grado o valencia: El número de aristas conectadas a un vértice.
- Grafos camino (P): Vértices conectados en secuencia sin conectar extremos.
- Grafos ciclo (C): Cada vértice se conecta con otros dos, formando un ciclo.
- Grafos rueda (W): Todos menos uno forman un ciclo, conectado al restante.
- Grafos completos (K): Todos los vértices están interconectados.
Representación de Grafos
Métodos de Representación
- Formal: Nombra los vértices y aristas usando llaves.
- Lista de adyacencias: Lista que muestra las conexiones adyacentes para cada vértice.
- Matriz de adyacencia: Matriz cuadrada donde filas y columnas representan vértices; 0 indica no conexión y 1 indica conexión.
Grafos Dirigidos
- En grafos dirigidos, las aristas son flechas (arcos), lo que cambia la representación. Se utilizan pares ordenados en lugar de llaves.
Características Avanzadas
Grafos Ponderados
- Un grafo puede ser ponderado si se asocia un número (peso) a cada arista. Se utiliza la letra "w" para weight.
Multigrafos e Isomorfismo
- Los multigrafos contienen aristas múltiples o bucles; su matriz refleja el número de conexiones entre vértices.
- Un grafo es isomorfo a otro si sus estructuras pueden coincidir mediante una reordenación adecuada.
Propiedades Especiales
Planaridad y Complementariedad
- Un grafo es plano si no hay cruces entre aristas; por ejemplo, el K4 es plano mientras que el K5 no lo es debido a sus cruces inevitables.