Grafos y ABB

Un grafo es la gráfica resultante de una representación R. Estas representaciones geométricas de las relaciones correspondientes son un enunciado verdadero de estas. Gracias a ellos, se pueden expresar de forma visual y sencilla las relaciones entre elementos de distinto tipo.

Los grafos se clasifican 5 categorías:

1. Grafos simples: Aquellos que no tienen ningún tipo de lazo ni lado paralelo.
2. Grafo completo de n vértices: En este grafo cada vértice está relacionado con todos los demás, sin lazos ni lados paralelos.
3. Complemento de un grafo: Aquel que no tiene ni lazos ni ramas paralelas, y aparte, que no contiene al grafo G formando un grafo completo de n vértices.
4. Grafo bipartido: Aquel que está formado por dos conjuntos de vértices, en donde los elementos del conjunto A se relacionan con el conjunto B (aRb).
5. Grafo bipartido y completo: Aquel que está compuesto por dos conjuntos de vértices, y en el que cada vértice de A esta unido con todos los de B, pero no hay ninguna arista que una a los elementos de un mismo conjunto.

Un grafo se compone de puntos (llamados vértices o nodos) y lados que unen los vértices (llamados ramas o aristas).

El vértice se indica por medio de un circulo y se le asigna un numero o una letra y puede colocarse donde sea.

Las aristas son líneas que unen un vértice con otro y se le asigna una letra, numero, o combinación de ambos.

Los lados paralelos son aquellas aristas que tienen relación con un mismo par de vértices.

Un lazo es aquella arista que sale de un vértice y regresa al mismo vértice.

La valencia de un vértice es el número de lados que entran o salen de un vértice. Las entradas son el número de aristas que terminan en un vértice, y las salidas son el número de aristas que salen de un nodo.

Los grafos son útiles para el reconocimiento de patrones mediante grafos de similaridad, determinando la ruta más corta mediante grafos ponderados

Arboles de búsqueda

Un árbol es un grafo conexo que no tiene ciclos, lazos ni lados paralelos. Su estructura jerárquica permite una organización ordenada de la información, por lo que cuando se requiera se pueda encontrar de forma rápida y precisa.

La situación principal era que el tratamiento de los grafos no guarda una estructura establecida y no respeta reglas, ya que el acomodo de los nodos y de las aristas puede ser como uno desee, y esto ocasiona que existan problemas al tratar y organizar la información para la computación, por lo que para este ámbito se empezaron a usar grafos con características especiales, a los que se les conoce como árboles.

...