Camino o trayectoria es el recorrido desde un V0 (vértice inicial) a Vn (vértice destino) de longitud n, es una sucesión alternante de n + 1 vértices y n aristas que comienza en elvértice V0 y termina en el Vn . Formalmente significa: comience en el vértice v0; recorra la arista e1 hasta v1; siga por la arista e2 hasta v2, y así sucesivamente.
(v_0', e_1', v_1', e_2', v_2',…. v_{n - 1}, e_n, v_n)
Donde la arista e_i es incidente sobre los vértices v_{i - 1} y v_i para i = 1, … n.
Ejemplo:
Construyamos un camino en G desde el vértice 1 hasta el vértice 2 de longitud4.
Camino o trayectoria de G: (1, e_1, 2, e_2, 3, e_3, 4, e_4, 2)
Además, el mismo camino se puede representar así: (1, 2, 3, 4, 2)
En caso de que no se repita ningún vértice entonces recibe elnombre de camino simple, por ejemplo: (1, 2, 3,4) y (7, 6, 5,2)
IMPORTANTE
Sean v y w vértices en un grafo G.
* Un camino simple o trayectoria de v a w es una ruta de v a w sin vérticesrepetidos.
* Un ciclo (o circuito) es un camino de longitud diferente de cero de v a v sin aristas repetidas.
* Un ciclo simple es un ciclo de v a v en el que no hay vértices repetidos, exceptopor el inicio y el fin que son iguales a v.
Tomando como referencia la grafica anterior, vamos a determinar si tiene caminos simples, ciclo y ciclo simple.
conecxa
una grafica es conexa si dados cualquiera dos vertices existe una trayectoria.
Representación de los grafos
Representación por incidencia
Lista de incidencia
El grafo está representado por un arreglo de aristas, identificadas por un de pares de vértices, que son los que conecta esa arista.
Matriz de incidencia
El grafo está representado por una matriz de A (aristas) por V (vértices), donde [arista, vértice] contiene la información de la arista (conectado o no conectado).
Representación por adyacencia
Listas de adyacencia
El grafo está representado por un arreglo de listas de adyacencia. Para un vértice i, la lista de adyacencia está formada por todos los vértices adyacentes a i. Puede construirse en tiempo lineal, y las inserciones pueden hacerse al principio de cada lista, con lo que se asegura tiempo constante.
Matriz de adyacencia
Una matriz de adyacencia es una matriz M de dimensión n*n, en donde n es el número de vértices que almacena valores booleanos, donde M[i,j] es verdadero (o contiene un peso) si y solo si existe un arco que vaya del vértice i al vértice j. La inicialización llevaría un tiempo del O ( #(V2)).
Representación Grafica
Un grafo se representa mediante un diagrama en el cual a cada vértice le corresponde un punto y si dos vértices son adyacentes se unen sus puntos
correspondientes mediante una línea, ejemplo:
ISOMORFISMO DE GRAFOS
Definición:
Dos grafos G1 y G2 son isomorfos si existe una función biyectiva f entre los vértices de G1 y G2, y una función biyectiva g entre lados de G1 y G2 tales que un lado e es incidente a v y w en G1 si solo si el lado g(e) es incidente a los vértices f (v) y f (w) en G2. Al par de funciones f y g se le denomina isomorfismo.
Ejemplo:
Sean los siguientes grafos G1 y G2
Dos grafos G1 y G2 son isomorfos si existe una función biyectiva f entre los vértices de G1 y G2, y una función biyectiva g entre lados de G1 y G2 tales que un lado e es incidente a v y w en G1 si solo si el lado g(e) es incidente a los vértices f (v) y f (w) en G2. Al par de funciones f y g se le denomina isomorfismo.
Ejemplo:
Sean los siguientes grafos G1 y G2
Un isomorfismo para los grafos anteriores G1 y G2 esta definido por:f (a) = A
f (b) = B
f (c) = C
f (d) = D
f (e) = E
f (b) = B
f (c) = C
f (d) = D
f (e) = E
y g(Xi) = Yi, i = 1, ... , 5
Los grafos G1 y G2 son isomorfos si y solo si para alguna ordenación de vértices y lados sus matrices de incidencia son iguales. Veamos las matrices de incidencia de los grafos anteriores:
GRAFOS APLANABLES
Este tipo de grafos, además de aparecer con mucha frecuencia también cuentan con muchas propiedades interesante. Se analizarán algunas de las más importantes.
Definición:
Diremos que un grafo es aplanable si puede ser dibujado sobre un plano de tal manera tal que ninguna arista se cruce con otra excepto, desde luego, en los vértices comunes. El siguiente es un grafo aplanable:
Diremos que un grafo es aplanable si puede ser dibujado sobre un plano de tal manera tal que ninguna arista se cruce con otra excepto, desde luego, en los vértices comunes. El siguiente es un grafo aplanable:
Ejemplo:
La siguiente figura es un grafo no aplanable que a decir verdad corresponde al problema de determinar si es posible conectar las casas 1, 2, 3 a los servicios de Luz, Agua y Drenaje, de tal manera que no haya 2 líneas de conexión que se crucen una con la otra.
La siguiente figura es un grafo no aplanable que a decir verdad corresponde al problema de determinar si es posible conectar las casas 1, 2, 3 a los servicios de Luz, Agua y Drenaje, de tal manera que no haya 2 líneas de conexión que se crucen una con la otra.
Definición:
Una región (o cara) de un grafo aplanable se define como una área del plano que está acotada por aristas y no pude continuar dividiéndose subáreas.
Una región (o cara) de un grafo aplanable se define como una área del plano que está acotada por aristas y no pude continuar dividiéndose subáreas.
Ejemplo:
El siguiente grafo tiene 5 regiones que son:
El siguiente grafo tiene 5 regiones que son:
Definición:
Diremos que una región es infinita si su área es infinita y se dice que es finita, si su área es finita. En un grafo aplanable se tienen exactamente una región infinita.
Tenemos el siguiente resultado:
v 
e + r = 2
e + r = 2
donde v, e y r son el numero de vértices, aristas y regiones respectivamente. Esta ecuación se conoce como la Formula de Euler para grafos aplanables. Sin excepción alguna todos los grafos aplanables conexos deben satisfacer la formula de Euler.
En cualquier grafo aplanable lineal conexo que no tenga lazos y que tenga 2 o mas aristas se cumple la siguiente desigualdad:
En cualquier grafo aplanable lineal conexo que no tenga lazos y que tenga 2 o mas aristas se cumple la siguiente desigualdad:
e 
3v 6
3v 6
Debido a que el grafo es lineal cada región es acotada por 3 o más aristas por lo tanto el número es mayor o igual que 3r. en la frontera a lo largo de 2 regiones, el numero total es igual o menor a 2e así tenemos:
2e  3r | ó |  |
De acuerdo a la fórmula de Euler, tenemos que:
 | ó | 3v - 6 e |
Es evidente que la planaridad de un grafo no se ve afectada si una arista es dividida en dos arista por la inserción de un vértice de grado 2 como i) o si 2 aristas se combinan en una sola arista al eliminar este vértice como en ii)
 | |
i)
|
ii)
|
Definición:
Dos grafos G1 y G2 son isomorfos bajo vértices de grado 2, si son isomorfos ó si pueden transformarse en grafos isomorfos mediante repeticiones de inserciones y/o eliminaciones de vértices de grado 2 como en i) y i i).
Ejemplo:
Los siguientes grafos son isomorfos bajo vértices de grado 2.
Teorema de Kuratoswki
Un grafo es aplanable si y solo si no contiene cualquier subgrafo que sea isomorfo bajo vértices de grado 2 a cualquier de los siguientes grafos, que son llamados de Kuratowski
Árboles
Un grafo conectado que contiene circuitos no simples se llama árbol. En el año de 1857 Arthur Cayley, matemático inglés, los empleó para contabilizar componente químicos, no obstante, es importante señalar que no solo es una herramienta de la química sino que se han utilizado en diversas áreas, por ejemplo, conforme el propio interés de la materia encaminado hacia las ciencias de la computación, se utiliza para la construcción de las redes.
Propiedades de los árboles
Entre las propiedades más importantes de los árboles está la presencia de un paseo entre cualquiera de dos vértices del árbol; segundo, que el número de vértices no es menor al número de aristas del árbol y que un árbol con más de dos vértices tiene por lo menos dos hojas.
Un ejemplo claro de los árboles en la vida cotidiana son los árboles genealógicos. Para este caso, los vértices representan a los miembros de la familia y los arcos representan la relación de parentesco. Conforme los conocimientos adquiridos con anterioridad, el árbol no deja de ser un grafo, pero es del tipo no dirigido.
Ejemplo de árbol genealógico:
En este ejemplo cabe señalar que los recuadros representan los vértices del grafo y los arcos son las líneas que representan las relaciones de parentesco conforme a esta familia:
 Representación de árboles
El árbol es un grafo no dirigido conectado con circuitos no simples; además, no contiene arcos múltiples, con la propiedad de que hay un único camino simple entre cada par de vértices, teniendo el siguiente teorema:
Teorema 1. “Un grafo no dirigido es un árbol si y solo si hay un camino simple único entre cualesquiera dos de sus vértices”.
Conforme los siguientes grafos, ¿cuál de ellos es del tipo de árboles?
Ejemplo:
¿Cuáles de los grafos de la figura 6.2 son árboles?
Fig. 6.2 Grafo 1,2 y 3
Si se observan los siguientes grafos, se concluye que el grafo G1 no es un árbol porque se observa un circuito simple, pero los grafos G2 Y G3 son de árboles, porque están conectados con circuitos no simples.
Como se sabe, existen grafos que no tienen conexión y podría existir confusión el pensar que un árbol es un grafo conectado que tiene circuitos no simples, pero es importante mencionar que existen árboles del tipo que contienen circuitos no simples que no necesariamente están conectados, y esos árboles reciben el nombre de bosques, cuya característica es que cada uno de sus componentes conectados es un árbol.
Los árboles son mostrados a continuación:
En gran parte de las aplicaciones de árboles, se designa a un vértice particular del árbol como laraíz, por lo que se pude asignar una dirección a cada arco, debido que hay un camino único de la raíz a cada vértice del grafo dirigiéndose cada arco alejándose de la raíz, conforme lo enunciado en el teorema 1, en el apartado 6.1.2, por lo tanto es un grafo de árbol con raíz, esto es simplemente el árbol que junto con su raíz forman un grafo y en caso que fuesen diferentes s vértices como raíz, se producen diferentes árboles con raíz.
A continuación se muestra un grafo de árbol con raíz:
De acuerdo a lo anterior se muestran los árboles con raíz en donde a y c son las raíces correspondientes del grafo R.
Lo usual es elaborar un grafo de árbol con raíz en la parte superior del grafo, en donde las flechas muestran la dirección de los arcos, como se muestra en la siguiente figura:
En el apartado 6.1.1 se elaboró un árbol genealógico con el propósito de familiarizarse con la terminología, que es de origen genealógico y botánico.
Observe el siguiente grafo:
En esta figura se deduce que E es un árbol con raíz a, se observa que los padres son b, c y d y, a su vez, don hermanos, f y g son hijos de b; además, e es hijo de c.
Otro ejemplo: si se supone que A es un árbol con raíz, si v es un vértice en A diferente de la raíz, el padre de v es el único vértice u tal que hay un arco dirigido de u a v. Cuando u es el padre de v, v es llamado un hijo de u. Los vértices con el mismo padre son llamados hermanos. Los ancestrosde un vértice diferente de la raíz son los vértices en el grafo de la raíz a ese vértice, excluyendo el vértice mismo e incluyendo a la raíz. Los descendientes de un vértice v son aquellos vértices que tienen a v como ancestro. Un vértice de un árbol es llamado hoja si no tiene hijos. Los vértices que tienen hijos son llamados vértices internos. La raíz es un vértice interno a menos que sea el único vértice del grafo, en ese caso es una hoja. Si a es un vértice en un árbol, el subárbol con a como raíz, es el subgrafo del árbol que consiste de a y sus descendientes y todos los arcos incidentes en estos descendientes.
Observa la siguiente figura:
En este árbol Z, la raíz está en el vértice a; el padre de c es b y su descendencia es b y e; los hermanos de i son h y j, quienes son hijos de g; además, se pueden observar todos los ancestros de m; y también se observa que en este árbol con raíz existe otro subárbol con raíz en el vértice g, si se hace un acercamiento en esta parte se percibe lo siguiente:
El padre es g, los hijos son h,i,j y los descendentes de j son i e m, y el descendente de h es k.
También existe un árbol con raíz, de nombre m-ario, que consiste en que cada vértice interno no tiene más de m hijos, y el árbol m-ario completo consiste si cada vértice tiene exactamente m hijos y un árbol m-ario con cuando m=2 es llamado árbol binario.
Conforme lo visto anteriormente se distinguirán los diferentes tipos de grafos:
Este grafo representa un árbol binario completo porque cada uno de sus vértices internos tiene un hijo.
En esta figura se representa un árbol, árbol 3-ario, completo porque cada uno de sus vértices internos tiene tres hijos.
Este es un árbol 5-ario completo porque cada vértice interno tiene 5 hijos.
Este grafo representa un árbol m-ario completo para alguna m, porque algunos de sus vértices internos tienen dos hijos y otros tienen tres hijos.
También existe el caso de un árbol con raíz ordenado debido que los hijos de cada vértice interno están ordenados, y estos se expresan en el grafo de tal forma que los hijos de cada vértice interno se representan en orden de izquierda a derecha. Si el árbol con raíz ordenado tiene un vértice interno del cual emanan dos hijos, el primero se nombra hijo izquierdo y el segundo es llamadohijo derecho
|
No hay comentarios:
Publicar un comentario