Informe Sobre Grafos Luis_suarez.pdf.docx

Universidad Nacional Experimental de los Llanos Occidentales Ezequiel Zamora. Programa de Ingenieria, Arquitectura y Tecnologia (PIAT). Barinas-Edo.Barinas.

Docente:

Alumno:

Franklin España.

Luis Suarez. C.I: V.-26133364.

Barinas Edo. Barinas 04 de Febrero de 2018.

Definición de Grafos: En matemáticas y ciencias de la computación, un grafo (del griego grafos: dibujo, imagen) es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto. Son objeto de estudio de la teoría de grafos. Un grafo es la representación simbólica de los elementos constituidos de un sistema o conjunto, mediante esquemas gráficos. Se puede decir también, que un grafo consiste en un conjunto de nodos (también llamados vértices) y un conjunto de arcos (aristas) que establecen relaciones entre nodos. Es importante resaltar, que informalmente un grafo se define como G = (V, E), siendo los elementos de V los vértices o nodos, y los elementos de E, las aristas. Formalmente, un grafo G, se define como un par ordenado, G = (V, E), donde V es un conjunto finito y E es un conjunto que consta de dos elementos de V. Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre unidades que interactúan unas con otras. Por ejemplo, una red de computadoras puede representarse y estudiarse mediante un grafo, en el cual los vértices representan los terminales y las aristas representan las conexiones inalámbricas). En fin, prácticamente cualquier problema puede representarse mediante un grafo. 

Ejemplo de Grafo con 6 vértices y 7 aristas.

En la imagen inferior cada punto (nodo) representa a una persona y cada línea (arista) establece la relación de amistad entre dos nodos. Vista esta representación de las relaciones dentro de una red social no es de extrañar que a través de la teoría de grafos se estudien los patrones seguidos, con la finalidad de incrementar la inteligencia de negocio.

Partes de un Grafo: Aristas: Son las líneas con las que se unen dos vertices 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. 

Ejemplo de Arista:

Aristas Adyacentes: Se dice que dos aristas son adyacentes si convergen en el mismo vértice. 

Ejemplo de Arista Adyancente:

Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial y el final son el mismo. 

Ejemplo de Aristas Paralelas:

Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo. 

Ejemplo de Aristas Cíclicas:

Cruce: son intersecciones de las aristas en puntos diferentes a los vértices. 

Ejemplo de Cruce:

Vértices: Son los puntos o nodos con los que está 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. 

Ejemplo de Vértice:

Vértice Adyacente: 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. Los vértices son adyacentes si están unidos mediante una arista. 

Ejemplo de Vértice Adyacente:

Vértice Aislado: Es un vértice de grado cero. 

Ejemplo de Vértice Aislado.

Vértice Terminal: Es un vértice de grado 1. 

Ejemplo de Vértice Terminal.

Caminos: Se llama camino a una secuencia de vértices de un grafo tal que exista una arista, cada vértice y el siguiente. Se dice que dos vértices están conectados si existe un camino que vaya de uno a otro, de lo contrario estarán desconectados. 

Ejemplo de Camino:

Grafo Dirigido: Un grafo dirigido o dígrafo es un tipo de grafo en el cual las aristas tienen una dirección definida, a diferencia del grafo generalizado, en el cual la dirección puede estar especificada o no. Al igual que en el grafo generalizado, el grafo dirigido está definido por un par de conjuntos

, donde: , un conjunto no vacío de objetos simples llamados vértices o nodos. , es un conjunto de pares ordenados de elementos

De denominados aristas o arcos, donde por definición un arco va del primer nodo (a) al segundo nodo (b) dentro del par. Por definición, los grafos dirigidos no contienen bucles (lazos).

Cada arista del grafo dirigido incluye una flecha para indicar la dirección. La punta de cada flecha representa el segundo nodo del par ordenado de nodos que constituye un arco y la cola de la flecha representa el primer nodo del par. Grafo no Dirigido: Un grafo no dirigido o grafo propiamente dicho es un grafo

donde:

, es un conjunto de pares no ordenados de elementos de . Un par no ordenado es un conjunto de la forma

, de manera que

los grafos, estos conjuntos pertenecen al conjunto de potencia de , denotado cardinalidad 2.

Grafo Mixto: Un grafo mixto es aquel que se define con la capacidad de poder contener aristas dirigidas y no dirigidas. Tanto los grafos dirigidos como los no dirigidos son casos particulares de este.

Multígrafo o Pseudo Grafo: Un multígrafo o pseudografo 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 multígrafo G es un par G:=(V, E) donde:

. Para , y son de

•

V es un conjunto de vértices o nodos

•

E es un multiconjunto de pares no ordenados de nodos, llamados aristas o líneas.

•

V es un conjunto de vértices o nodos

• A es un multiconjunto de pares ordenados de nodos, llamados aristas dirigidas, arcos o flechas. Grafos particulares: Existen grafos que poseen propiedades destacables. Algunos ejemplos básicos son: Grafo nulo: aquel que no tiene vértices ni aristas. Nótese que algunas personas exigen que el conjunto de vértices no sea vacío en la definición de grafo. Grafo vacío: aquel que no tiene aristas. Grafo trivial: aquel que tiene un vértice y ninguna arista. Grafo simple: aquel que no posee bucles ni aristas paralelas. Consultar variantes en esta definición. Multigrafo (o pseudografo): G es multigrafo si y solo si no es simple. Consultar variantes en esta definición. Grafo completo: grafo simple en el que cada par de vértices están unidos por una arista, es decir, contiene todas las posibles aristas. Grafo Bipartito:

Grafo Bipartido Completo:

Grafo plano: aquel que puede ser dibujado en el plano cartesiano sin cruce de aristas. Árbol: grafo conexo sin ciclos. Grafo rueda: grafo con n vértices que se forma conectando un único vértice a todos los vértices de un ciclo-(n-1). Grafo perfecto: aquel que el número cromático de cada subgrafo inducido es igual al tamaño del mayor clique de ese subgrafo.

Propiedades: 1. Adyacencia: dos aristas son adyacentes si tienen un vértice en común, y dos vértices son adyacentes si una arista los une. 2. Incidencia: una arista es incidente a un vértice si ésta lo une a otro. 3. Ponderación: corresponde a una función que a cada arista le asocia un valor (costo, peso, longitud, etc.), para aumentar la expresividad del modelo. Esto se usa mucho para problemas de optimización, como el del vendedor viajero o del camino más corto. 4. Etiquetado: distinción que se hace a los vértices y/o aristas mediante una marca que los hace unívocamente distinguibles del resto. Definición de Dígrafo: Según la Academia, un dígrafo es un grupo de dos letras que representa un único sonido. El sistema de representación gráfico del español cuenta con cinco dígrafos: ch (que representa el fonema africado palatal sordo), ll (que representa el fonema lateral palatal), rr (que representa el fonema vibrante múltiple), qu (que representa ante las vocales e, i el fonema velar sordo) y gu (que representa delante de e, i el fonema velar sonoro). En la actualidad y según la Ortografía del 2010, ningún dígrafo forma parte del alfabeto, de modo que la ch y la ll no se consideran letras. Estos dos dígrafos habían tenido tradicionalmente la consideración de letras porque, a diferencia de lo que ocurre con los otros dígrafos, son la única representación gráfica posible de los fonemas que representan. La rr también es un dígrafo (son dos letras, no una) aunque representa un único fonema (el vibrante múltiple de perro o carro). Pero, a diferencia de lo que ha ocurrido con la ch y la ll, el dígrafo rr no se ha considerado tradicionalmente una letra del abecedario o alfabeto (en España; en América sí ha sido habitual). Esto ha ocurrido así seguramente porque el mismo fonema vibrante múltiple se representa también con otro signo, la r (en palabras como ratón, Enrique o alrededor). En español se emplean 5 dígrafos para representar diversos fonemas: «ch», «ll», «rr», «gu» y «qu», considerados estos dos últimos como variantes posicionales para los fonemas /g/ y /k/.4 Los dígrafos ch y ll tienen valores fonéticos específicos, por lo que en la Ortografía de la lengua española de 1754 comenzaron a ser considerados como letras del alfabeto español5 y a partir de la publicación de la cuarta edición del Diccionario de la lengua española en 180367 se ordenaron separadamente de c y l,8 y fue durante el X Congreso de la Asociación de Academias de la Lengua Española celebrado en Madrid en 1994, y por recomendación de varios organismos, que se acordó reordenar los dígrafos ch y ll en el lugar que el alfabeto latino universal les asigna, aunque todavía seguían formando parte del abecedario.9 Con la publicación de la Ortografía de la lengua española de 2010, ambas dejaron de considerarse letras del abecedario.10 Los dígrafos en español restantes son qu y gu (delante de e o ante i) y rr. Un caso curioso en nuestro idioma es el referente al sonido representado por letra Ñ (evolución del nn latino), cuya

fonética en otros idiomas se representa como dígrafo (Nh en portugués, Ny en catalán, o Gn en francés e italiano). En polaco normalmente se la escribe con una sola letra (Ń), aunque delante de vocales pierde el acento, que se substituye por una I (NI), por lo cual se convierte en dígrafo. El idioma con mayor número de dígrafos en España es el catalán: más de diez (la cantidad exacta depende del dialecto del catalán utilizado). 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. Un camino simple es aquel que no repite vértices en su recorrido. 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 Euleriano: Un camino euleriano en un grafo es un camino que usa cada arista una y sólo una vez. Si existe tal camino decimos que el grafo es euleriano. Esta definición es dual a la de camino hamiltoniano.

Camino hamiltoniano: Existe un concepto dual al de camino/ciclo Euleriano. Un camino hamiltoniano en un grafo es un camino que "visita" cada vértice una y sólo una vez.

Ciclo: Un Ciclo (o circuito) es un camino que empieza y acaba en el mismo vértice. Los ciclos de longitud 1 se denominan lazos o bucles.

Un ciclo simple es un ciclo que tiene como longitud al menos 3 y en el que el vértice inicial coincide con el vértice final.

Ciclo euleriano: Un ciclo euleriano en un grafo es un ciclo que usa cada arista una y sólo una vez.

Ciclo hamiltoniano: Un ciclo hamiltoniano en un grafo es un ciclo que visita cada vértice una y sólo una vez.

Circunferencia: La circunferencia de un grafo es la longitud de su ciclo simple más largo.

Isomorfismo de Grafos: Se dice que dos grafos son isomorfos si y solo si se preserva la relación de adyacencia entre ambos. Por ejemplo, tenemos el siguiente grafo:

Entonces suponemos que el conjunto K={A,B,C,D,E} (donde cada una de las letras representa los vértices del grafo) posee una función f(v), la cual tiene como imagen al conjunto K'={A',B',C',D',E'}. Para que el grafo que tiene como vértices el conjunto K' sea isomorfo, este debe tener las mismas relaciones de adyacencia de K. En otras palabras, por ejemplo, en K tenemos una arista D-E,

entonces en K' tendríamos una arista D'-E'. Así para todos los vértices de K'. Entonces, un grafo isomorfo al anterior (El formado por los vértices incluidos en el conjunto K) seria:

Subgrafos: Un subgrafo se define como un grafo con vértices y aristas que son un subconjunto de un grafo padre. Un problema común en la lógica computacional es el Problema de isomorfismo de Subgrafos, en el mismo se tiene dos grafos G1 y G2, y se desea saber si existe un subgrafo en G2 que sea isomorfo a G1. Consideremos los siguientes grafos, el grafo G1 sería el siguiente:

El grafo G2 sería el siguiente:

Entonces, en este caso se podría decir que la respuesta al problema es afirmativa, ya que las aristas entre los vértices A', B' y C' formarían un subgrafo que es isomorfo a G1. En caso de no existir este subgrafo isomorfo, la respuesta seria obviamente negativa.