Grafos y arboles
Páginas: 7 (1734 palabras)
Publicado: 22 de agosto de 2012
Universidad Valle Del Grijalva
Campus Pichucalco Chiapas
Ingeniería en Sistemas Computacionales
Tema:
Unidad 3. Grafos y Arboles
Teoria Matematica
Semestre: “4°”
Sistema: Semiescolarizado
INTRODUCCIÓN
La teoría de gráficas o teoría de grafos es aplicada en una gran cantidad de áreas tales como ciencias sociales, lingüística, ciencias físicas,ingeniería de comunicación, y otras.
La teoría de grafos también juega un papel importante en varias áreas de la ciencia de la computación, tales como teoría de cambio y lógica de diseño, inteligencia artificial, lenguajes formales, gráficos por computadora, sistemas operativos, compiladores, y organización y recuperación de información.
3.1 GRAFOS, NODOS, RAMAS YLAZOS
LOS GRAFOS
Son estructuras discretas compuestas por puntos (llamados vértices) y líneas (llamadas aristas) que conectan algunos pares de esos puntos.
Son una abstracción útil para modelar diversas situaciones tales como: redes de computadoras, estructuras de datos redes telefónicas o eléctricas, circuitos eléctricos, sistemas de carreteras, sistemas de distribución de mercancías,sistemas de toma de decisiones, etc.
Nodo
Es uno de los elementos de una lista enlazada, de un árbol o de un grafo. Cada nodo será una estructura o registro que dispondrá de varios campos, y al menos uno de esos campos será un puntero o referencia a otro nodo, de forma que, conocido un nodo, a partir de esa referencia, será posible en teoría tener acceso a otros nodos de la estructura. Los nodosson herramientas esenciales para la construcción de estructuras de datos dinámicas.
Rama
Es una trayectoria dirigida continua de un nodo a otro. También reciben el nombre indistintamente de arcos, aristas o segmentos.
Las ramas paralelas o segmentos múltiples, son aristas que conectan las mismas terminales. Es decir, que del mismo vértice parten 2 o más aristas a otro.
Los grafos puedenser simples (cuando sólo una arista une dos vértices cualesquiera) o complejos. Los grafos simples están formados por dos conjuntos: el conjunto V de vértices o nodos y el conjunto de pares de vértices que se llaman aristas o arcos y que señalan qué nodos están relacionados.
En un grafo G = (V,E), un eje que esté asociado a un par ordenado de V x V es llamado eje dirigido de G, mientras un ejeque esté asociado a un par no ordenado de nodos es llamado eje no dirigido. Un grafo del cual cada nodo es dirigido es llamado dígrafo o grafo dirigido. Un grafo en el cual cada eje es no dirigido es llamado grafo no dirigido. Si algunos ejes son dirigidos y otros no dirigidos en un grafo, se trata de un grafo mixto.
[pic]
Fig.1 Los grafos (b), (e) y (g) son grafos dirigidos. Los grafosmostrados en (c) y (f) son no dirigidos.
El grafo (e) es mixto. El grafo de (a) puede considerarse como dirigido y no dirigido.
3.2 GRAFOS SIMPLES
Un grafo es simple si a lo más existe una arista uniendo dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos. Es un grafo que no tiene lazos ni lados paralelos.
Ungrafo que no es simple se denomina multígrafo.
[pic]
3.3 GRAFOS DE SIMILARIDAD
Es un grafo que representa la agrupación de varias clases de objetos parecidos, basándose en sus propiedades; y estableciendo así, qué tan similar es uno con respecto al otro.
Un grafo de similaridad se construye como sigue: los vértices corresponden a los programas
[pic]
3.4 GRAFOS CONEXOS
Ungrafo se puede definir como conexo si cualquier vértice V pertenece al conjunto de vértices y es alcanzable por algún otro. Otra definición que dejaría esto más claro sería: "un grafo conexo es un grafo no dirigido de modo que para cualquier par de nodos existe al menos un camino que los une".
3.5 DEFINICIÓN DE UN ÁRBOL, ARBOLES LIBRES
Árboles.
Un árbol se define como un tipo de grafo...
Campus Pichucalco Chiapas
Ingeniería en Sistemas Computacionales
Tema:
Unidad 3. Grafos y Arboles
Teoria Matematica
Semestre: “4°”
Sistema: Semiescolarizado
INTRODUCCIÓN
La teoría de gráficas o teoría de grafos es aplicada en una gran cantidad de áreas tales como ciencias sociales, lingüística, ciencias físicas,ingeniería de comunicación, y otras.
La teoría de grafos también juega un papel importante en varias áreas de la ciencia de la computación, tales como teoría de cambio y lógica de diseño, inteligencia artificial, lenguajes formales, gráficos por computadora, sistemas operativos, compiladores, y organización y recuperación de información.
3.1 GRAFOS, NODOS, RAMAS YLAZOS
LOS GRAFOS
Son estructuras discretas compuestas por puntos (llamados vértices) y líneas (llamadas aristas) que conectan algunos pares de esos puntos.
Son una abstracción útil para modelar diversas situaciones tales como: redes de computadoras, estructuras de datos redes telefónicas o eléctricas, circuitos eléctricos, sistemas de carreteras, sistemas de distribución de mercancías,sistemas de toma de decisiones, etc.
Nodo
Es uno de los elementos de una lista enlazada, de un árbol o de un grafo. Cada nodo será una estructura o registro que dispondrá de varios campos, y al menos uno de esos campos será un puntero o referencia a otro nodo, de forma que, conocido un nodo, a partir de esa referencia, será posible en teoría tener acceso a otros nodos de la estructura. Los nodosson herramientas esenciales para la construcción de estructuras de datos dinámicas.
Rama
Es una trayectoria dirigida continua de un nodo a otro. También reciben el nombre indistintamente de arcos, aristas o segmentos.
Las ramas paralelas o segmentos múltiples, son aristas que conectan las mismas terminales. Es decir, que del mismo vértice parten 2 o más aristas a otro.
Los grafos puedenser simples (cuando sólo una arista une dos vértices cualesquiera) o complejos. Los grafos simples están formados por dos conjuntos: el conjunto V de vértices o nodos y el conjunto de pares de vértices que se llaman aristas o arcos y que señalan qué nodos están relacionados.
En un grafo G = (V,E), un eje que esté asociado a un par ordenado de V x V es llamado eje dirigido de G, mientras un ejeque esté asociado a un par no ordenado de nodos es llamado eje no dirigido. Un grafo del cual cada nodo es dirigido es llamado dígrafo o grafo dirigido. Un grafo en el cual cada eje es no dirigido es llamado grafo no dirigido. Si algunos ejes son dirigidos y otros no dirigidos en un grafo, se trata de un grafo mixto.
[pic]
Fig.1 Los grafos (b), (e) y (g) son grafos dirigidos. Los grafosmostrados en (c) y (f) son no dirigidos.
El grafo (e) es mixto. El grafo de (a) puede considerarse como dirigido y no dirigido.
3.2 GRAFOS SIMPLES
Un grafo es simple si a lo más existe una arista uniendo dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos. Es un grafo que no tiene lazos ni lados paralelos.
Ungrafo que no es simple se denomina multígrafo.
[pic]
3.3 GRAFOS DE SIMILARIDAD
Es un grafo que representa la agrupación de varias clases de objetos parecidos, basándose en sus propiedades; y estableciendo así, qué tan similar es uno con respecto al otro.
Un grafo de similaridad se construye como sigue: los vértices corresponden a los programas
[pic]
3.4 GRAFOS CONEXOS
Ungrafo se puede definir como conexo si cualquier vértice V pertenece al conjunto de vértices y es alcanzable por algún otro. Otra definición que dejaría esto más claro sería: "un grafo conexo es un grafo no dirigido de modo que para cualquier par de nodos existe al menos un camino que los une".
3.5 DEFINICIÓN DE UN ÁRBOL, ARBOLES LIBRES
Árboles.
Un árbol se define como un tipo de grafo...
Leer documento completo
Regístrate para leer el documento completo.