Teoria de grafos

TEORIA DE GRAFOS
Por: Jose Fernando Galindo Suarez

ESTRUCTURAS DE DATOS DE INFORMACION GRAFOS POR JOSE FERNANDO GALINDO SUAREZ

Qué es un Grafo?
• Representación gráfica de los datos de una situación particular. • Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas (edges en inglés) que pueden ser orientados ono. • Un grafo es una terna G = (V,A,j ), en donde V y A son conjuntos finitos, y j es una aplicación que hace corresponder a cada elemento de A un par de elementos de V. Los elementos de V y de A se llaman, respectivamente, "vértices" y "aristas" de G, y j asocia entonces a cada arista con sus dos vértices.
ESTRUCTURAS DE DATOS DE INFORMACION GRAFOS POR JOSE FERNANDO GALINDO SUAREZ

Qué es unaArista?
• Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos. • Si la arista carece de dirección se denota indistintamente {a, b} o {b, a}, siendo a y b los vértices que une. • Si {a ,b} es una arista, a los vértices a y b se les llama sus extremos.
ESTRUCTURAS DE DATOS DE INFORMACION GRAFOS POR JOSE FERNANDO GALINDO SUAREZ

Qué es unaArista?
• Aristas Adyacentes: Se dice que dos aristas son adyacentes si convergen en el mismo vértice. • Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial y el final son el mismo. • Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo. • Cruce: Son dos aristas que cruzan en un punto.

ESTRUCTURAS DE DATOS DE INFORMACION GRAFOS POR JOSE FERNANDO GALINDOSUAREZ

Qué son los vértices?
• Son los puntos o nodos con los que esta conformado un grafo. • grado de un vértice al número de aristas de las que es extremo. Se dice que un vértice es `par' o `impar' según lo sea su grado. • Vértices Adyacentes: si tenemos un par de vértices de un grafo (U, V) y si tenemos un arista que los une, entonces U y V son vértices adyacentes y se dice que U es elvértice inicial y V el vértice adyacente.
ESTRUCTURAS DE DATOS DE INFORMACION GRAFOS POR JOSE FERNANDO GALINDO SUAREZ

Qué son los vértices?
• Vértice Aislado: Es un vértice de grado cero. • Vértice Terminal: Es un vértice de grado 1.

ESTRUCTURAS DE DATOS DE INFORMACION GRAFOS POR JOSE FERNANDO GALINDO SUAREZ

Qué son los caminos?
• Sean x, y " V, se dice que hay un camino en G de x a y siexiste una sucesión finita no vacía de aristas {x,v1}, {v1,v2},..., {vn,y}. • x e y se llaman los extremos del camino • El número de aristas del camino se llama la longitud del camino. • Si los vértices no se repiten el camino se dice propio o simple. • Si hay un camino no simple entre 2 vértices, también habrá un camino simple entre ellos.
ESTRUCTURAS DE DATOS DE INFORMACION GRAFOS POR JOSEFERNANDO GALINDO SUAREZ

Qué son los caminos?
• Cuando los dos extremos de un camino son iguales, el camino se llama circuito o camino cerrado. • Llamaremos ciclo a un circuito simple • Un vértice a se dice accesible desde el vértice b si existe un camino entre ellos. Todo vértice es accesible respecto a si mismo

ESTRUCTURAS DE DATOS DE INFORMACION GRAFOS POR JOSE FERNANDO GALINDO SUAREZClasificación de los grafos
• Los grafos se pueden clasificar en dirigidos y no dirigidos. • En un grafo no dirigido el par de vértices que representa un arco no está ordenado. • los pares (v1, v2) y (v2, v1) representan el mismo arco. • En un grafo dirigido cada arco está representado por un par ordenado de vértices, de forma que y representan dos arcos diferentes.
ESTRUCTURAS DE DATOS DEINFORMACION GRAFOS POR JOSE FERNANDO GALINDO SUAREZ

Clasificación de los grafos
• Grafo regular: Aquel con el mismo grado en todos los vértices. Si ese grado es k lo llamaremos k-regular. • Grafo bipartito: Es aquel con cuyos vértices pueden formarse dos conjuntos disjuntos de modo que no haya adyacencias entre vértices pertenecientes al mismo conjunto • Grafo completo: Aquel con una arista entre...