grafos

Republica bolivariana de Venezuela
Ministerio del poder popular para la educación
Liceo bolivariano Rafael medina Jiménez
Barinas edo. Barinas


Los grafos




Profesor(a) Alumnos(as)
Heysel sierra
Jefferson mena


Barinas, Marzo del 2014
Índice
Grafos…………………………………………………………………………
Historia degrafos……………………………………………………….
Teoría de los grafos…………………………………………………….
Representación de grafos…………………………………………..
Problema de teoría de grafos……………………………………..
Coloración de grafos…………………………………………………..
Teorema de los cuatros colores………………………………….
Caracteristicas de grafos…………………………………………….
Arboles………………………………………………………………………
Diámetro …………………………………………………………………..

Grafo
En matemáticas y ciencias de la computación,un grafo (del griego grafos: dibujo, imagen) es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto. Son objeto de estudio de la teoría de grafos.
Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas).
Desde un punto de vista práctico,los grafos permiten estudiar las interrelaciones entre unidades que interactúan unas con otras. Por ejemplo, una red de computadoras puede representarse y estudiarse mediante un grafo, en el cual los vértices representan terminales y las aristas representan conexiones (las cuales, a su vez, pueden ser cables o conexiones inalámbricas).
Prácticamente cualquier problema puede representarse medianteun grafo, y su estudio trasciende a las diversas áreas de las ciencias y las ciencias sociales.
Historia
El origen de la teoría de grafos se remonta al siglo XVIII con el problema de los puentes de Königsberg, el cual consistía en encontrar un camino que recorriera los siete puentes del río Pregel (54°42′12″N 20°30′56″E) en la ciudad de Königsberg, actualmente Kaliningrado, de modo que serecorrieran todos los puentes pasando una sola vez por cada uno de ellos. El trabajo de Euler sobre el problema titulado Soluto problematiza ad geometría situé pertinentes (La solución de un problema relativo a la geometría de la posición) en 1736, es considerado el primer resultado de la teoría de grafos.
Teoría de grafos
La teoría de grafos (también llamada teoría de las gráficas) es un campo deestudio de las matemáticas y las ciencias de la computación, que estudia las propiedades de los grafos (también llamadas gráficas, que no se debe confundir con las gráficas que tienen una acepción muy amplia) estructuras que constan de dos partes, el conjunto de vértices, nodos o puntos; y el conjunto de aristas, líneas o lados (edges en inglés) que pueden ser orientados o no.
La teoría de grafos esuna rama de la Matemática discreta y de las aplicadas, y es un tratado que usa diferentes conceptos de diversas áreas como Análisis combinatorio, Álgebra abstracta, probabilidad, geometría de polígonos, aritmética y topología.
Representación de grafos
Existen diferentes formas de representar un grafo (simple), además de la geométrica y muchos métodos para almacenarlos en una computadora.La estructura de datos usada depende de las características del grafo y el algoritmo usado para manipularlo. Entre las estructuras más sencillas y usadas se encuentran las listas y las matrices, aunque frecuentemente se usa una combinación de ambas. Las listas son preferidas en grafos dispersos porque tienen un eficiente uso de la memoria. Por otro lado, las matrices proveen acceso rápido, pero puedenconsumir grandes cantidades de memoria.
Estructura de lista
Lista de incidencia - Las aristas son representadas con un vector de pares (ordenados, si el grafo es dirigido), donde cada par representa una de las aristas.
Lista de adyacencia - Cada vértice tiene una lista de vértices los cuales son adyacentes a él. Esto causa redundancia en un grafo no dirigido (ya...