Grafos

REPUBLICA BOLIVARIANA DE VENEZUELA
UNIVERSIDAD NACIONAL EXPERIMENTAL DE LOS LLANOS OCCIDENTALES EZEQUIEL ZAMORA
BARINAS

PROF: PEDRO GOMEZ
BACHILLER:
ANDRES GONZALEZC.I: 22.114.572.
ING. EN INFORMATICA
V SEM.
SECCIÓN N”1” (NOCTURNO)

BARINAS 21/03/2012

GRAFOS:
Representación Grafica:
Es un conjunto de objetos llamados vértices o nodos unidospor enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto.
Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas).
Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre unidades que interactúan unas con otras. Por ejemplo, una red decomputadoras puede representarse y estudiarse mediante un grafo, en el cual los vértices representan terminales y las aristas representan conexiones (las cuales, a su vez, pueden ser cables o conexiones inalámbricas).

Grafo dirigido

Grafo dirigido
Un grafo dirigido o diagrafo es un grafo  donde:
*
*  es un conjunto de pares ordenados de elementos de.
Dada una arista,  es su nodoinicial y  su nodo final.
Por definición, los grafos dirigidos no contienen bucles.
Grafo no dirigido

Grafo no dirigido
Un grafo no dirigido o grafo propiamente dicho es un grafo  donde:
*
*  es un conjunto de pares no ordenados de elementos de .
Un par no ordenado es un conjunto de la forma , de manera que. Para los grafos, estos conjuntos pertenecen al conjuntopotencia de  de cardinalidad 2, el cual se denota por.

CARACTERIZACIÓN DE GRAFOS:
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.
Un grafo que no es simple se denomina multigrafo.
Grafos conexos
Un grafo es conexo si cada par de vértices está conectado por un camino; esdecir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b.
Un grafo es doblemente conexo si cada par de vértices está conectado por al menos dos caminos disjuntos; es decir, es conexo y no existe un vértice tal que al sacarlo el grafo resultante sea disconexo.
Es posible determinar si un grafo es conexo usando un algoritmo Búsqueda en anchura (BFS)o Búsqueda en profundidad (DFS).
En términos matemáticos la propiedad de un grafo de ser (fuertemente) conexo permite establecer con base en él una relación de equivalencia para sus vértices, la cual lleva a una partición de éstos en "componentes (fuertemente) conexas", es decir, porciones del grafo, que son (fuertemente) conexas cuando se consideran como grafos aislados. Esta propiedad es importantepara muchas demostraciones en teoría de grafos. 
Grafos completos
Artículo principal: Grafo completo.
Un grafo es completo si existen aristas uniendo todos los pares posibles de vértices. Es decir, todo par de vértices (a, b) debe tener una arista e que los une.
El conjunto de los grafos completos es denominado usualmente, siendo  el grafo completo de n vértices.
Un, es decir, grafo completode  vértices tiene exactamente  aristas.
La representación gráfica de los  como los vértices de un polígono regular da cuenta de su peculiar estructura.
Grafos bipartitos
Artículo principal: Grafo bipartito.
Un grafo G es bipartito si puede expresarse como  (es decir, sus vértices son la unión de dos grupos de vértices), bajo las siguientes condiciones:
*  y  son disjuntos y no...