Ing. Sistemas

Grafos: En matemáticas y ciencias de la computación, un grafo (del griego grafos: dibujo, imagen) es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, quepermiten representar relaciones binarias entre elementos de un conjunto. Son objeto de estudio de la teoría de grafos.
Típicamente, un grafo se representa gráficamente como un conjunto de puntos(vértices o nodos) unidos por líneas (aristas).
Tipos: Tipos de grafos (Simples, completos, bipartidos, planos, conexos, ponderados)

            Grafos simples.- Un grafo es simple si a lo más existeuna 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 multigrafo.Grafo completo.- 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 losgrafos 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 delos  como los vértices de un polígono regular da cuenta de su peculiar estructura.

Grafos bipartitos.- Un grafo G es bipartito si puede expresarse como G = {V1 U V2, A} (es decir, sus vértices sonla 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 doselementos de V1; 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,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...