teoria de grafos






















Profesor: Integrantes:

Caracas, Diciembre de 2013
Definiciones
Grafos: En la Lingüística, un grafo es un unitario de naturaleza abstracta que abarca a las graficas que componen una letra. La palabra tiene origen griego ysignifica “imagen” o “dibujo”.
Para las ciencias de la computación y la matemática, un grafo es una representación gráfica de diversos puntos que se conocen como nodos o vértices, los cuales se encuentran unidos a través de líneas que reciben el nombre de aristas o arcos. Al analizar los grafos, los expertos logran conocer cómo se desarrollan las relaciones recíprocas entre aquellas unidades que mantienen algún tipo deinteracción.
Grafo Dirigido: es un tipo de grafo en el cual el conjunto de las aristas tiene una dirección definida, a diferencia del grafo generalizado, en el cual la dirección puede estar especificada o no.
Un grafo dirigido está definido por un par de conjuntos G= (V, A), donde:
V ≠ 0, un conjunto no vacío de objetos simples llamados vértices o nodos.
E{(a,b) V x V: a ≠ b} es un conjuntode pares ordenados de elementos de V  denominados aristas o arcos, donde por definición un arco va del primer nodo (a) al segundo nodo (b) dentro del par.
Grafo no Dirigido: Es aquel que no tiene un orden específico como el grafo dirigido que se le asigna a un orden a sus extremos con una flecha.
Un grafo no dirigido o grafo propiamente dicho es un grafo G= (V, E) donde:
V≠0
E{ (V):=2} es unconjunto de pares no ordenados de elementos de V.
Un par no ordenado es un conjunto de la forma {a,b}, de manera que {a,b}= {b,a}. Para los grafos, estos conjuntos pertenecen al conjunto potencia de V de cardinalidad 2, el cual se denota por (V)

Propiedades
Adyacencia: dos aristas son adyacentes si tienen un vértice en común, y dos vértices son adyacentes si una arista los une.
Incidencia: unaarista es incidente a un vértice si ésta lo une a otro.
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.
Etiquetado: distinción que se hace a los vértices y/o aristas mediante una marca que los hace unívocamente distinguibles del resto.
Vértices y Aristas
Vértice: un vértice o nodo es la unidadfundamental de la que están formados los grafos.  Son tratados como objetos indivisibles y sin propiedades, aunque puedan tener una estructura adicional dependiendo de la aplicación por la cual se usa el grafo
Arista: Son las líneas con las que se unen los vértices de un grafo y con la que se construyen también caminos. Se clasifican en:
Aristas Adyacentes: Se dice que dos aristas son adyacentessi 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.

Grado de un Vértice: Es el número de aristas incidentes a él.
Vértice aislado es un vértice con grado cero; esto es, un vértice que noes punto final de ninguna arista.
Vértice hoja es un vértice con grado uno. En un grafo dirigido, se puede distinguir entre grado de salida y grado de entrada.
Vértice fuente es un vértice con grado de entrada cero.
Vértice hundido es un vértice con grado de salida cero.

Representaciones
Representación Grafica
Consiste en un gráfico en que los vértices se representan mediantes puntos. Enfunción del tipo de grafo que se tenga, ocurre:
Los vértices se unen mediantes segmentos si el grafo es no orientado.
Los Vértices se unen mediantes flechas indicando el vértice origen y final si el grafo es orientado.


Grafo no Dirigido Grafo Dirigido
Representación Relacional
Se basa en la aplicación de...