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

grafo

No description
by

Yurleidis Vega Villalba

on 14 December 2012

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of grafo

DÍGRAFOS CONEXOS ALGORITMO PARA HALLAR LA CONDENSACION DE UN DIGRAFO DIGRAFO SUBDIGRAFO Los conceptos de ruta, cadena, cadena simple, ruta cerrada, ciclo y ciclo simple dados para grafos son también validos para los dígrafos teniendo en cuenta la orientación de los arcos, estos últimos se llaman ahora ruta dirigida, camino simple, ruta dirigida cerrada, circuito y circuito simple respectivamente. Dado un dígrafo D, el GRAFO SUBYACENTE de D, denotado GD, es el grafo que se obtiene al omitir la orientación de los arcos.

Un dígrafo D es CONEXO (O DÉBILMENTE CONEXO) si el correspondiente grafo subyacente GD es conexo.

Un dígrafo D es FUERTEMENTE CONEXO, si entre todo par de vértices vi y vj de V(D) existe al menos un camino C(vi-->vj), el dígrafo de la figura no es fuertemente conexo ya que por ejemplo no existe ningún camino entre los dos vértices v2 y v4. DIGRAFOS




ADRIANA MARCELA JIMÉNEZ MARTÍNEZ
DUVIER JOSE MARTINEZ ALVAREZ
YURLEIDIS VEGA VILLLALBA
JERSON BETIN PANTOJA
RAMIRO DE AVILA TAPIA
MIGUEL RODRÍGUEZ




TEORIA DE GRAFO



TUTOR:
MSC. MARIO MACEA



UNIVERSIDAD DE CORDOBA
FACULTAD DE INGENIERIA
INGENIERIA DE SISTEMAS
SAHAGÚN
2012 DIGRAFO (Grafo Dirigido) Un dígrafo (o grafo dirigido) D es una terna (V(D); A(D); f(D) donde V(D) es un conjunto no vacío cuyos elementos son llamados vértices, A(D) es otro conjunto, cuyos elementos son llamados aristas, fD es una función de incidencia que asigna a cada arista un par ordenado de vértices. El primer elemento de dicho par es llamado la cola de la arista, el segundo es llamado la cabeza de la arista; tomados en conjunto, estos dos vértices son llamados los extremos de arista. EJEMPLO Dígrafo Vacío se denomina dígrafo vacío, cuando existe un conjunto |V|=n y el conjunto de aristas A(D) es un conjunto vacío y se encuentra denotado por: |V|=n y A(D)= Ø Dígrafo Trivial Dígrafo vacío con un solo vértice donde V(D)={v}. Dígrafo simple Un dígrafo D se denomina simple si no posee ni bucles, ni aristas paralelas. . . Cantidad de arcos que inciden negativamente en el vértice (son las que “Entran” del vértice). Se denota GRADO NEGATIVO DE UN VÉRTICE GRADO POSITIVO DE UN VÉRTICE Cantidad de arcos que inciden positivamente en el vértice (son las que “Salen” del vértice). Se denota = . Es la suma de los grados positivo y negativo. Se denota: GRADO TOTAL Ejemplo de la definición anterior tenemos :






Nótese que la suma de los grafos totales de un dígrafo es igual a dos veces el numero de arcos, es decir: Dígrafos notables EJEMPLO SUBDIGRAFO COBERTOR SUBDIGRAFOS VÉRTICE-DISJUNTOS SUBDIGRAFOS ARCO-DISJUNTOS EJEMPLO CONEXIÓN EN DÍGRAFOS EJEMPLO EJEMPLO EJEMPLO Para hallar la condensación de un dígrafo necesitamos encontrar:

El conjunto de vértices descendentes de cada vértice del dígrafo.
El conjunto de vértices ascendentes de cada vértice del dígrafo.
Los fragmentos que contiene el dígrafo.

Determinación de los conjuntos de vértices descendentes y ascendentes de un vértice.

Sea D = (V, A, fD) un dígrafo. El conjunto de vértices descendentes de un vértice

puede ser hallado mediante el siguiente algoritmo de rotulación: DETERMINACIÓN DE LOS FRAGMENTOS De la definición de conexidad fuerte se tiene que el conjunto F(vk) de los vértices que estén fuertemente conectados al vértices vk pueden ser expresados por:

Esto es, podemos obtener el conjunto de vértices del fragmento que contiene algún vértice específico vk mediante la construcción de los conjuntos
separadamente, utilizando el algoritmo y luego hallando la intersección de estos conjuntos.
Para hallar todos los fragmentos de un dígrafo, tomamos un vértice cualquiera y hallamos el fragmento que lo contiene. A continuación seleccionamos un vértice del dígrafo que no pertenezca al fragmento. EJEMPLO Gracias Se forma cuando el vértice inicial y final de una arista es el mismo vértice. BUCLE O RIZO Si dos o más aristas poseen el mismo vértice inicial y el mismo vértice final ARISTAS PARALELAS: Ejemplo EJEMPLO Un dígrafo simple donde , para toda arista existe en la arista

Hay una correspondencia natural uno-a-uno. DÍGRAFO SIMÉTRICO DÍGRAFO ASIMÉTRICO: EJEMPLO EJEMPLO Es un subdigrafo de un dígrafo D inducido por los vértices de D que están fuertemente conectado.

La CONDENSACIÒN de un dígrafo D es una operación que consiste en remplazar cada fragmento de D por un solo vértice y las aristas entre los fragmentos por una sola arista, se denota la condensación de un dígrafo D por D*. FRAGMENTO Representamos a continuación un algoritmo que permite determinar la condensación de un dígrafo. Antes de desarrollar el algoritmo presentaremos algunos elementos teóricos relativos a un dígrafo D. CONDENSACIÓN DE UN DÍGRAFO En un dígrafo D= (V, A, fD), un vértice vj se dice que es un SUCESOR del vértice vi se el arco (vi vj) € A(D). El conjunto de todos los sucesores de vi los denotamos por + (vi).

Similarmente, un vértice vj es un PREDECESOR del vértice vi si el arco (vj vi) € A(D). El conjunto de predecesores de vi es denotado por - (vi). SUCESORES Y PREDECESORES DE UN VÉRTICE ASCENDENTES Y DESCENDENTES DE UN VÉRTICE Sea D=(V ,A, fD) un dígrafo y vi un vértice cualquiera de D. cualquier vértice vj (no necesariamente diferente de vi) tal que existe un camino C-( vi-->vj) se llama un DESCENDENTE de vi. En la misma forma, cualquier vértice vj (no necesariamente diferente de vi) tal que existe un camino C´-(vj-->vi) se llama un ASCENDENTE de vi.
Note que un vértice vj puede ser ascendente y descendente de vi. Esto ocurre siempre que exista un circuito que contiene a vi y a vj.
Notaremos el conjunto de descendentes del vértice vi y el conjunto de ascendentes de vi. SUBDIGRAFO RESTANTE AL SUPRIMIR V1 O EL SUBDIGRAFO INDUCIDO POR V-V1 Sea D un dígrafo. Sea v1++v1<=v Se llama subdígrafo restante al suprimir v1 al subdígrafo obtenido al suprimir de V los vértices de v1 junto con los arcos incidentes en ellos. Se denota por D-V1





Sea D un dígrafo. Sea Se llama subdígrafo restante al suprimir A1 al subdígrafo obtenido al suprimir de A las aristas de A1 Se denota por: D-A1 SUBDIGRAFO RESTANTE AL SUPRIMIR A1 O EL SUBDIGRAFO INDUCIDO POR A-A1 Un dígrafo D1 es un subdígrafo cobertor de un dígrafo D si V(D1)=V(D)
Full transcript