Teoría de Grafos
¿Que es la Teoría de Grafos?
Es una rama de las matemáticas y las ciencias de la computación que permite el estudio de grafos, un grafo es una par (V,E) donde V es un conjunto de vértices y E es un conjunto de aristas, junto con una relación que relaciona dos vertices a través de una arista. Esta rama permite su clasificación, análisis de propiedades y sus aplicaciones prácticas para un fin. Por ejemplo, los problemas relacionados con posibilidades de comunicación (redes de comunicación y de transporte), relaciones de orden entre actividades (planificaciones de proyectos mediante PERT) o estructuras de producto complejas(gestión de inventarios). Los grafos son una herramienta que permite modelizar relaciones de esta naturaleza, de modo que sea posible resolver problemas asociados a esas circunstancias de manera menos costosa que con otras técnicas.
Ejemplos de grafos:
Mapa de carreteras,planos de metro, redes de PCs,Plano de un circuito eléctrico, árboles genealógicos.
Entre sus aplicaciones se destacan las áreas de:
Compiladores y traductores, estructuras de datos, autómatas computacionales, redes, etc.
¿Que es la Teoría de Grafos?
Es una rama de las matemáticas y las ciencias de la computación que permite el estudio de grafos, un grafo es una par (V,E) donde V es un conjunto de vértices y E es un conjunto de aristas, junto con una relación que relaciona dos vertices a través de una arista. Esta rama permite su clasificación, análisis de propiedades y sus aplicaciones prácticas para un fin. Por ejemplo, los problemas relacionados con posibilidades de comunicación (redes de comunicación y de transporte), relaciones de orden entre actividades (planificaciones de proyectos mediante PERT) o estructuras de producto complejas(gestión de inventarios). Los grafos son una herramienta que permite modelizar relaciones de esta naturaleza, de modo que sea posible resolver problemas asociados a esas circunstancias de manera menos costosa que con otras técnicas.
Ejemplos de grafos:
Mapa de carreteras,planos de metro, redes de PCs,Plano de un circuito eléctrico, árboles genealógicos.
Entre sus aplicaciones se destacan las áreas de:
Compiladores y traductores, estructuras de datos, autómatas computacionales, redes, etc.
Vértice: Los vértices constituyen uno de los dos elementos que forman un grafo. Como ocurre con el resto de las ramas de las matemáticas, a la Teoría de Grafos no le interesa saber qué son los vértices. Diferentes situaciones en las que pueden identificarse objetos y relaciones que satisfagan la definición de grafo pueden verse como grafos y así aplicar la Teoría de Grafos en ellos.
Grafo:Un grafo es una pareja de conjuntos donde es el conjunto de vértices, y es el conjunto de aristas, este último es un conjunto de pares de la forma tal que . Para simplificar, notaremos la arista como . En teoría de grafos, sólo queda lo esencial del dibujo: la forma de las aristas no son relevantes, sólo importa a qué vértices están unidas. La posición de los vértices tampoco importa, y se puede variar para obtener un dibujo más claro.
Subgrafo: Un subgrafo de un grafo G es un grafo cuyos conjuntos de vértices y aristas son subconjuntos de los de G. Se dice que un grafo G contiene a otro grafo H si algún subgrafo de G es H o es isomorfo a H (dependiendo de las necesidades de la situación).
El subgrafo inducido de G es un subgrafo G' de G tal que contiene todas las aristas adyacentes al subconjunto de vértices de G.
Entre Otros.
Teoría de Arboles
Árbol: Es un grafo en el que cualesquiera dos vértices están conectados por exactamente un camino.
Los árboles corresponden a una de las subclases de grafos de uso más amplio, particularmente en computación.
Los grafos se pueden clasificar en dos grupos: dirigidos y no dirigidos. Los arboles forman parte de los no dirigidos.
Sirven para organizar y relacionar datos en una base de datos, por ejemplo. Esto permite realizar operaciones de manera eficiente. Por ejemplo, un árbol de definición jerárquica se utiliza para configurar una base de datos para los registros de libros existentes en diversas bibliotecas.
Otro ejemplo de la utilización de árboles son los diccionarios. A partir de una palabra, se realiza una búsqueda en el árbol para saber si está incluida en el conjunto, y si existe, se obtienen sus datos asociados (por ejemplo, si es un verbo, un sustantivo, un artículo, etc.).
Definición: un árbol binario es un árbol con raíz en el cual cada vértice tiene cero, uno o dos hijos. Si un vértice tiene un hijo, ese hijo se designa como un hijo izquierdo o un hijo derecho (pero no ambos). Si un vértice tiene dos hijos, uno de ellos se designa como un hijo izquierdo y el otro se designa como un hijo derecho.
Un árbol de búsqueda binaria es un árbol binario T en el cual se asocian ciertos datos con los vértices. Los datos están ordenados de modo que, para cada vértice v en T, cada elemento de dato en el subárbol izquierdo de v sea menor que el elemento de dato en v y cada elemento de dato en el subárbol derecho de v es mayor que el elemento de dato en v.
Los arboles de búsqueda binaria son útiles para localizar datos. Es decir, dado un elemento D, podemos determinar con facilidad si D está en un árbol de búsqueda binaria y, de estar presente, conocer su posición. Para determinar si un elemento de dato D esta en un árbol de búsqueda binaria, comenzaríamos en la raíz. Luego compararíamos de manera sucesiva D con el elemento de dato del vértice en cuestión. Si D es igual al elemento de dato del vértice en cuestión, hemos encontrado a D, por lo cual habremos concluido. Si D es menor que el elemento de dato en el vértice en cuestión v, nos movemos al hijo izquierdo de v y repetimos el proceso. Si D es mayor que el elemento de dato en el vértice en cuestión v, nos movemos al hijo derecho de v y repetimos el proceso. Si en algún momento no existe un hijo al cual moverse, podemos concluir que D no está en el árbol.
Teoría de Arboles
Árbol: Es un grafo en el que cualesquiera dos vértices están conectados por exactamente un camino.
Los árboles corresponden a una de las subclases de grafos de uso más amplio, particularmente en computación.
Los grafos se pueden clasificar en dos grupos: dirigidos y no dirigidos. Los arboles forman parte de los no dirigidos.
Sirven para organizar y relacionar datos en una base de datos, por ejemplo. Esto permite realizar operaciones de manera eficiente. Por ejemplo, un árbol de definición jerárquica se utiliza para configurar una base de datos para los registros de libros existentes en diversas bibliotecas.
Otro ejemplo de la utilización de árboles son los diccionarios. A partir de una palabra, se realiza una búsqueda en el árbol para saber si está incluida en el conjunto, y si existe, se obtienen sus datos asociados (por ejemplo, si es un verbo, un sustantivo, un artículo, etc.).
Árboles binarios
Definición: un árbol binario es un árbol con raíz en el cual cada vértice tiene cero, uno o dos hijos. Si un vértice tiene un hijo, ese hijo se designa como un hijo izquierdo o un hijo derecho (pero no ambos). Si un vértice tiene dos hijos, uno de ellos se designa como un hijo izquierdo y el otro se designa como un hijo derecho.
Un árbol de búsqueda binaria es un árbol binario T en el cual se asocian ciertos datos con los vértices. Los datos están ordenados de modo que, para cada vértice v en T, cada elemento de dato en el subárbol izquierdo de v sea menor que el elemento de dato en v y cada elemento de dato en el subárbol derecho de v es mayor que el elemento de dato en v.
Los arboles de búsqueda binaria son útiles para localizar datos. Es decir, dado un elemento D, podemos determinar con facilidad si D está en un árbol de búsqueda binaria y, de estar presente, conocer su posición. Para determinar si un elemento de dato D esta en un árbol de búsqueda binaria, comenzaríamos en la raíz. Luego compararíamos de manera sucesiva D con el elemento de dato del vértice en cuestión. Si D es igual al elemento de dato del vértice en cuestión, hemos encontrado a D, por lo cual habremos concluido. Si D es menor que el elemento de dato en el vértice en cuestión v, nos movemos al hijo izquierdo de v y repetimos el proceso. Si D es mayor que el elemento de dato en el vértice en cuestión v, nos movemos al hijo derecho de v y repetimos el proceso. Si en algún momento no existe un hijo al cual moverse, podemos concluir que D no está en el árbol.
No hay comentarios:
Publicar un comentario