TEORÍA DE GRAFOS
♥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.

APLICACIONES DE LOS GRAFOS:

Las aplicaciones de los grafos es en diversas áreas:

♪Resolución de problemas 

♪Algoritmos compuestos

♪Dibujos computacionales

♪Planos,etc.

Árbol: es un grafo en el que cualesquiera dos vértices están conectados por exactamente un camino.
Un árbol de búsqueda binaria es un árbol binario T en el cual se asocian ciertos datos con los vértices. Los datos están ordenados de modo que, para cada vértice v en T, cada elemento de dato en el subárbol izquierdo de v sea menor que el elemento de dato en v y cada elemento de dato en el subárbol derecho de v es mayor que el elemento de dato en v.

Composición de los grafos 

• Aristas: Son las líneas con las que se unen los vértices de un grafo.
• Aristas adyacentes: 2 aristas son adyacentes si convergen en el mismo vértice.
• Aristas paralelas: Son dos aristas conjuntas si el vértice inicial y final son el mismo.
• Arista cíclicas: Es la arista que parte de un vértice para entrar en sí mismo.
• Cruce: Son 2 aristas que cruzan en un mismo punto.
• Vértices: Los vértices son los elementos que forman un grafo. Cada uno lleva asociada una valencia característica según la situación, que se corresponde con la cantidad de aristas que confluyen en dicho vértice.
• Camino: Se denomina camino de un grafo a un conjunto de vértices interconectados por aristas. Dos vértices están conectados si hay un camino entre ellos.

Tipos de grafos

• Grafo simple: O simplemente grafo es aquel que acepta una sola 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: Es el que acepta más de una arista entre 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 general.
• Grafo orientado: grafo dirigido o digrafo. 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.
• Grafo plano: Los grafos planos son aquellos cuyos vértices y aristas pueden ser representados sin ninguna intersección entre ellos. Podemos establecer que un grafo es plano gracias al Teorema de Kuratowski.

• Grafo regular: Un grafo es regular cuando todos sus vértices tienen el mismo grado de valencia.

Grafos conexos[editar]

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érminos matemáticos la propiedad de un grafo (fuertemente) conexo permite establecer una relación de equivalenciapara sus vértices, la cual lleva a una partición de estos en "componentes (fuertemente) conexos", 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.

Grafo conexo y no conexo

Grafos completos[editar]

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 ${\displaystyle \mathbb {K} }$, siendo ${\displaystyle \mathbb {K} _{n}}$ el grafo completo de n vértices.

Un ${\displaystyle \mathbb {K} _{n}}$, es decir, grafo completo de ${\displaystyle n}$ vértices tiene exactamente ${\displaystyle {\frac {n(n-1)}{2}}}$ aristas.

La representación gráfica de los ${\displaystyle \mathbb {K} _{n}}$ como los vértices de un polígono regular da cuenta de su peculiar estructura.

Grafos bipartitos[editar]

Artículo principal: Grafo bipartito

Un grafo G es bipartito si puede expresar como ${\displaystyle G=\{V_{1}\cup V_{2},A\}}$ (es decir, sus vértices son la unión de dos grupos de vértices), bajo las siguientes condiciones:

• ${\displaystyle V_{1}}$ y ${\displaystyle V_{2}}$ son disjuntos y no vacíos.
• Cada arista de A une un vértice de V₁ con uno de V₂.
• No existen aristas uniendo dos elementos de V₁; análogamente para V₂.

Bajo estas condiciones, 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 rompecabezas en los que debe unirse un elemento de la columna A con un elemento de la columna B.

Homeomorfismo de grafos[editar]

Artículo principal: Homeomorfismo de grafos

Dos grafos ${\displaystyle G_{1}}$ y ${\displaystyle G_{2}}$ son homeomorfos si ambos pueden obtenerse a partir del mismo grafo con una sucesión desubdivisiones elementales de aristas.

Árboles[editar]

Artículo principal: Árbol (teoría de grafos)

Ejemplo de árbol.

Un grafo que no tiene ciclos y que conecta a todos los puntos, se llama un árbol. En un grafo conn vértices, los árboles tienen exactamente n - 1 aristas, y hay n^n-2 árboles posibles. Su importancia radica en que los árboles son grafos que conectan todos los vértices utilizando el menor número posible de aristas. Un importante campo de aplicación de su estudio se encuentra en el análisis filogenético, el de la filiación de entidades que derivan unas de otras en un proceso evolutivo, que se aplica sobre todo a la averiguación del parentesco entre especies; aunque se ha usado también, por ejemplo, en el estudio del parentesco entre lenguas.

Grafos ponderados o etiquetados[editar]

En muchos casos, es preciso atribuir a cada arista un número específico, llamado valuación, ponderación o coste según el contexto, y se obtiene así un grafo valuado.
Formalmente, es un grafo con una función v: A → R₊.

Por ejemplo, un representante comercial tiene que visitar n ciudades conectadas entre sí por carreteras; su interés previsible será minimizar la distancia recorrida (o el tiempo, si se pueden prever atascos). El grafo correspondiente tendrá como vértices las ciudades, como aristas las carreteras y la valuación será la distancia entre ellas.Si embargo, hasta ahora no ha sido posible encontrar métodos generales para hallar un ciclo de valuación mínima, pero sí para los caminos desde ahasta b, sin más condición.

EJEMPLOS DE ARBOLES Y GRAFOS