teoria de grafos

Grafo: 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.
Grafo simple: Un grafo simple G(V,E) consta de V , un conjunto no vacío de vértices, y de E, un conjunto de pares no ordenadosde elementos distintos de V . A esos pares se les llama aristas o lados.
Subgrafo: Sea G = (V,E) un grafo. Si H = (W,F) es un grafo tal que W ⊆ V y F ⊆ E decimos que H es un subgrafo de G. Si Fcontiene todos los lados de E que unen a los puntos de W en G se dice que H es un subgrafo completo de G generado por W. Si W = V decimos que H es un subgrafo extendido de G
Ejemplo:

v1 vb10 bv9
v4v7 v4 v7
G G1
v1 vb8 v1 bv9 vb10
v4 v7 v4 v7
G2 G3
El grafo G1 es un subgrafo de G, el grafo G2 es un subgrafo completo de G y el grafo G3 es un subgrafo extendido de G.
Grafo bipartito: Sedice que un grafo simple G = (V,E) es bipartito si el conjunto de vértices V se puede dividir en dos conjuntos disjuntos V1,V2, (V1 ∪ V2 = V, V1 ∩ V2 = ∅, de tal manera que toda arista e ∈ E conecta unvértice de V1 con un vértice de V2.
Esto significa que el subgrafo completo generado por V1 es libre de lados; asimismo el subgrafo completo generado por V2.

G1 G2
Ejemplos de grafos bipartitosUn subgrafo bipartito se dice completo si cada vértice de V1 está conectado a todos los vértices de V2; si |V1| = n y |V2| = m este grafo se denota Km,n
b b b b

K2,3 K3,3 K2,4
Grado de unvértice, adyacencia de un grafo:

Representación de los grafos: Sea G = (V,E) un grafo con ν vértices y ε aristas, entonces le corresponde una matrizν × ε denominada la matriz de incidencia de G. Sidenotamos los vértices de G por v1,v2,...,vν y las aristas por e1,e2,...,eε. Entonces la matriz de incidencia de G es la matriz M(G) = [mij] donde mij es el número de veces que la arista ej incide en...