Grafos Y Arboles
Páginas: 7 (1659 palabras)
Publicado: 3 de octubre de 2012
Unidad 5 Grafos Y Árboles
¿Qué es un grafo y de que consta?
Un grafo G = (V;E) es una estructura combinatoria constituida por un conjunto V = V(G) de elementos llamados vértices y un conjunto E = E(G) de pares no ordenados de vértices distintos llamados aristas. Si la arista e = {u;v} = uv relaciona los vértices u y v, se dice que u y v son vértices adyacentes y también que el vértice u (o v)y la arista e son incidentes. De otro modo, los vértices se llaman independientes. Las aristas e = uv y f = wz son aristas independientes si no tienen vértices en común, es decir, {u;v} ∩ {w; z} = 0. El número de vértices de G, ǀV(G))ǀ, es el orden del grafo y el número de aristas ǀE(G)ǀ es su tamaño.
De un ejemplo gráfico de un grafo y diga cuales son los vértices y cuáles son las aristasA menudo resulta útil representar un grafo mediante un dibujo donde los vértices son puntos y las aristas líneas que unen los vértices adyacentes. Así, por ejemplo, en el grafo representado en la figura, de orden 5 y tamaño 8, los vértices u y v son adyacentes, mientras que u y w son vértices independientes.
¿Qué es un multígrafo?
A veces conviene ampliar la definición de grafo para permitirla existencia de lazos, es decir, aristas que unen un vértice con él mismo, y aristas paralelas que unen un mismo par de vértices. Un grafo con lazos y/o con aristas paralelas se llamará multígrafo.
¿Qué es el grado de un vértice y como se denota? De un ejemplo
Dado u ϵ V(G), Γ(u) denota el conjunto de vértices adyacentes con u y su número, d(u), es el grado del vértice u. El grado mímino y elgrado máximo son parámetros del grafo definidos por δ =δ(G) =minuεV{d(u)} y Δ= Δ(G)=maxuεvV {d(u)} respectivamente. Si δ =Δ =d, se dice que G es un grafo d–regular. Cuando G es un multigrafo, el grado de un vértice se define como el número de aristas incidentes con este vértice (contando cada lazo dos veces). Al sumar todos los grados de los vértices de un grafo, cada arista e=uv se cuenta dosveces (una vez desde cada uno de los dos vértices u y v incidentes con e).
Diga que son los subgrafos, grafos, isomorfos y homeomorfos de ejemplos de cada uno
Subgrafos
Son grafos que cubren únicamente una parte de un proyecto y que se encuentra enlazado mediante relaciones de ordenación con otros subgrafos en el mismo proyecto.
Isomorfos
Se puede decir que dos grafos son isomorfos si existeuna correspondencia uno a uno entre los vértices de los grafos tal que para todo par de vértices que son adyacentes en un grafo si y sólo si el correspondiente par de vértices son adyacentes en el otro grafo.
Homeomorfos
Un homeomorfismo (del griego ὅμοιος (homoios) = misma y μορφή (morphē) = forma) es una biyeccion entre dos espacios topológicos por una aplicación biyectiva que es continua ycuya recíproco es continua. En este caso, los dos espacios topológicos se dicen homeomorfos. Las propiedades de estos espacios que se conservan bajo homeomorfismos se denominan propiedades topológicas.
¿Qué es un camino? (ejemplo)
Es la sucesión de vértices tal de cada una de sus vértices existe una arista hacia el vértice sucesor.
Ejemplo (1, 3, 4, 5).
¿A qué se le denomina longitud de uncamino? (ejemplo)
Es el número de aristas que usa dicho camino, contando aristas recorridas varias veces el mismo número de veces que las recorramos.
Ejemplo: (1, 2, 5, 1, 2, 3) es un camino con longitud 5 y (5, 2, 1) es un camino simple de longitud 2.
¿Qué es un camino cerrado? (ejemplo)
Es aquel cuyo inicio es igual al final.
Ejemplo (1, 2, 3, 2, 1).
¿Qué es un camino simple?
Es aquelen el que todas las aristas del camino son diferentes.
¿Qué es un recorrido?
Recorrer un grafo significa tratar de alcanzar todos los nodos que están relacionados con uno que llamaremos nodo de salida.
Dado un grafo G = (V,E), una secuencia de vértices u0, u1… uƖ con ui-1ui ϵ E, 1 ≤ i ≤ Ɩ, y ui-1ui ≠ uj-1uj si i ≠ j, se llama un recorrido R de longitud l entre u0 y uƖ . Es preciso notar que...
¿Qué es un grafo y de que consta?
Un grafo G = (V;E) es una estructura combinatoria constituida por un conjunto V = V(G) de elementos llamados vértices y un conjunto E = E(G) de pares no ordenados de vértices distintos llamados aristas. Si la arista e = {u;v} = uv relaciona los vértices u y v, se dice que u y v son vértices adyacentes y también que el vértice u (o v)y la arista e son incidentes. De otro modo, los vértices se llaman independientes. Las aristas e = uv y f = wz son aristas independientes si no tienen vértices en común, es decir, {u;v} ∩ {w; z} = 0. El número de vértices de G, ǀV(G))ǀ, es el orden del grafo y el número de aristas ǀE(G)ǀ es su tamaño.
De un ejemplo gráfico de un grafo y diga cuales son los vértices y cuáles son las aristasA menudo resulta útil representar un grafo mediante un dibujo donde los vértices son puntos y las aristas líneas que unen los vértices adyacentes. Así, por ejemplo, en el grafo representado en la figura, de orden 5 y tamaño 8, los vértices u y v son adyacentes, mientras que u y w son vértices independientes.
¿Qué es un multígrafo?
A veces conviene ampliar la definición de grafo para permitirla existencia de lazos, es decir, aristas que unen un vértice con él mismo, y aristas paralelas que unen un mismo par de vértices. Un grafo con lazos y/o con aristas paralelas se llamará multígrafo.
¿Qué es el grado de un vértice y como se denota? De un ejemplo
Dado u ϵ V(G), Γ(u) denota el conjunto de vértices adyacentes con u y su número, d(u), es el grado del vértice u. El grado mímino y elgrado máximo son parámetros del grafo definidos por δ =δ(G) =minuεV{d(u)} y Δ= Δ(G)=maxuεvV {d(u)} respectivamente. Si δ =Δ =d, se dice que G es un grafo d–regular. Cuando G es un multigrafo, el grado de un vértice se define como el número de aristas incidentes con este vértice (contando cada lazo dos veces). Al sumar todos los grados de los vértices de un grafo, cada arista e=uv se cuenta dosveces (una vez desde cada uno de los dos vértices u y v incidentes con e).
Diga que son los subgrafos, grafos, isomorfos y homeomorfos de ejemplos de cada uno
Subgrafos
Son grafos que cubren únicamente una parte de un proyecto y que se encuentra enlazado mediante relaciones de ordenación con otros subgrafos en el mismo proyecto.
Isomorfos
Se puede decir que dos grafos son isomorfos si existeuna correspondencia uno a uno entre los vértices de los grafos tal que para todo par de vértices que son adyacentes en un grafo si y sólo si el correspondiente par de vértices son adyacentes en el otro grafo.
Homeomorfos
Un homeomorfismo (del griego ὅμοιος (homoios) = misma y μορφή (morphē) = forma) es una biyeccion entre dos espacios topológicos por una aplicación biyectiva que es continua ycuya recíproco es continua. En este caso, los dos espacios topológicos se dicen homeomorfos. Las propiedades de estos espacios que se conservan bajo homeomorfismos se denominan propiedades topológicas.
¿Qué es un camino? (ejemplo)
Es la sucesión de vértices tal de cada una de sus vértices existe una arista hacia el vértice sucesor.
Ejemplo (1, 3, 4, 5).
¿A qué se le denomina longitud de uncamino? (ejemplo)
Es el número de aristas que usa dicho camino, contando aristas recorridas varias veces el mismo número de veces que las recorramos.
Ejemplo: (1, 2, 5, 1, 2, 3) es un camino con longitud 5 y (5, 2, 1) es un camino simple de longitud 2.
¿Qué es un camino cerrado? (ejemplo)
Es aquel cuyo inicio es igual al final.
Ejemplo (1, 2, 3, 2, 1).
¿Qué es un camino simple?
Es aquelen el que todas las aristas del camino son diferentes.
¿Qué es un recorrido?
Recorrer un grafo significa tratar de alcanzar todos los nodos que están relacionados con uno que llamaremos nodo de salida.
Dado un grafo G = (V,E), una secuencia de vértices u0, u1… uƖ con ui-1ui ϵ E, 1 ≤ i ≤ Ɩ, y ui-1ui ≠ uj-1uj si i ≠ j, se llama un recorrido R de longitud l entre u0 y uƖ . Es preciso notar que...
Leer documento completo
Regístrate para leer el documento completo.