Teoria de grafos

|teoría de grafos |
| |
|Inés Aparicio Pulido |
| |
|27/01/2011|
| |
|[Escribir el nombre del autor] |

27/1/2011
|Inés Aparicio Pulido|

[pic]

CONTENIDO

Introducción, Definiciones. Pag.s 1-4

Grafos: Definiciones, representación
Pag.s 4-12

Dígrafo, ciclo de un grafo
pag.s 12-14
Estructuras no lineales
Pags 14-15

Ejemplos de representación de grafos
pags 15-19

Bibliografía pag 20Introducción, Definiciones:

Hoy en día podemos ver muchas cosas que nos pueden parecer de lo mas cotidianas, carreteras, líneas telefónicas, líneas de televisión por cable, el transporte colectivo metro, circuitos eléctricos de nuestras casas, automóviles, y tantas cosas mas; lo que no pensamos frecuentemente es que estos forman parte de algo que en matemáticas se denomina como grafos.
Eneste trabajo se tratará de explicar lo que son los grafos, sus tipos, y algunas derivaciones de ellos, así como su representación gráfica y en algunos casos, su representación en algún programa informático, así como en la memoria.
En este trabajo, se está explicando de manera muy sencilla los conceptos y algunas metodologías con un lenguaje no tan rebuscado para su mayor entendimiento.Grafos:

Desafortunadamente no existe una terminología estandarizada en la teoría de los grafos, por lo tanto es oportuno aclarar que las presentes definiciones pueden variar ligeramente entre diferentes publicaciones de estructura de datos y de teoría de grafos, pero en general se puede decir que un grafo como indica su nombre es la representación (para nuestro caso) gráfica de losdatos de una situación particular, ejemplo:
   Los datos contienen, en algunos casos, relaciones entre ellos que no es necesariamente jerárquica. Por ejemplo, supongamos que unas líneas aéreas realizan vuelos entre las ciudades conectadas por líneas (más adelante se presentaran grafos con estructuras de datos); la estructura de datos que refleja esta relación recibe el nombre de grafo.
Sesuelen usar muchos nombres al referirnos a los elementos de una estructura de datos. Algunos de ellos son "elemento", "ítem", "asociación de ítems", "registro", "nodo" y "objeto". El nombre que se utiliza depende del tipo de estructura, el contexto en que usamos esa estructura y quien la utiliza.
En la mayoría de los textos de estructura de datos se utiliza el término "registro" al hacer referenciaa archivos y "nodo" cuando se usan listas enlazadas, árboles y grafos.
También un grafo es una terna G = (V,A,j ), en donde V y A son conjuntos finitos, y j es una aplicación que hace corresponder a cada elemento de A un par de elementos de V. Los elementos de V y de A se llaman, respectivamente, "vértices" y "aristas" de G, y j asocia entonces a cada arista con sus dos vértices.

Estadefinición da lugar a una representación gráfica, en donde cada vértice es un punto del plano, y cada arista es una línea que une a sus dos vértices.

► Aristas:

Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos.

Si la arista carece de dirección se denota indistintamente {a, b} o {b, a}, siendo a y b los vértices que une.

Si {a ,b} es una...