APUNTES TEORIA DE GRAFOS

Teoría de Grafos y Aplicaciones

Prof. Leonardo Román Olmedo García
Email: rolmedo@apolo.acatlan.unam.mx

Miércoles 21 de Enero de 2015

Teoría de grafos (matemática)
Teoría de redes (aplicada)
Funciones continuas
Funciones discretas

Bibliografía:
Vararajan Matemáticas discretas Mc Graw Hill 2008
Johnsonbaugh Matemáticas discretas 6ª edición Prentice Hall 2005

Lectura:
Unidad Teoría de Grafoso de Gráficos (Unidad 8)
Johnsonbaugh Matemáticas discretas 6ª edición Prentice Hall 2005

Examen:
Unidades 5 y 6 primer parcial






¿Qué es una gráfica?

Una gráfica está formada por un conjunto de vértices y un conjunto de aristas que unen pares de vértices. Es un objeto matemático abstracto y su estudio permite modelar problemas reales.

Un grafo o gráfica simple es una estructura matemáticaque consta de un par ordenado de conjuntos (V, E), siendo V ≠ 0.

Los elementos de V se llaman vértices y los elementos de E se llaman aristas. Notemos que en un grafo simple, una arista es un par (x, y) no ordenado de vértices diferentes.

Un ejemplo de un grafo G = (V, E) viene dado por los conjuntos

V = {1, 2, 3, 4}
E = {{1, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 4}}

Llamaremos orden al cardinal delconjunto de vértices V y tamaño al cardinal del conjuntos de aristas E.

Por lo tanto G es un grafo de orden 4 y tamaño 5.

Ejemplo:
V= {1, 2, 3}
E = {{1, 2}, {1, 3}, {2, 3}, {3, 3}}

Orden = 3
Tamaño = 4



Observaciones

El grado de un vértice v, se denomina g(v), es el número de aristas de un grafo que inciden en v. Los vértices de grado 0 reciben el nombre de vértices aislados, mientras quelos de grado 1 se denominan vértices terminal o extremo.

Un lazo es una arista que tiene tanto como origen como por destino un nodo v, y contribuye al grado, se llama lazo o bucle.

Definiciones

Se dice que dos nodos son adyacentes si el grafo contiene al menos una arista que los une. Del mismo modo, dos aristas son adyacentes si poseen un vértice común.

Un subgrafo de un grafo G es un grafocuyos vértices y aristas pertenecen a V(G) y E(G) respectivamente.

Una gráfica simple es aquel en el que todo par de nodos está unido por, a lo sumo, una arista.

Un dígrafo, D, o grafo orientado, es un grafo formado por un conjunto de nodos V(D) y un conjunto de arcos o aristas orientadas A(D) (tienen sentido o flechas de dirección).

Un grafo completo es un grafo en el que todos los pares de nodosson adyacentes estando conectados por una arista. El número de aristas de un grafo de este tipo de n vértices es por tanto n(n-1)/2.

Un grafo regular es aquel cuyos nodos tienen el mismo grado.




Miércoles 28 de Enero de 2014

Libro:http://eva.sepyc.gob.mx:8383/greenstone3/sites/localsite/collect/ciencia1/index/assoc/HASH01be/9b711740.dir/12060025.pdf;jsessionid=8BBA1099AA47DC02634AD41380F4F2B4

http://eva.sepyc.gob.mx:8383/greenstone3/sites/localsite/collect/ciencia1/index/assoc/HASH01be/9b711740.dir/12060025.pdf

Teoría de gráficas con aplicaciones Murphy, North Holland

Clasificación de grafos

Un grafo es bipartito si su conjunto de vértices V(G) puede expresarse como dos subconjuntos V1 y V2 de modo que todas las aristas del grafo unen nodos de conjuntos diferentes.


CuboGrafo conexo

Se dice que un grafo es conexo si todos sus vértices están conectados a través de alguna secuencia de aristas del grafo.

Trayectoria

Se denomina trayectoria a un grafo cuyas aristas forman una secuencia en la que todos los nodos a excepción del primero y el último, son diferentes. Una trayectoria en la que coinciden el primer y último vértice, se denomina circuito.

Observaciones

Silas aristas E1, E2, …, Ek de un camino W son distintas, W se llama pista. Si además los vértices V1, V2, …, Vk de W son distintos, W se llama trayectoria.



Definición

Un camino en G es una sucesión no nula finita W = V1K1, V2K2, …, VnKn cuyos términos son vértices y arcos alternados



W = u, 1, y, 5, x, 8, w, 7, v
Trayectoria =
Pista = u, 1, y, 5, x, 8, w, 6, y

Gráficas dirigidas (Grafo...