historiaa

6.1.1 componentes de un grafo
Elementos y características de los grafos.
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 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.
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 denota indistintamente {a, b} o {b, a}, siendo a yb 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 un vértice para entrar en el mismo.
-Cruce: Son dos aristasque cruzan en un punto.
Lazo:
Un lazo o bucle es una arista que relaciona al mismo nodo; es decir, una arista donde el nodo inicial y el nodo final coinciden.
Es aquella arista que sale de un vértice y regresa al mismo vértice. En el grafo anterior se tiene el lazo: A={6}
Valencia:
Es el numero de lados que salen o entran a un vértice. En el grafo anterior las valencias de los vértices son:Valencia (a)=2
Valencia (b)=4
Valencia (c)=2
Valencia (d)=3
Hay que observar como en el caso del vértice de el lazo solo se considera una vez, entrada o salida pero no ambos.


6.1.2 Tipos de grafos
Simples:
Un grafo es simple si a lo sumo sólo 1 arista une dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos.
Ungrafo que no es simple se denomina Multigráfica o Gráfo múltiple.
Son aquellos grafos que no tienen lazos ni lados paralelos.
Completos:
Un grafo es completo si existen aristas uniendo 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 , siendo  el grafo completo de nvértices.
Un es decir, grafo completo de n vértices tiene exactamente aristas.

Bipartidos:
Un grafo G es bipartito si puede expresarse como G = \{V_1 \cup V_2, 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 deV1; análogamente para V2.
Bajo estas condiciones, el grafo se considera bipartito, y puede describirse informalmente como el grafo que une o relaciona dos conjuntos de elementos diferentes.
Planos:
En teoría de grafos, un grafo plano (o planar según referencias) es un grafo que puede ser dibujado en el plano sin que ninguna arista se cruce (una definición más formal puede ser que este grafopueda ser "incrustado" en un plano). Los grafos K5 y el K3,3 son los grafos no planos minimales, lo cual nos permitirán caracterizar el resto de los grafos no planos.
Todo grafo plano puede ser dibujado sobre la esfera, y viceversa. Una generalización de los grafos planos son grafos dibujados e incrustados sobre superficies de genero arbitrario. En esta terminología, los grafos planos tienen genero0, por ser el plano y la esfera de genero 0
Conexos:
La teoría de grafos (también llamada teoría de las gráficas) es un campo de estudio de lasmatemáticas y las ciencias de la computación, que estudia las propiedades de los grafos(también llamadas gráficas) estructuras que constan de dos partes, el conjunto de vértices, nodos o puntos; y el conjunto de aristas, líneas o lados (edges en...