Fisica

TEORIA DE GRÁFOS
* Elementos y Características
* Representación
* Algoritmos de recorrido y búsqueda
* Aplicaciones
* Arboles
* Redes

TEORIA DE GRAFOS
El concepto de gráficos es tan simple que resulta difícil creer que su estudio se haya convertido en una de las áreas más ricas de las matemáticas.
Gran parte de los problemas que se le examinara surge de situacionesprácticas de la vida real y aunque a primera vista padecen de naturaleza distinta en todos ellos se puede identificar un sistema de objetos que están relacionados de alguna manera. En cada problema podemos hacer un diagrama en el que los objetos están representados por puntos y las interconexiones están representadas por líneas y al diagrama le llamamos grafo.
C
D
E
B
A
LAZO
ARISTAMULTIPLE
ARISTA
VERTICE
El proceso de representar un problema cotidiano en términos matemáticos se conoce como modelación matemática.

Ejemplo de un grafo

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 (onodos) 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 de puntos (los vértices) conectados por líneas (las aristas).
Conceptos Básicos
Grafo

En la figura, V = { a, b, c, d, e, f }, y A = { ab, ac, ae, bc, bd, df, ef }.
Un grafo es una pareja de conjuntos G = (V,A), donde V es elconjunto de vértices, y A es el conjunto de aristas, este último es un conjunto de pares de la forma (u,v) tal que , tal que .

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 yrelaciones que satisfagan la definición de grafo pueden verse como grafos y así aplicar la Teoría de Grafos en ellos.
1º Grado de un vértice: es el número de aristas que se encuentran en ese vértice y se representa de la siguiente manera.
gr(A)=5
2º Vértice adyacente: dos vértices son adyacentes si existe una arista que losuna.

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 grafosorientados, 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).
En el grafo anterior se ha utilizado una arista que tiene sus dos extremos idénticos: es un lazo (o bucle), y aparece también una arista bidireccional, y corresponde a dos aristas orientadas.

3ºAristas adyacentes: Son adyacentes si comparten un vértice.
4º Trayectoria: Es una sucesión de vértices con la propiedad de que cada vértice es adyacente al siguiente y tal que en la correspondiente sucesión de aristas todas las aristas son distintas por ejemplo:
A
B
C
D
E

Caracterización de grafos
Grafos simples
Un grafo es simple si a lo sumo sólo 1 arista une dos vérticescualesquiera. 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 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...