Gestion empresarial


TEORÍA DEL GRAFO Y SUS APLICACIONES

Alberto Rojo
Gonzalo Ruiz
Rodrigo Montelongo





ÍNDICE
Definición (página 3)
Partes de los grafos (página 3)
Tipos de grafos (página 4)
Caracterización de grafos (página 4, 5 y 6)
Introducción aplicaciones de los grafos (página 6)
Principales aplicaciones (página 7,8 y 9)
Bibliografía (página 9)









DEFINICIÓN
La teoríade 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, 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.
La teoría de grafos es una rama de la matemáticas discretas y aplicadas, y esuna disciplina que unifica diversas áreas como combinatoria, álgebra, probabilidad, geometría de polígonos, aritmética y topología.
Un grafo está compuesto por dos conjuntos finitos: Un conjunto de |A| aristas y un conjunto |V| vértices.

PARTES DE LOS GRAFOS
Vértices: Son los objetos representados por punto dentro del grafo.
Aristas: son las líneas que unen dos vértices.
AristasAdyacentes: dos aristas son adyacentes si convergen sobre el mismo vértice.
Aristas Múltiples o Paralelas: dos aristas son múltiples o paralelas si tienen los mismos vértices en común o incidente sobre los mismos vértices.
Lazo: es una arista cuyos extremos inciden sobre el mismo vértice.
Vertice Aislado: es un vértice de grado cero
Vértice pendiente: es aquel grafo que contiene sólo una arista, esdecir tiene grado 1.
Cruce: Son intersecciones de las aristas en puntos diferentes a los vértices.


TIPOS DE GRAFOS
Grafo Sencillo o Simple: se dice que un Grafo G es simple si no tiene aristas cíclicas y existe una sola arista entre dos vértices. También puede ser aquel que no contiene lazos, ni aristas paralelas o dirigidas.
Grafo Completo: un grafo es completo si cada vértice tiene un gradoigual a n-1, donde n es el número de vértice que componen el grafo.
Multigrafo: son grafos en los cuales se ha añadido una orientación a las aristas representadas gráficamente por una flecha.
Grafo dirigido: son grafos en los cuales se ha añadido una orientación a las aristas, representadas gráficamente por unas flechas.
Grafo etiquetado: grafos en los cuales se ha añadido un peso a lasaristas.
Grafo aleatorio: grafo cuyas aristas están asociadas a una probabilidad.
Hipergrafo: grafos en los cuales las aristas tienen más de dos extremos, es decir, las aristas son incidentes a 3 o mas vértices.
Grafo infinito: grafos con conjunto de vértices y aristas de cardinal infinito.

CARACTERIZACIÓN DE GRAFOS
Grafos simples
Un grafo es simple si a lo más existe una arista uniendo dosvértices cualesquiera. 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 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 cadapar de vé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.
En términos matemáticos la propiedad de un grafo de ser 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 conexas", es decir, porciones del grafo, que son conexas cuando se consideran como grafos aislados.


Grafos completos
Un grafo es completo si existen aristas uniendo todos los pares posibles de vé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...