Elementos y características de los grafos.
Un
grafo, G, es un par ordenado de V y A, donde V es el conjunto de vértices o
nodos del grafo y A es un conjunto de pares de vértices, a estos también se les
llama arcos o ejes del grafo. Un vértice puede tener 0 o más aristas, pero toda
arista debe unir exactamente a dos vértices. Los grafos representan conjuntos
de objetos que no tienen restricción de relación entre ellos. Un grafo puede
representar varias cosas de la realidad cotidiana, tales como mapas de
carreteras, vías férreas, circuitos eléctricos, etc. La notación G = A (V, A)
se utiliza comúnmente para identificar un grafo. Los grafos se constituyen
principalmente de dos partes: las aristas, vértices y los caminos que pueda
contener el mismo grafo.
Composición de un grafo.
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: 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.
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: 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.
Vértices :
Son los puntos o nodos con los que esta conformado un grafo. Llamaremos 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 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.
Son los puntos o nodos con los que esta conformado un grafo. Llamaremos 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 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.
Tipos de grafos.
Podemos clasificar los grafos en 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.
Ejemplo:
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> }
Gráficamente estas tres estructuras de vértices y arcos se pueden representar de la siguiente manera:
Ejemplo:
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> }
Gráficamente estas tres estructuras de vértices y arcos se pueden representar de la siguiente manera:
Hay también 6 tipos principales de grafos; simples,
completos, bipartidos, planos, conexos y ponderados.
Grafo simple. Se dice que el grafo G = (V, E) es un grafo simple de grado n si todos sus vértices tienen grado n.
Grafo completo. Un grafo es completo si cada par de vértices está unido por una arista. Se denota por Kn al grafo completo de n vértices. Ejemplos
Grafo bipartido. Un grafo es bipartido si V=V1?V2 y cada arista de E une un vértice de V1 y otro de V2
-Grafo bipartido completo
.Un grafo es bipartido completo si V=V1?V2 y dos vértices de V están unidos por una arista de E si y solo si un vértice está en V1 y el otro en V2. Se denota por Kr,sal grafo bipartido completo donde V1 tiene r vértices y V2 tiene s vértices
Grafos planos. Un grafo plano es aquel que puede ser dibujado en el plano sin que ninguna arista se interseque.
Grafos conexos. Un grafo es conexo si cada par de vértices está conectado por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b
Grafo ponderado. Un grafo es ponderado si presenta los pesos de cada arista y se puede determinar la longitud de una ruta, la cual es la suma de todos los pesos de las aristas.
Grafo simple. Se dice que el grafo G = (V, E) es un grafo simple de grado n si todos sus vértices tienen grado n.
Grafo completo. Un grafo es completo si cada par de vértices está unido por una arista. Se denota por Kn al grafo completo de n vértices. Ejemplos
Grafo bipartido. Un grafo es bipartido si V=V1?V2 y cada arista de E une un vértice de V1 y otro de V2
-Grafo bipartido completo
.Un grafo es bipartido completo si V=V1?V2 y dos vértices de V están unidos por una arista de E si y solo si un vértice está en V1 y el otro en V2. Se denota por Kr,sal grafo bipartido completo donde V1 tiene r vértices y V2 tiene s vértices
Grafos planos. Un grafo plano es aquel que puede ser dibujado en el plano sin que ninguna arista se interseque.
Grafos conexos. Un grafo es conexo si cada par de vértices está conectado por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b
Grafo ponderado. Un grafo es ponderado si presenta los pesos de cada arista y se puede determinar la longitud de una ruta, la cual es la suma de todos los pesos de las aristas.
