Bere

En matemáticas y ciencias de la computación, un grafo (del griego grafos: dibujo, imagen) o gráfica es el principal objeto de estudio de la teoría de grafos.
Informalmente, un grafo es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto.
Típicamente, un grafo se representagrá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 de computadoras puede representarse y estudiarse mediante un grafo, en el cual los vértices representan terminales y las aristas representan conexiones (las cuales, asu vez, pueden ser cables o conexiones inalámbricas).
Tipos de grafos
* Grafo simple. o simplemente grafo es aquel que acepta una sola 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. Es la definición estándar de un grafo.
* Multigrafo. o pseudografo son grafos que aceptan más de una aristaentre dos vértices. Estas aristas se llaman múltiples o lazos (loops en inglés). Los grafos simples son una subclase de esta categoría de grafos. También se les llama grafos no-dirigido.
* Grafo dirigido. Son grafos en los cuales se ha añadido una orientación a las aristas, representada gráficamente por una flecha
* Grafo etiquetado. Grafos en los cuales se ha añadido un peso a las aristas(número entero generalmente) o un etiquetado a los vértices.
* Grafo aleatorio. Grafo cuyas aristas están asociadas a una probabilidad.
* Hipergrafo. Grafos en los cuales las aristas tienen más de dos extremos, es decir, las aristas son incidentes a 3 o más vértices.
* Grafo infinito. Grafos con conjunto de vértices y aristas de cardinal infinito.
Caracterización de grafos
[editar]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.
[editar] Grafos conexos
Un grafo es conexo si cada par de vértices está conectado por un camino; es decir, 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érminosmatemá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 importante para muchas demostraciones en teoría de grafos.[editar] 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 completo de 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.
[editar] 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 vacíos.
* Cada arista de A une un...