Teoria de grafos

Solo disponible en BuenasTareas
  • Páginas : 11 (2592 palabras )
  • Descarga(s) : 0
  • Publicado : 26 de noviembre de 2010
Leer documento completo
Vista previa del texto
MINISTERIO DE EDUCACION DEL PODER POPULAR PARA LA EDUCACION SUPERIOR INSTITUTO UNIVERSITARIO DE TECNOLOGIA AGRO-INDUSTRIAL SAN CRISTÓBAL-ESTADO TÁCHIRA DEPARTAMENTO DE INFORMÁTICA – PNF INGENIERIA EN INFORMATICA Matemática Aplicada – Módulo Matemática Discreta

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...
tracking img