TEORIA DE GRAFOS
Páginas: 2 (461 palabras)
Publicado: 7 de octubre de 2014
Grafos no Dirigidos
Un grafo en el cual todas las aristas son no dirigidas se denominará "grafo no dirigido". El grafo no dirigido es aquel que no tiene sentido su arista. Un grafo no dirigido Grepresenta elementos, y una arista (v, w) representa una incompatibilidad entre los elementos v y w.
Ejemplo de Grafo no Dirigido:
Una red Eléctrica de Varias Ciudades.
GrafosDirigidos:
Un grafo en el cual toda arista es dirigida se denominará "dígrafo" o bien "grafo dirigido". Un grafo dirigido o dígrafo consiste de un conjunto de vértices V y un conjunto de arcos A. Los vértices se denominan nodos o puntos; los arcos también se conocen como aristas o líneas dirigidas que representan que entre un par de vértices existe una relación unívoca.
Qué significadotiene para una Arista ser Incidente sobre una Vértice
Una arista es incidente a un vértice si ésta lo une a otro.
Que significa Adyacente
Dos aristas son adyacentes si tienen un vértice en común, ydos vértices son adyacentes si una arista los une.
Que es una Arista Paralela
Son dos o más aristas que son incidentes (es decir, que conectan) a al menos dos vértices. Los grafos sin aristasmúltiples son llamados grafos simples.
Que es un Lazo
Es aquella arista que sale de un vértice y regresa al mismo vértice.
Un vértice aislado es un vértice con grado cero; esto es, un vértice que noes punto final de ninguna arista.
Que es Grafica Simple-Ponderado
En muchos casos, es preciso atribuir a cada arista un número específico, llamado valuación, ponderación o coste según el contexto, yse obtiene así un grafo valuado.
Formalmente, es un grafo con una función v: A → R+.
Por ejemplo, un representante comercial tiene que visitar n ciudades conectadas entre sí por carreteras; suinterés previsible será minimizar la distancia recorrida (o el tiempo, si se pueden prever atascos). El grafo correspondiente tendrá como vértices las ciudades, como aristas las carreteras y la...
Un grafo en el cual todas las aristas son no dirigidas se denominará "grafo no dirigido". El grafo no dirigido es aquel que no tiene sentido su arista. Un grafo no dirigido Grepresenta elementos, y una arista (v, w) representa una incompatibilidad entre los elementos v y w.
Ejemplo de Grafo no Dirigido:
Una red Eléctrica de Varias Ciudades.
GrafosDirigidos:
Un grafo en el cual toda arista es dirigida se denominará "dígrafo" o bien "grafo dirigido". Un grafo dirigido o dígrafo consiste de un conjunto de vértices V y un conjunto de arcos A. Los vértices se denominan nodos o puntos; los arcos también se conocen como aristas o líneas dirigidas que representan que entre un par de vértices existe una relación unívoca.
Qué significadotiene para una Arista ser Incidente sobre una Vértice
Una arista es incidente a un vértice si ésta lo une a otro.
Que significa Adyacente
Dos aristas son adyacentes si tienen un vértice en común, ydos vértices son adyacentes si una arista los une.
Que es una Arista Paralela
Son dos o más aristas que son incidentes (es decir, que conectan) a al menos dos vértices. Los grafos sin aristasmúltiples son llamados grafos simples.
Que es un Lazo
Es aquella arista que sale de un vértice y regresa al mismo vértice.
Un vértice aislado es un vértice con grado cero; esto es, un vértice que noes punto final de ninguna arista.
Que es Grafica Simple-Ponderado
En muchos casos, es preciso atribuir a cada arista un número específico, llamado valuación, ponderación o coste según el contexto, yse obtiene así un grafo valuado.
Formalmente, es un grafo con una función v: A → R+.
Por ejemplo, un representante comercial tiene que visitar n ciudades conectadas entre sí por carreteras; suinterés previsible será minimizar la distancia recorrida (o el tiempo, si se pueden prever atascos). El grafo correspondiente tendrá como vértices las ciudades, como aristas las carreteras y la...
Leer documento completo
Regístrate para leer el documento completo.