hawasaya

Contenido ¿Qué es un grafo? ¿De que consta un grafo? Aristas Vértices Lazo o Bucle Caminos Camino Camino Cerrado Camino Simple Ciclo Grafo Conexo Árbol Gráfica Completa Gráfica Etiquetada Etiquetado elegante Etiquetado armonioso Coloración de grafos Multígrafo Matriz de Adyacencia Propiedades de la matriz de adyacencia Comparación con otras representaciones Ejemplo ¿Qué es 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. Esta definición da lugar a una representación gráfica, en donde cada vértice es un punto del plano, y cada arista es una línea que une a sus dos vértices. ¿De que consta 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. 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. Lazo o Bucle Un lazo o bucle es una arista que relaciona al mismo nodo; es decir, una arista donde el nodo inicial y el nodo final coinciden. Un bucle o lazo (loop en inglés) en un grafo o digrafo es una arista que conecta al mismo vértice consigo mismo. Un grafo simple no puede tener bucles. Caminos Camino Un camino es una sucesión de vértices tal que de cada uno de sus vértices existe una arista hacia el vértice sucesor. Dos caminos son ajenos o independientes si no tienen ningún vértice en común excepto el primero y el último. La longitud de un camino es el número de aristas que usa dicho camino, contando aristas recorridas varias veces el mismo número de veces que las recorramos. En el ejemplo, (1, 2, 5, 1, 2, 3) es un camino con longitud 5, y (5, 2, 1) es un camino simple de longitud 2.. Camino Cerrado Cuando los dos extremos de un camino son iguales, el camino se llama circuito o camino cerrado. Camino Simple Un camino simple es aquel en que todas las aristas del camino son diferentes. Si hay un camino no simple entre 2 vértices, también habrá un camino simple entre ellos. Ciclo Un Ciclo (o circuito) es un camino que empieza y acaba en el mismo vértice. Los ciclos de longitud 1 son los bucles. En el ejemplo, (1, 2, 3, 4, 5, 2, 1) es un ciclo de longitud 6. Un ciclo simple es un ciclo que tiene como longitud al menos 3 y en el que el vértice del comienzo sólo aparece una vez más y como vértice final, y los demás sólo aparecen una vez. En el grafo de arriba (1, 5, 2, 1) es un ciclo simple. Un ciclo es un camino cerrado donde los únicos vértices repetidos son el primero y el ultimo. Ciclo Euleriano: Es un camino o circuito que contiene todas las aristas apareciendo cada una de ellas exactamente una vez. Un grafo que admite dicho circuito se denomina grafo euleriano, y sus vértices o tienen grado par o dos de los vértices tienen grado impar. Ciclo Hamiltoniano: Es un camino simple que contiene todos los vértices apareciendo cada uno de ellos exactamente una vez. Un ciclo que a su vez es un camino hamiltoniano se denomina ciclo hamiltoniano, y un grafo que contiene un ciclo hamiltoniano se denomina grafo hamiltoniano. Grafo Conexo Un grafo es conexo si para cada par de vértices, existe un camino con extremos en dichos vértices. Si es posible formar un camino desde cualquier vértice a cualquier otro en el grafo, decimos que el grafo es conexo. Si es posible hacer esto incluso tras quitar k-1 vértices, decimos que el grafo es k-conexo. Un grafo es k-conexo si y sólo si contiene k caminos independientes entre cualesquiera dos vértices. Un grafo se puede definir como conexo si cualquier vértice V pertenece al conjunto de vértices y es alcanzable por algún otro. Otra definición que dejaría esto más claro sería: “un grafo conexo es un grafo no dirigido de modo que para cualquier par de nodos existe al menos un camino que los une”. Árbol Un árbol se define como un tipo de grafo que no contiene ciclos, es decir es un grafo también acíclico, pero a su vez es conexo. Tal es el caso de los siguientes dos grafos en donde se puede notar que ninguno de los dos contiene repeticiones (ciclos). Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos. También se suele dar una definición recursiva: un árbol es una estructura en compuesta por un dato y varios árboles. Gráfica Completa Se dice que un grafo es completo si el vértice v del otro vértice G es adyacente de los otros vértices de G. Un Grafo Completo es un grafo no direccionado donde existe un arco entre cada par de vértices cualesquiera del mismo. Un grafo completo es un grafo simple en el que todo el par de nodos está unido por una arista y se representa con Kn. La representación gráfica de los Kn como los vértices de un polígono regular se da cuenta de su peculiar estructura. Según el número de aristas que contiene, un grafo será completo si cuenta con todas las aristas posibles, es decir, si todos los nodos están conectados con todas las aristas. Gráfica Etiquetada Un grafo etiquetado es la asignación de etiquetas representado mediante enteros, a las aristas o vértices o ambos de un grafo. El término grafo etiquetado generalmente se refiere a un grafo con vértices etiquetados con todas las etiquetas distintas. Los grafos puede ser equivalentemente etiquetado mediante enteros consecutivos desde 1 hasta n, donde n es el número de vértices en el grafo. Para muchas aplicaciones, a las aristas y los vértices le corresponden etiquetas que tienen un significado en el dominio asociado. Existen 3 tipos de etiquetado: Etiquetado elegante Las etiquetas de los vértices están en negro, las etiquetas de las aristas en rojo. Etiquetado armonioso Un grafo armonioso es un grafo con “k” aristas que permiten una inyección de los vértices de “G” al grupo de enteros modulo “k” que induce una bisección entre las aristas de “G” y los enteros positivos hasta ||E||. Para cualquier arista e, los etiquetados de e son la suma de las etiquetas de dos vértices incidentes con “e”. Coloración de grafos La coloración de grafos es un caso muy especial para los grafos etiquetados, los vértices adyacentes y las aristas coincidentes deben tener diferentes etiquetas. Multígrafo Es un grafo que está facultado para tener aristas múltiples; es decir, aristas que relacionan los mismos nodos. De esta forma, dos nodos pueden estar conectados por más de una arista. Formalmente, un multigrafo G es un par ordenado G:=(V, E) donde: V es un conjunto de vértices o nodos E es un multiconjunto de pares no ordenados de nodos, llamados aristas o líneas. Un multigrafo es un grafo con varias aristas entre dos vértices. Matriz de Adyacencia El grafo está representado por una matriz cuadrada M de tamaño n2, donde n es el número de vértices. Si hay una arista entre un vértice x y un vértice y, entonces el elemento mx,y es 1, de lo contrario, es 0. Propiedades de la matriz de adyacencia Para un grafo no dirigido la matriz de adyacencia es simétrica. El número de caminos Ci,j(k), atravesando k aristas desde el nodo i al nodo j, viene dado por un elemento de la potencia k-ésima de la matriz de adyacencia. Comparación con otras representaciones Existen otras formas de representar relaciones binarias, como por ejemplo los pares ordenados o los grafos. Cada representación tiene sus virtudes y desventajas. En particular, la matriz de adyacencia es muy utilizada en la programación, porque su naturaleza binaria y matricial calza perfecto con la de los computadores. Sin embargo, a una persona común y corriente se le hará mucho más sencillo comprender una relación descrita mediante grafos, que mediante matrices de adyacencia. Otra representación matricial para las relaciones binarias es la matriz de incidencia. Ejemplo: Autor: Mézquita Rangel Pedro Antonio