martes, 14 de agosto de 2012

Tipos de grafos


  • Grafo simple. o simplemente grafo es aquel que acepta una sola 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. Es la definición estándar de un grafo.



  • Multigrafo. o pseudografo son grafos que aceptan más de una arista entre dos vértices. Estas aristas se llaman múltiples o lazos. Los grafos simples son una subclase de esta categoría de grafos. También se les llama grafos no-dirigido.




  • Grafo dirigido. Son grafos en los cuales se ha añadido una orientación a las aristas, representada gráficamente por una flecha


  • Grafo etiquetado. Grafos en los cuales se ha añadido un peso a las aristas (número entero generalmente) o un etiquetado a los vértices.


  • 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 más vértices.


  • . Grafos con conjunto de vértices y aristas de cardinal infinito.

La teoria de grafos


La teoría de grafos

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 es una disciplina que unifica diversas áreas como combinatoria, álgebra,probabilidad, geometría de polígonos, aritmética y topología.
Actualmente ha tenido mayor preponderancia en el campo de la informática, las ciencias de la computación y telecomunicaciones.

GRAFOS

 Grafos Dirigidos:


Un grafo dirigido o digrafo es un tipo de grafo en el cual el conjunto de los vértices tiene una dirección definida1 , a diferencia del grafo generalizado, en el cual la dirección puede estar especificada o no.
Al igual que en el grafo generalizado, el grafo dirigido está definido por un par de conjuntos G=(V,A), donde:
  • V\neq\emptyset, un conjunto no vacío de objetos simples llamados vértices o nodos.
  • E \subseteq \{(a,b) \in V \times V: a \neq b \}\, es un conjunto de pares ordenados de elementos de V\, denominados aristas o arcos, donde por definición un arco va del primer nodo (a) al segundo nodo (b) dentro del par.
A veces un digrafo es denominado digrafo simple para distinguirlo del caso general del multigrafo dirigido, donde los arcos constituyen un multiconjunto, en lugar de un conjunto. En este caso, puede haber más de un arco que una dos vértices en la misma dirección, distinguiéndose entre sí por su identidad, por su tipo (por ejemplo un tipo de arco representa relaciones de amistad mientras que el otro tipo representa mensajes enviados recientemente entre los nodos), o por un atributo como por ejemplo su importancia opeso.
A menudo también se considera que un digrafo simple es aquél en el que no están permitidos los bucles. Un bucle es un arco que une un vértice consigo mismo.



Grafos No Dirigidos:

Un grafo no dirigido o grafo propiamente dicho es un grafo G = (V, E) donde:
  • V\neq\emptyset
  • E\subseteq \{x\in\mathcal P(V): |x|=2\} es un conjunto de pares no ordenados de elementos de V\,.
Un par no ordenado es un conjunto de la forma \{a, b\}, de manera que \{a, b\}=\{b, a\}. Para los grafos, estos conjuntos pertenecen al conjunto potencia  de V de cardinalidad 2, el cual se denota por \mathcal P(V).




LOS GRAFOS

PARA COMENZAR HAY QUE SABER QUE SON GRAFOS Y SUS TEORÍAS PARA ASÍ COMPRENDER DE QUE TEMAS ESTAMOS HABLANDO.

 INTRODUCCIÓN:

1. QUE SON GRAFOS
2. HISTORIA
3.  GRAFOS DIRIGIDOS
4. GRAFOS NO DIRIGIDOS
5. TEORÍA DE LOS GRAFOS
6. TIPOS DE GRAFOS


1. QUE SON GRAFOS

En matemáticas ciencias de la computación, un grafo gráfica es el principal objeto de estudio de la teoría de grafos.

Informalmente, un grafo 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.


 2. HISTORIA
Ahora veremos un vídeo para saber un poco mas de este tema  y después veremos la teoría 

VÍDEO:



TEORÍA:

El primer artículo científico relativo a grafos fue escrito por el matemático suizo Leonhard Euler en 1736. Euler se basó en su artículo en el problema de los puentes de Königsberg. La ciudad de Kaliningrado, originalmente Königsberg, es famosa por sus siete puentes que unen ambas márgenes del río Pregel con dos de sus islas. 
De hecho, Euler resuelve el problema más general: ¿qué condiciones debe satisfacer un grafo para garantizar que se puede regresar al vértice de partida sin pasar por la misma arista más de una vez? Si definimos como "grado" al número de líneas que se encuentran en un punto de un grafo, entonces la respuesta al problema es que los puentes de un pueblo se pueden atravesar exactamente una vez si, salvo a lo sumo dos, todos los puntos tienen un grado par.