matematicas

Teoría de Grafos


        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) estructuras que constan de dos partes, el conjunto de vértices, nodos o puntos; y el conjunto dearistas, líneas o lados (edges en inglés) que puedenser orientados o no.

La teoría de grafos es una rama de la matemáticas discretas y aplicadas, y es una disciplina que unifica diversas áreas como combinatoria, álgebra,probabilidad, geometría de polígonos, aritmética y topología.


La Teoría de Grafos es parte de Matemáticas Discreta que es una asignatura del plan de estudios de Ingeniería en Informática, que tiene un marcado enfoque práctico, aplicado ycomputacional, además de un acentuado carácter formativo. El contenido referido a esta temática se plantea como respuesta a una variada serie de problemas de la «vida real» (diseño de bloques, flujo de redes, diseño de circuitos, transporte de viajeros, asignaciones horarias o de tareas, programación, etc.), lo que le confiere el enfoque aplicado que señalamos arriba, aprendiendo el alumno,además, a buscar modelos matemáticos adecuados para gran número de situaciones diferentes, lo que suele ser muy habitual en el desarrollo profesional.

Componentes de un grafo (vértices, aristas, lazos, valencia)


         Aristas.- Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos.
Aristas Adyacentes: Se dice que dos aristas son adyacentes sicoinciden en el mismo vértice
Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial y el final son el mismo
Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo

Cruce: Son dos aristas que cruzan en un puntos

Vértices.- Son los puntos o nodos con los que esta conformado un grafo.

Llamaremos grado de un vértice al número de aristas de las que esextremo. Se dice que un vértice es `par' o `impar' según lo sea su grado.
Vértices Adyacentes: si tenemos un par de vértices de un grafo (U, V) y si tenemos un arista que los une, entonces U y V son vértices adyacentes y se dice que U es el vértice inicial y V el vértice adyacente.
Vértice Aislado: Es un vértice de grado cero.
Vértice Terminal: Es un vértice de grado 1

Lazo: es una aristacuyos extremos inciden sobre el mismo vértice


Valencia de un vértice.- Es el numero de lados que salen o entran a un vértice. En el grafo anterior las valencias de los vértices son:

Valencia (a)=2
Valencia (b)=4
Valencia (c)=2
Valencia (d)=3

Hay que observar como en el caso del vértice del lazo solo se considera una vez, entrada o salida pero no ambos.

Tipos de grafos (Simples,completos, bipartidos, planos, conexos, ponderados)

            Grafos simples.- Un grafo es simple si a lo más existe una arista uniendo dos vé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.

Grafo completo.- Un grafo es completo si existen aristas uniendo todos los paresposibles 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 K, siendo Kn  el grafo completo de n vértices. Un Kn, es decir, grafo completo de n vértices tiene exactamente n(n-1)/2  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 es bipartito si puede expresarse como G = {V1 U V2, A} (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...