Diferencia entre revisiones de «Teoría de grafos»

El primer libro sobre teoría de grafos fue escrito por [[Dénes Kőnig]] y publicado en [[1936]].<ref>{{citation|last1=Tutte|first1=W.T.|authorlink=W. T. Tutte|title=Graph Theory|publisher=[[Cambridge University Press]]|year=2001|isbn=978-0-521-79489-3|page=30|url=http://books.google.com/books?id=uTGhooU37h4C&pg=PA30}}.</ref>

 

* '''Aristas''': Son las líneas con las que se unen los vértices de un grafo.

** '''Aristas adyacentes''': 2 aristas son adyacentes si convergen en el mismo vértice.

* '''Camino''': Se denomina camino de un grafo a un conjunto de vértices interconectados por aristas. Dos vértices están conectados si hay un camino entre ellos.

 

* '''Grafo simple:''' O simplemente ''grafo'' es aquel que acepta una sola 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:''' Es el que acepta más de una arista entre dos vértices. Estas aristas se llaman ''múltiples'' o ''lazos'' (''loops'' en [[idioma inglés|inglés]]). Los ''grafos simples'' son una subclase de esta categoría de grafos. También se les llama ''grafos general''.

* '''[[Grafo regular]]:''' Un grafo es regular cuando todos sus vértices tienen el mismo grado de valencia.

 

{{AP|Grafo (estructura de datos)}}

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 [[grafo disperso|grafos dispersos]] porque tienen un eficiente uso de la memoria. Por otro lado, las matrices proveen acceso rápido, pero pueden consumir grandes cantidades de memoria.

</center>

 

 

===Subgrafos, subgrafos inducidos y menores===