Teoria De Grafos

Ciclos y caminos hamiltonianos
Artículo principal: Ciclo hamiltoniano

Ejemplo de un ciclo hamiltoniano.
Un ciclo es una sucesión de aristas adyacentes, donde no se recorre dos veces la misma arista, y donde se regresa al punto inicial. Un ciclo hamiltoniano tiene además que recorrer todos los vértices exactamente una vez (excepto el vértice del que parte y al cual llega).
Por ejemplo, en unmuseo grande (al estilo del Louvre), lo idóneo sería recorrer todas las salas una sola vez, esto es buscar un ciclo hamiltoniano en el grafo que representa el museo (los vértices son las salas, y las aristas los corredores o puertas entre ellas).
Se habla también de camino hamiltoniano si no se impone regresar al punto de partida, como en un museo con una única puerta de entrada. Por ejemplo, uncaballo puede recorrer todas las casillas de un tablero de ajedrez sin pasar dos veces por la misma: es un camino hamiltoniano. Ejemplo de un ciclo hamiltoniano en el grafo del dodecaedro.
Hoy en día, no se conocen métodos generales para hallar un ciclo hamiltoniano en tiempo polinómico, siendo la búsqueda por fuerza bruta de todos los posibles caminos u otros métodos excesivamente costosos.Existen, sin embargo, métodos para descartar la existencia de ciclos o caminos hamiltonianos en grafos pequeños.
El problema de determinar la existencia de ciclos hamiltonianos, entra en el conjunto de los NP-completos.
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 cualquieraes 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; 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; esdecir, 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 unapartició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.
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 devé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 regular da cuenta de su peculiar estructura.
Grafos bipartitos
Artículo principal: Grafo bipartitoUn 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 estas condiciones, el grafo se considera bipartito, y puede describirseinformalmente 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.
Operaciones en Grafos
Subdivisión elemental de una arista
se convierte en
Se reemplaza la arista por dos aristas y un vértice w.
Después de realizar esta operación, el...