Grafos , Tipos De Grafos, Grafitis

TALLER
GRAFOS

PRESENTADO A
CRISTIAN MARTINES

PRESENTADO POR
MARCELO CAMPOS


UNIVERSIDAD DE CARTAGENA
CREAD -- LORICA

GRAFOS
Para las ciencias de la computación y la matemática,un grafo es una representación gráfica de diversos puntos que se conocen como nodos o vértices, los cuales se encuentran unidos a través de líneas que reciben el nombre de aristas. Al analizar losgrafos, los expertos logran conocer cómo se desarrollan las relaciones recíprocas entre aquellas unidades que mantienen algún tipo de interacción.
Los grafos se pueden clasificar de diversas manerassegún sus características. Los grafos simples, en este sentido, son aquellos que surgen cuando una única arista logra unir dos vértices. Los grafos complejos, en cambio, presentan más de una arista enunión con los vértices.
Por otra parte, un grafo es conexo si dispone de dos vértices conectados a través de un camino. ¿Qué quiere decir esto? que, para el par de vértices (p, r), tiene que existir algúncamino que permita llegar desde p hasta r.
Un grafo simple, además, puede ser completo si las aristas están en condiciones de unir todos los pares de vértices, mientras que un grafo es bipartito sisus vértices surgen por la unión de un par de conjuntos de vértices y si se cumple una serie de condiciones.
Recorrer un grafo significa tratar de alcanzar todos los nodos que estén relacionados conuno que llamaremos nodo de salida. Existen básicamente dos técnicas para recorrer un grafo: el recorrido en anchura y el recorrido en profundidad.
RECORRIDO DE ANCHURA (BFS) El recorrido en anchurade un árbol consiste en visitar todos los elementos del árbol una sola vez, de la forma: primero se visitan los elementos del nivel 0, luego los del nivel 1, y así sucesivamente, En cada nivel, sevisitan los elementos de izquierda a derecha.

RECORRIDO DE PROFUNDIDAD DFS) Es un algoritmo que permite recorrer todos los nodos de un grafo o árbol (teoría de grafos) de manera ordenada, pero no...