Teoria de Grafos

William Danilo Banchón Vargas
Lógica Matemática DSE03
TEORÍA DE GRAFOS
Introducción
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 (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 de puntos (los vértices) conectados por líneas (las aristas).
Historia
El trabajo de Leonhard Euler, en 1736, sobre el problema de los puentes de

Königsberg es considerado el primer resultado de la teoría de grafos. También
se considera uno de los primeros resultados topológicos en geometría (que no
depende de ninguna medida). Este ejemplo ilustra la profunda relación entre la
teoría de grafos y la topología.
En 1845 Gustav Kirchhoff publicó sus leyes de los circuitos para calcular el
voltaje y la corriente en los circuitos eléctricos.
En 1852 Francis Guthrie planteó el problema de los cuatro colores que plantea
si es posible, utilizando solamente cuatro colores, colorear cualquier mapa de
países de tal forma que dos países vecinos nunca tengan el mismo color. Este
problema, que no fue resuelto hasta un siglo después por Kenneth Appel y
Wolfgang Haken, puede ser considerado como el nacimiento de la teoría de
grafos. Al tratar de resolverlo, los matemáticos definieron términos y conceptos

teóricos fundamentales de los grafos.
Tipos de Grafos
Grafo acíclico
Es aquel grafo no contiene ningún ciclo simple.
Grafo cíclico
Un grafo se dice cíclico si contiene algún ciclo simple.
Grafo bipartito
Un grafo bipartito es cualquier grafo, cuyos vértices pueden ser divididos en dos
conjuntos, tal que no haya aristas entre los vértices del mismo conjunto. Se ve
que un grafo es bipartito si no hay ciclos de longitud impar.
Grafo completo
Un grafo es completo si cada vértice tiene un grado igual a n-1, donde n es el

número de vértice que compone el grafo. Además es un grafo simple en el que
cada vértice es adyacente a cualquier todo otro vértice.
Grafo conexo
Decimos que es un grafo conexo, si es posible formar un camino desde cualquier

vértice a cualquier otro en el grafo.
Grafo denso
Un grafo denso es aquel grafo en el que el número de aristas está cercano al

número de máximo de aristas.
Grafo dirigido
Es un conjunto de vértices V y un conjunto de aristas E tal que para cada arista

perteneciente al conjunto de aristas E se asocia con dos vértices en forma
ordenada.
Grafo no dirigido
Son aquellos grafos en los cuales los lados no están orientados (no son flechas).
Cada lado se representa entre paréntesis, separando sus vértices por comas
Grafo nulo
El grafo nulo es el grafo cuyos conjuntos de aristas y de vértices son vacíos.

Grafo plano
Un grafo plano es uno que es posible dibujar en el plano sin que ningún par de
aristas se crucen entre sí.
Grafo ponderado
Un grafo ponderado es aquel que asocia un valor o peso a cada arista en el

grafo. El peso de un camino en un grafo con pesos es la suma de los pesos de
todas las aristas atravesadas.
Grafo regular
Un grafo regular es un grafo cuyos vértices tienen el mismo grado.

Grafo simple
Un grafo simple es un grafo o dígrafo que no tiene bucles, y que no es un

multígrafo.
Grafo no Simple
Grafo no dirigido que tiene lados paralelos y lazos.
Grafo trivial
Un grafo trivial es aquel grafo vacío con un único vértice.
Grafo vacío
Un grafo vacío es el grafo cuyo conjunto de aristas es vacío.

Aplicaciones
Gracias a la teoría de grafos se pueden resolver diversos problemas como por

ejemplo la síntesis de circuitos secuenciales, contadores o sistemas de apertura.
Se utiliza para diferentes áreas por ejemplo, Dibujo computacional, en todas las
áreas de Ingeniería.
Los grafos se utilizan también para 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 aplicando diversos algoritmos como puede ser
el algoritmo de Floyd.
Para la administración de proyectos, utilizamos técnicas como PERT en las que

se modelan los mismos utilizando grafos y optimizando los tiempos para
concretar los mismos.
La teoría de grafos también ha servido de inspiración para las ciencias sociales,

en especial para 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. Esta medida permite cuantificar y
abstraer relaciones complejas, de manera que la estructura social puede
representarse gráficamente. Por ejemplo, una red social puede representar la
estructura de poder dentro de una sociedad al identificar los vínculos (aristas),
su dirección e intensidad y da idea de la manera en que el poder se transmite y
a quiénes.
Ejemplo de Aplicación
Una de las aplicaciones más importantes y más usadas de los grafos en los
mapas, es para determinar e intentar disminuir el tiempo y camino en recorridos
entre sitios distintos.
En el siguiente ejemplo vemos rutas en un mapa, en las cuales determinaremos

varias distancias entre varios puntos.
Para ir de la ciudad P a la ciudad F, existen al menos 5 rutas; pero el objetivo de

los grafos aquí es identificar y aplicar el camino más corto entre los 2 vértices. El
camino más corto para llegar de P a F, es el que contenga menos aristas en su
recorrido hacia el vértice final. En este caso sería {P, O, M, L, J, F}.

Teoria de Grafos

Cargado por

Copyright:

Formatos disponibles

Teoria de Grafos

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Teoria de Grafos

Cargado por

Copyright:

Formatos disponibles

William Danilo Banchón Vargas

Lógica Matemática DSE03

En matemáticas y en ciencias de la computación, la teoría de grafos (también

El trabajo de Leonhard Euler, en 1736, sobre el problema de los puentes de

grafos. Al tratar de resolverlo, los matemáticos definieron términos y conceptos

Es aquel grafo no contiene ningún ciclo simple.

Un grafo se dice cíclico si contiene algún ciclo simple.

Un grafo es completo si cada vértice tiene un grado igual a n-1, donde n es el

Decimos que es un grafo conexo, si es posible formar un camino desde cualquier

Un grafo denso es aquel grafo en el que el número de aristas está cercano al

Es un conjunto de vértices V y un conjunto de aristas E tal que para cada arista

El grafo nulo es el grafo cuyos conjuntos de aristas y de vértices son vacíos.

Un grafo ponderado es aquel que asocia un valor o peso a cada arista en el

Un grafo regular es un grafo cuyos vértices tienen el mismo grado.

Un grafo simple es un grafo o dígrafo que no tiene bucles, y que no es un

Grafo no dirigido que tiene lados paralelos y lazos.

Un grafo trivial es aquel grafo vacío con un único vértice.

Un grafo vacío es el grafo cuyo conjunto de aristas es vacío.

Gracias a la teoría de grafos se pueden resolver diversos problemas como por

Para la administración de proyectos, utilizamos técnicas como PERT en las que

La teoría de grafos también ha servido de inspiración para las ciencias sociales,

En el siguiente ejemplo vemos rutas en un mapa, en las cuales determinaremos

Para ir de la ciudad P a la ciudad F, existen al menos 5 rutas; pero el objetivo de

También podría gustarte