Quimica

TEMAS: Grafos
Tipos de Grafos
Vértices
Aristas
Tipos de Aristas
Circuito Euleriano
Circuito HamiltonianoGrafos
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. Son objeto de estudio de la teoría de grafos.
Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas).
Prácticamente cualquier problema puederepresentarse mediante un grafo, y su estudio trasciende a las diversas áreas de las ciencias exactas y las ciencias sociales.
Un grafo G es un par ordenado G=(V,E), donde:
V es un conjunto de vértices o nodos, y
E es un conjunto de aristas o arcos, que relacionan estos nodos.
Normalmente V suele ser finito. Muchos resultados importantes sobre grafos no son aplicables para grafos infinitos.
Se llamaorden del grafo G a su número de vértices, |V|.
El grado de un vértice o nodo es igual al número de arcos que lo tienen como extremo.
Un bucle es una arista que relaciona al mismo nodo; es decir, una arista donde el nodo inicial y el nodo final coinciden.

Ejemplo:
La imagen es una representación del siguiente grafo:
V:={1,2,3,4,5,6}
E:={{1,2},{1,5},{2,3},{2,5},{3,4},{4,5},{4,6}}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.- Son grafos que aceptan más de una arista entre dos vértices. Estas aristas se llaman múltiples o lazos. Losgrafos 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 cuyasaristas 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.

Vértices
En teoría de grafos, un vértice o nodo es la unidad fundamental de la que están formados los grafos. Un grafo no dirigido estáformado por un conjunto de vértices y un conjunto de aristas (pares no ordenados de vértices), mientras que un grafo dirigido está compuesto por un conjunto de vértices y un conjunto de arcos (pares ordenados de vértices). En este contexto, los vértices son tratados como objetos indivisibles y sin propiedades, aunque puedan tener una estructura adicional dependiendo de la aplicación por la cual se usael grafo; por ejemplo, una red semántica es un grafo en donde los vértices representan conceptos o clases de objetos.
Los dos vértices que conforman una arista se llaman puntos finales, y esa arista se dice que es incidente a los vértices. Un vértice w es adyacente a otro vértice v si el grafo contiene una arista (v,w) que los une. La vecindad de un vértice v es un grafo inducido del grafo,formado por todos los vértices adyacentes a v.


Grados de los Vértices
El grado de un vértice en un grafo es el número de aristas incidentes a él. Un vértice aislado es un vértice con grado cero; esto es, un vértice que no es punto final de ninguna arista. Un vértice hoja es un vértice con grado uno. En un grafo dirigido, se puede distinguir entre grado de salida y grado de entrada; un vértice...