Trabajos

Universidad pedagógica experimental libertador.
Instituto Pedagógico Rural “El Mácaro”.
Cede: San Juan de los morros.
Informática 2009-II.
Estado Guárico.

Matemática Discreta

Profesor: Integrante:
José Luis FríasSoto Maria: 19.943.968

“San Juan de los Morros”

Grafos.
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 delados del grafo G. Además º(G) y "(G) denotan el numero de vértices y el numero 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últiplesy/o lazos decimos que G es un multígrafo. 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. Los lados 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.

V = {a, b, c, d, e, f}, y A = {ab,ac, ae, bc, bd, df, ef}.

Grado de los Vértices
Dos vértices u, v de un grafo G = (V,E) se dicen adyacentes si {u, v}E, asimismo dos aristas son adyacentes si tienen un mismo vértice como extremo; análogamente si e = {u,v} decimos que el lado e es incidente a los vértices u y v. El grado de un vértice es el numero de lados incidentes a él. El grado de un vértice u se denota gr(u). Denotamos con±(G) y ¢(G) el mínimo y el máximo grado de los vértices de G respectivamente.

En un dígrafo distinguimos entre grado entrante (indegree) y grado saliente (outdegree) de u, el primero indica el numero de lados que tienen al vértice u como terminal y el segundo indica el numero de lados que tiene al vértice u como inicial, y se denotan gr−(u) y gr+(u) respectivamente.

Representaciones de losgrafos
Sea G = (V,E) un grafo con º vértices y " aristas, entonces le corresponde una matriz × " denominada la matriz de incidencia de G. Si denotamos 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 el vértice vi; los valores son 0,1 o 2 (2en el caso que la arista sea un lazo).
Otra matriz asociada a G es la matriz de adyacencia, esta es una matriz º ׺ A(G)[aij ], en donde aij es el numero de aristas que van de vi hasta vj .
A continuación damos un ejemplo de un grafo con su correspondiente matriz de incidencia y matriz de adyacencia.

Caminos y Ciclos
Se distingue entre cadenas (chains) y caminos (path), usando el primertermino para grafos y el segundo para dígrafos. Una sucesión alternada de vértices y lados u1, e1, u2, e2, . . . , ek, uk+1 tal que ei = [ui, ui+1] se denomina cadena en un grafo y camino en un dígrafo.
Los caminos deben realizarse de acuerdo a la dirección de los lados. Si no existen lados múltiples podemos denotar sin ambigüedad la cadena como una sucesión de vértices (vértices consecutivosadyacentes). Una cadena es cerrada si el vértice inicial y final es el mismo. La cadena cerrada es un ciclo si todos los vértices (excepto los extremos) son distintos. El camino cerrado es un circuito si todos los vértices (excepto los extremos) son distintos.

Grafos Etiquetados y Ponderados
Aunque ya hemos usado los grafos etiquetados, damos una definición en esta sección. Un grafo G es un grafo...