GRAFOS (tipos de grafos y terminología básica)

Tipos de Grafos y sus Propiedades

Introducción a los Grafos

• Los grafos son estructuras discretas que conectan vértices mediante aristas. Se compone de un conjunto de vértices y un conjunto de aristas.

• Un grafo simple se representa gráficamente con puntos para los vértices y líneas (aristas) que los conectan, sin permitir aristas múltiples.

Grafo Simple vs Multi Grafo

• En un multi grafo, se permiten aristas paralelas entre los mismos vértices, lo que no es posible en un grafo simple. Esto significa que puede haber más de una arista entre dos vértices.

• Todo grafo simple puede considerarse como un multi grafo, pero no todos los multi grafos son simples debido a la posibilidad de tener aristas paralelas.

Autógrafos y Pseudo Grafos

• Un autógrafo permite bucles en sus vértices además de las aristas paralelas; se considera un pseudo grafo porque incluye características tanto del multi grafo como del grafo dirigido.

• En el caso de grafos dirigidos, las aristas tienen dirección y pueden incluir bucles, pero no permiten listas paralelas con el mismo sentido.

Terminología Básica

• Dos vértices son adyacentes si comparten una arista; por ejemplo, si hay una conexión directa entre ellos. El grado de un vértice es la cantidad total de aristas incidentes en él.

• La notación griega se utiliza para denotar el grado de cada vértice; por ejemplo, si el grado del vértice A es 2, significa que tiene dos conexiones directas con otros vértices.

Propiedades Adicionales

• En pseudo grafos, además de tener múltiples aristas o paralelas, también pueden tener bucles; el grado cuenta doble cuando hay bucles involucrados en un vértice específico.

• Existe un teorema que establece que la suma de los grados de todos los vértices es igual al doble del número total de aristas en el grafo; esto se aplica independientemente del tipo de grafo (simple o no).

Grados en Grafos Dirigidos

Conceptos Básicos de Grados en Grafos

• En los grafos no dirigidos, se cumple que cada vértice tiene un número par de grados. Sin embargo, al calcular los grados en grafos dirigidos, es necesario considerar tanto los grados de entrada como los de salida.

• Los grados de entrada se denotan con la letra delta (δ) y un signo menos (−). Este grado representa la cantidad de aristas que apuntan hacia un vértice específico.

• Por otro lado, los grados de salida se indican con un signo más (+). Se refiere a cuántas aristas salen desde un vértice hacia otros vértices.

Cálculo de Grados

• Para calcular el grado de entrada y salida, se deben contar las aristas que llegan y salen del vértice. Los bucles cuentan tanto como entradas como salidas.

• Existe un teorema importante que establece que la suma total de los grados de entrada es igual a la suma total de los grados de salida, lo cual también equivale al número total de aristas en el grafo dirigido.

Verificación del Teorema

• Al sumar los grados obtenidos, por ejemplo 2 + 3 + 5 = 10 para entradas y compararlo con las salidas (6 + 7 + 8 = 21), podemos verificar si el cálculo es correcto. Esto ayuda a confirmar la validez del teorema mencionado anteriormente.