Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

TEORIA Y EJEMPLO DE GRAFOS

No description
by

solangel vera

on 9 October 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of TEORIA Y EJEMPLO DE GRAFOS

TEORIA Y EJEMPLO DE GRAFOS
EJEMPLO DE UN PROBLEMA REPRESENTADO EN GRAFO
Un arquitecto quiere hacer los planos de una casa que contenga 3 habitaciones, sala, cocina, comedor, baño, cuarto de lavado, pero el arquitecto quiere que la casa tenga una característica principal que la sala tenga conexión a todas las habitaciones
(A) habitación 1, (B) habitación 2
(C) habitación 3, (D) sala
(E) cocina, (F) comedor
(G) baño, (H)cuarto de lavado
-Dibuje la representación mediante un grafo
-Identifique las partes del grafo
-Identifique que tipo de grafo es
-Realizar sus respectivas matrices
-Escriba la relaciones para ser grafo complemento
Partes del grafo:
Vértices: {A,B,C,D,E,F,G,H}
Aristas: {1,2,3,4,5,6,7,8,9,10,11,12,13,14}
Valencia: (A)=3, (B)=3,(C)=3,(D)=7,(E)=3,(F)=3,(G)=3,(H)=3.
Tipo de grafo:
No dirigido: por que no tienen asociada una dirección
Simple:por que no tiene lazos ni lados paralelos


Matrices
ss
Un arquitecto quiere hacer los planos de una
casa que contenga 3 habitaciones, sala, cocina, comedor, baño, cuarto de lavado, pero el arquitecto quiere que la casa tenga una característica principal que la sala tenga conexión a todas las habitaciones
(A) habitación 1, (B) habitación 2
(C) habitación 3, (D) sala
(E) cocina, (F) comedor
(G) baño, (H)cuarto de lavado
adyacencia

incidencia
VERA ESPINOZA SOLANGEL
Grafo Complemento
R=(A,B) R=(B,A) R=(C,G) R=(E,A) R=(F,A) R=(G,C) R=(H,E)
R=(A,H) R=(B,C) R=(C,H) R=(E,G) R=(F,B) R=(G,E) R=(H,C)
R=(A,F) R=(B,E) R=(C,F) R=(E,B) R=(F,C) R=(G,F) R=(H,A)
R=(A,E) R=(B,F) R=(C,E) R=(E,H) R=(F,G) R=(G,H) R=(H,G)
ALGORITMO DEL CIRCUITO DE EULER
1-Verificar que el grafo sea conexo y que todos sus vértices tengan valencia par:
-Es un grafo conexo por que todos sus vértices están conectados
-Tiene valencia par

2-Si cumple con la condición anterior seleccionar un vértice arbitrario para iniciar el recorrido
-considere que se inicia el recorrido en el vértice A

CIRCUITO DE EULER
3-Hay que escoger una arista a partir del vértice actual y esa arista no debe de ser lado puente:
-se puede seleccionar cual quier arista del grafo ya que ninguna es lado puente
4-Registre como parte del circuito de euler de dicha arista:
(A,D)
ALGORITMO DE CIRCUITO DE EULER
(A,D)
(D,E)
(F,B)
(B,D)
(D,C)
Algoritmo de circuito de euler
5-si todos los vértices ya están desconectados ya se tiene el circuito de euler y finalizar
Full transcript