Teoria de grafos
UNIDAD III TEORIA DE GRAFOS – TALLER UNIDAD III
Grafo: Un grafo G, se define como un dibujo, imagen, gráfico. Es la representacióngráfica de un conjunto de puntos (nodos o vértices), unidos por líneas (aristas) Tiene entonces dos partes: a.-Un conjunto V= V(G) cuyos elementos son los vértices del grafo G b.-Una colección E = E(G) de pares desordenados de vértices llamados aristas Se escribe entonces G(V,E) cuando se hace referencia a ambas partes de G Multígrafo: Un multigrado G= G(V,E) consiste también en un conjunto V devértices y E de aristas excepto que E puede contener aristas múltiples, es decir, aristas que conectan a los mismos extremos o aristas cuyos extremos son el mismo vértice (bucles) Grafo trivial: aquel que solo tiene un vértice Grafo nulo: aquel que ni tiene vértices, ni tiene aristas
Figura 1 Descripción formal del grafo de la figura 1 Grafo G(V,E) donde V= {A,B,C,D} y E={e1, e2, e3, e4 e5} dondee1={A,B}, e2={B,C}, e3={C,D}, e4={A,C}, e5={B,D}.
figura 2 José Javier García C. Matemática Discreta – IUTAI – PNFI Página1
¿La figura 2 es un grafo o multigrado? Es un multigrado ya que G tiene múltiples aristas que conectan a los vértices A,C y además un bucle e7. 1.- Describa formalmente el siguiente grafo de la figura 3
figura 3
2.-En el siguiente multigrado G (figura 4), halle:figura 4 a.- el numero de aristas y vértices:
b.- Si hay aristas múltiples o bucles diga cuales son::
3.-Dibuje un diagrama para cada uno de los grafos siguientes G(V,E): a.- V={A,B,C,D} , E= [{A,B},{D,A},{C,A},{C,D}] b.- V= {a,b,c,d,e,f} E=[{a,d},{a,f},{b,c},{b,f},{c,e}]
José Javier García C.
Matemática Discreta – IUTAI – PNFI
Página2
4.-Dibuje un diagrama para cada uno delos siguientes grafos G (V,E) , donde V= {P1,P2,P3,P4,P5}, y a.- E=[{P2,P4},{P2,P3},{P3,P5},{P5,P4}] b.- E=[{P1,P1},{P2,P3},{P2,P4},{P3,P2},{P4,P1},{P5,P4}]
5.-En el grafo anterior (el dibujado) ¿hay un vértice aislado? ¿Cuál?
6.-Determine SI cada uno de los multigrados siguientes grafo, donde V= {A,B,C,D} y a.- E= [{A,B},{A,C},{A,D},{B,C},{C,D}] (Grafo) b.- E= [{A,B},{B,B},{A,D}] (Grafo) c.-E= [{A,B},{C,D},{A,B},{B,D}] (Grafo) d.- E= [{A,B},{B,C},{C,B},{B,B}] (Grafo)
G(V,E), es o no un
(Multígrafo) (Multígrafo) (Multígrafo) (Multígrafo)
Nota: Recuerde que G(V,E) es un grafo si no tiene aristas múltiples o bucles. 7.-Describa formalmente el grafo que se muestra a continuación(figura 5):
figura 5
Adyacencia e incidencia en un grafo Suponga que e={u,v} es una arista de G,es decir, que u y v son extremos de e. entonces se dice que el vértice u es adyacente al vértice v, y que la arista e es incidente sobre u y sobre v. José Javier García C. Matemática Discreta – IUTAI – PNFI Página3
Grado de un vértice g(v) Es determinado por el numero de aristas que inciden en v, (el numero de aristas que tienen a v como extremo), se dice que el vértice v es par o impar segúng(v) lo sea. Teorema A: La suma de los grados de los vértices de un grafo es igual a dos veces el número de aristas. Nota: El teorema se cumple en multigrados, y en caso de los bucles se contabilizan dobles. Del siguiente grafo (figura 6): a.-) descríbalo formalmente b.-) halle el grado y paridad de cada vértice c.-) verifique el teorema anterior
figura 6
Considere el multigrafo G dondeV={A,B,C,D}, y E= [{A,C},{A,D},{B,B},{B,C},{C,A},{C,B},{D,B},{D,D}] a.-Halle el grado y la paridad de cada vertice en G b.-Verifique el teorema A
Caminos, Conectividad Un camino α en G con origen v0 y destino vn es una secuencia alterna de vértices y aristas de la forma v0, e1, v1, e2, v2,…,en-1, vn-1, en, vn, donde cada nodo ei incide en los vértices vi-1 y vi. El numero n de aristas se...
Regístrate para leer el documento completo.