gafos






¿QUE E UN GRAFO?
Un grafo G se define como un par (V; E), donde V es un conjunto cuyos elementos son denominados vértices o nodos y E es un subconjunto de pares no ordenados de vértices y que reciben el nombre de aristas o arcos.
Si V = {U1,…, Un}, los elementos de E se representa de la forma, {Ui,…, Uj}, donde, i# j. Los elementos de una arista o arco se denominan extremos de dichaarista.
Componentes de un grafo (vértices, aristas, lazos, valencia).

Aristas.- Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos.
Aristas Adyacentes: Se dice que dos aristas son adyacentes si coinciden en el mismo vértice.
Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial y el final son el mismo.
AristasCíclicas: Arista que parte de un vértice para entrar en el mismo.

Cruce: Son dos aristas que cruzan en un puntos.

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.
Vértices Adyacentes: si tenemos un par de vértices de un grafo (U, V) y sitenemos 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: es una arista cuyos extremos inciden sobre el mismo vértice
Valencia de un vértice.- Es el número de lados que salen o entran a un vértice.


Tipos de grafos(Simples, completos, bipartidos, planos, conexos, ponderados)

            Grafos simples.- Un grafo es simple si a lo más existe una arista uniendo dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos. Un grafo que no es simple se denomina multígrafo.

Grafo completo.- Un grafo es completo si existen aristasuniendo todos los pares posibles de vértices. Es decir, todo par de vértices (a, b) debe tener una arista e que los une. El conjunto de los grafos completos es denominado usualmente K, siendo Kn  el grafo completo de n vértices. Un Kn, es decir, grafo completo de n vértices tiene exactamente n(n-1)/2  aristas.

La representación gráfica de los  como los vértices de un polígono regular da cuenta de su peculiarestructura.

Grafos bipartitos.- Un grafo G es bipartito si puede expresarse como G = {V1 U V2, A} (es decir, sus vértices son la unión de dos grupos de vértices), bajo las siguientes condiciones:
V1 y V2  son disjuntos y no vacíos.
Cada arista de A une un vértice de V1 con uno de V2.
No existen aristas uniendo dos elementos de V1; análogamente para V2.
Bajo estas condiciones, el grafo seconsidera bipartito, y puede describirse informalmente como el grafo que une o relaciona dos conjuntos de elementos diferentes, como aquellos resultantes de los ejercicios y puzzles en los que debe unirse un elemento de la columna A con un elemento de la columna B.



Grafos Planos.- Un grafo G es planar si admite una representación en el plano de  tal forma que las aristas no se cortan, salvo ensus extremos. A dicha representación se le denomina grafo plano. Se dice que un grafo es plano si puede dibujarse en el plano de manera que ningún par de sus aristas se corte. A ese dibujo se le llama representación plana del grafo.


Grafo conexo.- Un grafo se dice que es conexo si cada par de sus vértices están conectados. Es decir, G es conexo ⇐⇒ ∀u, v : ∃µ = [u, v]
En caso contrario,diremos que G es un grafo desconexo.



 Ejemplo
¿Cuál de los grafos siguientes es conexo?
a.- Conexo. 
b.- Conexo.
c.- No es conexo.

Grafos ponderados.- Llamamos grafos ponderados a los grafos en los que se asigna un número a cada una de las aristas. Este número representa un peso para el recorrido a través de la arista. Este peso podrá indicar, por ejemplo, la distancia, el costo...