Grafos en estadistica

GRAFOS

En la lingüística, un grafo es la unidad abstracta que comprende el conjunto de grafías de una letra. La palabra tiene origen griego y significa “dibujo” o “imagen”.
[pic]
Para las matemáticas y las ciencias de la computación, un grafo es el principal objeto de estudio de la teoría de grafos. De esta forma, un grafo se representa gráficamente como un conjunto de puntos (llamadosvértices o nodos), unidos por líneas (aristas). Los grafos permiten estudiar las interrelaciones entre unidades que se encuentran en interacción.
Los especialistas consideran que el primer resultado de la teoría de grafos fue la respuesta de Leonhard Euler sobre el problema de los puentes de Königsberg, en 1736. Este trabajo también se considera como uno de los primeros resultados topológicos engeometría.
Los grafos pueden ser simples (cuando sólo una arista une dos vértices cualesquiera) o complejos. Los grafos simples están formados por dos conjuntos: el conjunto V de vértices o nodos y el conjunto de pares de vértices que se llaman aristas o arcos y que señalan qué nodos están relacionados.
Por otra parte, un grafo es conexo si cada par de vértices está conectado por un camino. Porejemplo: para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b.
En cambio, un grafo es fuertemente conexo si cada par de vértices está conectado por, al menos, dos caminos disjuntos.
Un grafo simple es completo si existen aristas uniendo todos los pares posibles de vértices, mientras que un grafo es bipartito si sus vértices son la unión de dos grupos de vértices,bajo una serie de condiciones.
En la teoría de grafos, los vértices son las unidades fundamentales que componen los grafos. Los grafos no dirigidos están compuestos por vértices y aristas (pares no ordenados de vértices), mientras que los grafos dirigidos se componen de vértices y arcos (pares ordenados de vértices).

También un grafo es una terna G = (V,A,j ), en donde V y A son conjuntosfinitos, y jes 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.

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 denotaindistintamente {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 unvé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 quelos 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.
•

Caminos

Sean x, y " V, se dice que hay un camino en G de x a y si existe una sucesión finita no vacía de aristas {x,v1}, {v1,v2},..., {vn,y}. En este caso

• x e y se llamanlos extremos del camino
•

• El número de aristas del camino se llama la longitud del camino.
•

• Si los vértices no se repiten el camino se dice propio o simple.
•

• Si hay un camino no simple entre 2 vértices, también habrá un camino simple entre ellos.
•

• Cuando los dos extremos de un camino son iguales, el camino se llama circuito o camino cerrado.
•

• Llamaremos ciclo a...