arboles y grafos

Grafos.

Un Grafo (o grafo no dirigido) es un conjunto V de vértices y un conjunto E de aristas tales que cada arista e ? E(queda asociada a un par no ordenado de vértices. Si existe una única arista e asociada con los vértices v y w, escribimos e = (v,w). En este contexto (v,w) denota una arista en un grafo no dirigido y no un par ordenado.
Un grafo dirigido (o digrafo) consta de un conjuntofinito de vértices V y un conjunto de arcos E ? V × V (obsérvese que cada arco es un par ordenado de vértices).
Grafo conexo: un grafo G es conexo si dados cualesquiera dos vértices v y w en G, existe un camino de v a w.
Camino: sean v0 y vn vértices de un grafo. Un camino de v0 a vn de longitud n es una sucesión alternante de n+1 vértices y n aristas que comienza con el vértice v0 y terminacon el vértice vn.
Longitud del camino: es el número de aristas que contiene.
Ciclo: sean v y w vértices en un grafo G, un ciclo o circuito es un camino de longitud distinta de 0 de v a w, sin aristas repetidas.
Subgrafo: sea G (V, E) un grafo. (V", E") es un subgrafo de G si
a) V" ( V y E"( E.
b) Para cada arista e" ( E", si e" es incidente en v" y w", entonces v", w" ( V.
Grafo con pesos (opoderado): es un grafo en el cual se le asignan valores a las aristas y la longitud del camino de un grafo con pesos es la suma de todos los pesos de las aristas en la ruta (camino).
Árbol: es un grafo en el que cualesquiera dos vértices están conectados por exactamente un camino.
GRAFO

Es un conjunto de puntos y un conjunto de líneas, cada una de las cuales une un punto con otro. Los puntosse llaman nodos o vértices de un grafo y las líneas se llaman aristas o arcos.

¿QUÉ ES UN NODO?
Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o más nodos hijos conectados a él.
      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 sicoinciden 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. 


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.

CLASIFICACION DE LOS GRAFOS* DIRIGIDOS
Cada arco esta representado por un par ordenado de vertices, de forma que representan dos arcos diferentes.
* NO DIRIGIDOS
En este el par de vertices que representa un arco no esta ordenado

TIPOS DE GRAFOS

    Grafo regular: Aquel con el mismo grado en todos los vértices.
    Grafo bipartito: Es aquel con cuyos vértices pueden formarse dos conjuntos disjuntos de modo que nohaya adyacencias entre vértices pertenecientes al mismo conjunto
   Grafo completo: Aquel con una arista entre cada par de vértices
   Grafo nulo: Se dice que un grafo es nulo cuando los vértices que lo componen no están conectados, esto es, que son vértices aislados.
  Grafos Isomorfos: Dos grafos son isomorfos cuando existe una correspondencia biunívoca (uno a uno), entre sus vértices de talforma que dos de estos quedan unidos por una arista en común.
      Grafos Platónicos: Son los Grafos formados por los vértices y aristas de los cinco  sólidos regulares      (Sólidos Platónicos), a saber, el tetraedro, el cubo, el octaedro, el dodecaedro y el icosaedro
       Grafos conexos:  Un grafo se puede definir como conexo si cualquier vértice V pertenece al conjunto de vértices y es...