Matematicas

Matemáticas Discretas

12
Investigación
Michel Gerardo Ramírez Martínez
Sistemas

Algoritmos de recorrido y búsqueda
El algoritmo de Dijkstra: en la Teoría de grafos, el problema de los CAMINOS más cortos es el problema que consiste en encontrar un camino entre dos vértices (o nodos) de tal manera que la suma de los pesos de las aristas que lo constituyen es mínima.

La idea subyacenteen este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene.

Algoritmos a lo ancho
El algoritmo de recorrido en anchura o BFS, explora sistemáticamente todas las ramas o aristasdel grafo de manera que primero se visitan los nodos o vértices más cercanos a un nodo inicial.

Para la implementación de este algoritmo se utiliza globalmente un contador y un vector de enteros para marcar los vértices ya visitados y almacenar el recorrido. El algoritmo BFS requiere también un vector de cola auxiliar para gestionar los vértices no visitados. En muchos casos es necesarioejecutar este algoritmo empezando en los nodos más alejados del nodo escogido como nodo inicial.

Algoritmos de profundidad
El algoritmo de recorrido en profundidad o DFS, explora sistemáticamente las ramas o aristas del grafo de manera que primero se visitan los nodos o vértices adyacentes a los visitados más recientemente.

De esta forma se va "profundizando" en el grafo, es decir, alejándoseprogresivamente del nodo inicial [2]. Esta estrategia admite una implementación simple en forma recursiva, utilizando globalmente un contador y un vector de enteros para marcar los vértices ya visitados y almacenar el orden del recorrido.

Árbol (Teoría de grafos)
Propiedades:
El nº de caminos de longitud k de vi a vj es el elemento ij de la matriz M(G)k.
Un grafo G es bipartido Û G no tieneciclos de longitud impar.
Se llama distancia entre dos vértices u y v, a la longitud mínima de un camino que conecta dichos vértices y se designa por d(u,v).
Se llama diámetro de G a la máxima distancia entre dos vértices de G, diam(G).
Un grafo es conexo si para cada par de vértices u y v existe un camino de u a v. Si G es un grafo no conexo (o disconexo), cada uno de sus subgrafos conexosmaximales se llama componente conexa de G.
Un vértice v se llama vértice-corte (o punto de articulación) de G si el grafo G-{v} tiene más componentes conexas que G.
Una arista a de un grafo G se llama puente si G-{a} tiene más componentes conexas que G.
Clasificación
Arbol binario: No pueden tener más de dos hijos de ahí el nombre binario. Si algún hijo tiene como referencia a null, es decirque no almacena ningún dato, entonces este es llamado un nodo externo. En el caso contrario el hijo es llamado un nodo interno.
Árbol binario de búsqueda auto-balanceable: En ciencias de la computación, un árbol binario de búsqueda auto-balanceable o equilibrado es un árbol binario de búsqueda que intenta mantener su altura, o el número de niveles de nodos bajo la raíz, tan pequeños como seaposible en todo momento, automáticamente. Esto es importante, ya que muchas operaciones en un árbol de búsqueda binaria tardan un tiempo proporcional a la altura del árbol, y los árboles binarios de búsqueda ordinarios pueden tomar alturas muy grandes en situaciones normales, como cuando las claves son insertadas en orden.
Arbol AVL: Fue el primer árbol de búsqueda binario auto-balanceable que seideó.
Arbol Rojo-Negro: Un árbol rojo-negro es un tipo especial de árbol binario usado en informática para organizar información compuesta por datos comparables. En los árboles rojo-negro las hojas no son relevantes y no contienen datos. A la hora de implementarlo en un lenguaje de programación, para ahorrar memoria, un único nodo (nodo-centinela) hace de nodo hoja para todas las ramas. Así,todas...