Teoria De Grafos

Teoría de grafos | | | |

|
|
En matemáticas y ciencias de la computación, la teoría de grafos estudia las propiedades de los grafos, que son colecciones de objetos llamados nodos (o vértices) conectados por líneas llamadas aristas (o arcos) que pueden tener orientación (dirección asignada). |

Introducción a la teoría de grafos | | | |

|
|
Problema de los Puentes deKönisbergDefinición: Un grafo G = (N, A) consta de un conjunto de nodos N y un conjunto de aristas A, en donde a cada arista es un par no ordenado de nodos. 
Una arista en general se representa por {a, b}.Una forma de representar grafos es mediante círculos para los nodos, conectados por líneas para las aristas.Ejemplo: G = { n1, n2, n3,n4,n5, n6, n7,n8 } , A = { {n1, n2}}, {n1, n5},{n2, n3},{n3,n4} , {n4, n7}, {n2, n6},{n6, n2} } Notación: Una arista es un conjunto, pero puede haber dos aristas que conecte los mismos nodos, por lo que se le puede anteponer un nombre, por ejemplo a1 (n2, n6), a2(n2, n6) son dos aritas para unir los nodos n2 y n6. También puede ser que en una arista importe el orden de los nodos por lo que podemos en este caso utilizar la notación de par ordenado (n1, n2). |
Conceptos básicos de grafos | | | |

|
|
Aristas: 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.Aristas Adyacentes: Sedice 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.
Vértices: Son los puntos o nodos con los que esta conformado un grafo. Llamaremos grado de un vértice alnú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 el vértice inicial y V el vértice adyacente.Vértice Aislado: Es un vértice de grado cero.Vértice Terminal: Es un vértice de grado 1.Caminos: Sean x, y Î V, se dice que hay un camino en G de x a y si existe una sucesión finita no vacía de aristas {x, v1}, {v1, v2},…, {vn, y}. En este caso
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 caminosimple entre ellos.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. |
Clasificación de grafos | | | |

|
|
Los grafos se pueden clasificaren dos grupos: dirigidos y no dirigidos. En un grafo no dirigido el par de vértices que representa un arco no está ordenado. Por lo tanto, 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.Ejemplos G1 = (V1, A1) V1 = {1, 2, 3, 4} A1 = (1, 2), (1, 3), (1, 4), (2,3), (2, 4), (3, 4) G2 = (V2, A2) V2 = {1, 2, 3, 4, 5, 6} A2 = (1, 2), (1, 3), (2, 4), (2, 5), (3, 6) G3 = (V3, A3) V3 = {1, 2, 3} A3 = { <1, 2>, <2, 1>, <2, 3> }
Algunos de los principales tipos de grafos son los que se muestran a continuación: * Grafo regular: Aquel con el mismo grado en todos los vértices. Si ese grado es k lo llamaremos k-regular. Por ejemplo, el primero...