Grafos

 
Grafos. Conceptos fundamentales
Un grafo G es un par G = (V, E), donde V es un conjunto finito (vértices, nodos) y E es un multiconjunto de pares no ordenados de vértices, denotados por {x, y},que se denominan lados, aristas, etc. En este caso decimos que x y y son extremos de {x, y}. Denotamos V (G) por el conjunto de vértices del grafo G y por E(G) el conjunto de lados del grafo G. Ademásν(G) y ε(G) denotan el número de vértices y el número de aristas de G respectivamente.
Puesto que E es un multiconjunto es posible que existen pares repetidos, en este caso G tiene lados múltiples.También es posible que algún par no ordenado de E tenga el mismo vértice repetido, en este caso decimos que el lado es un lazo (loop) o bucle. Cuando existen lados múltiples y/o lazos decimos que G es unmultigrafo. Si no hay lados múltiples ni lazos decimos que es un grafo simple. Un dígrafo G es un par G = (V, E) donde V es un conjunto de vértices y E es un multiconjunto de pares ordenados. Loslados se denotan por pares ordenados, (u, v) denota el lado dirigido que tiene como vértice inicial a u y como vértice terminal a v.

Grafos Regulares
Un grafo G = (V, E) es regular de grado k ok-regular si cada vértice tiene grado k; es decir, un grafo es regular si todos los vértices tienen el mismo grado.






Grafos planos
En teoría de grafos, un grafo plano es un grafo que puedeser dibujado en el plano sin que ninguna arista se cruce (una definición más formal puede ser que este grafo pueda ser "incrustado" en un plano). Los grafos K5 y el K3,3 son los grafos no planosminimales, 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 grafosdibujados e incrustados sobre superficies de género arbitrario. En esta terminología, los grafos planos tienen genero 0, por ser el plano y la esfera de género 0





Grafos Bipartitos

Se...