Teoria de grafos

UNIDAD 6

TEORIA DE GRAFOS
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 se representa mediante una serie depuntos (los vértices) conectados por líneas (las aristas).
ELEMENTOS Y CARACTERISTICAS
COMPONENTES DE UN GRAFO
Vértice: Los vértices constituyen uno de los dos elementos que forman un grafo. Como ocurre con el resto de las ramas de las matemáticas, a la Teoría de Grafos no le interesa saber qué son los vértices. Diferentes situaciones en las que pueden identificarse objetos y relaciones quesatisfagan la definición de grafo pueden verse como grafos y así aplicar la Teoría de Grafos en ellos.
Aristas dirigidas y no dirigidas: En algunos casos es necesario asignar un sentido a las aristas, por ejemplo, si se quiere representar la red de las calles de una ciudad con sus direcciones únicas. El conjunto de aristas será ahora un subconjunto de todos los posibles pares ordenados de vértices, con(a, b) ≠ (b, a). Los grafos que contienen aristas dirigidas se denominan grafos orientados, como el siguiente: Las aristas no orientadas se consideran bidireccionales para efectos prácticos (equivale a decir que existen dos aristas orientadas entre los nodos, cada una en un sentido).

TIPOS DE GRAFOS
Grafos simples: Un grafo es simple si sólo 1 arista une dos vértices cualesquiera. Esto esequivalente a decir que una arista cualquiera es la única que une dos vértices específicos. Un grafo que no es simple se denomina Multigráfica o Gráfo múltiple.
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 fuertemente conexo si cada par devé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 de ser (fuertemente) conexo permite establecer con base en él una relaciónde 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.

Grafos completos: Un grafo es completo si existen aristas uniendo todos los pares posibles devé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 regular da cuenta de su peculiar estructura.
Grafos bipartitos: Un grafo G esbipartito 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 describirse informalmentecomo 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 ponderados o etiquetados: 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...