Grafos y RedesCONCEPTO.

La teoría de grafos (también llamada teoría de las gráficas) es un campo de estudio de las matemáticas y las ciencias de la computación, que estudia las propiedades de los grafos (también llamadas gráficas, que no se debe confundir con las gráficas que tienen una acepción muy amplia) estructuras que constan de dos partes, el conjunto de vértices, nodos o puntos; y el conjunto de aristas, líneas o lados que pueden ser orientados o no. Por ello, también se conoce como análisis de redes.

Un grafo, G, es un par ordenado de V y A, donde V es el conjunto de vértices o nodos del grafo y A es un conjunto de pares de vértices, a estos también se les llama arcos o ejes del grafo. Un vértice puede tener 0 o más aristas, pero toda arista debe unir exactamente a dos vértices.

Los grafos representan conjuntos de objetos que no tienen restricción de relación entre ellos. Un grafo puede representar varias cosas de la realidad cotidiana, tales como mapas de carreteras, vías férreas, circuitos eléctricos, etc.

La notación G = A (V, A) se utiliza comúnmente para identificar un grafo.

Los grafos se constituyen principalmente de dos partes: las aristas, vértices y los caminos que pueda contener el mismo grafo.

Aplicaciones1. La síntesis de circuitos secuenciales, contadores o sistemas de apertura. Se utiliza

para diferentes áreas por ejemplo, Dibujo computacional, en toda las áreas de Ingeniería.

2. Modelar trayectos como el de una línea de autobús a través de las calles de una ciudad, en el que podemos obtener caminos óptimos para el trayecto.

3. Para la administración de proyectos, utilizamos técnicas como técnica de revisión y evaluación de programas (PERT) en las que se modelan los mismos utilizando grafos y optimizando los tiempos para concretar los mismos.

4. Desarrollar un concepto no metafórico de red social que sustituye los nodos por los actores sociales y verifica la posición, centralidad e importancia de cada actor dentro de la red. 

5. Se emplea en problemas de control de producción, para proyectar redes de ordenadores, para diseñar módulos electrónicos modernos y proyectar sistemas físicos con parámetros localizados (mecánicos, acústicos y eléctricos).

6. Se usa para la solución de problemas de genética y problemas de automatización de la proyección (SAPR). Apoyo matemático de los sistemas modernos para el procesamiento de la información. 

Ejemplos:

Mapas Conceptuales

Plano de estaciones del metro.

Plano de autopistas.

Circuito eléctrico

Sociograma de una red social

Topología de red de computadores

Organigramas

Isomeros

Arquitectura de redes de telefonía móvil

Ver videos:

Teoría de Grafos en la vida real. Conceptos básicos. Primeros conceptos.Teoría de Redes o GrafosAplicación de la Teoría de Grafos en nuestra vida.

Software a utilizar: grafos y PackTracer de Cisco

Matriz Adyacencia de un Grafo

Todo grafo simple puede ser representado por una matriz, que llamamos matriz de adyacencia.

Se trata de una matriz cuadrada de   filas     columnas (siendo   el número de vértices del grafo).

Para construir la matriz de adyacencia, cada elemento   vale {{1}}

cuando haya una arista que una los vértices   y  . En caso contrario el

elemento   vale 0.La matriz de adyacencia, por tanto, estará formada por ceros y unos.Ejemplo 1

Vamos a construir la matriz de adyacencia del siguiente grafo:

Practica # 1:

Practica # 2:

Practica # 3

Practica # 4:

S

Practica #5, por Conjunto.

Solución

Recorridos y circuitos eulerianos.

Caminos y ciclos hamiltonianos.

Árbol de expansión mínima.

El problema de la ruta más corta.

El problema de flujo máximo.