Teoria de grafos

TEORIA DE GRAFOS

En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos (también llamadas gráficas). Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas (edges en inglés) que pueden ser orientados o no. Típicamente, un grafo serepresenta mediante una serie de puntos (los vértices) conectados por líneas (las aristas).

TIPO 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 completos
Un grafoes 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 n vértices tiene exactamente  aristas.
La representación gráfica de los  como los vértices de un polígono regularda cuenta de su peculiar estructura.

Grafos bipartitos
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:
* V1 y V2 son disjuntos y no vacíos.
* Cada arista de A une un vértice de V1 con uno de V2.
* No existen aristas uniendo dos elementos de V1; análogamente para V2.
Bajo estascondiciones, el grafo se considera bipartito, y puede describirse informalmente como el grafo que une o relaciona dos conjuntos de elementos diferentes, como aquellos resultantes de los ejercicios y puzzles en los que debe unirse un elemento de la columna A con un elemento de la columna B.

Grafos conexos
Un grafo es conexo si cada par de vértices está conectado por un camino; es decir, si paracualquier 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 enprofundidad (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 importante para muchasdemostraciones en teoría de grafos. 

Grafos planos
un grafo plano (o planar según referencias) es un grafo que puede ser dibujado en el plano sin que ninguna arista se interseque (una definición más formal puede ser que este grafo pueda ser "embebido" en un plano). Un grafo no es plano si no puede ser dibujado sobre un plano sin que sus aristas se intersequen. Los grafos K5 y el K3,3 son los grafos noplanos minimales, lo cual nos permitirán caracterizar el resto de los grafos no planos.

ARBOLES
En teoría de grafos, un árbol es un grafo en el que cualesquiera dos vértices están conectados por exactamente un camino. Un bosques una unión disjunta de árboles. Un árbol a veces recibe el nombre de árbol libre.
Un árbol es un grafo simple unidireccional G que satisface alguna de las siguientescondiciones equivalentes:
* G es conexo y no tiene ciclos simples.
* G no tiene ciclos simples y, si se añade alguna arista se forma un ciclo simple.
* G es conexo y si se le quita alguna arista deja de ser conexo.
* G es conexo y el grafo completo de 3 vértices K3 no es un menor de G.
* Dos vértices cualquiera de G están conectados por un único camino simple.
Si G tiene...