Diferencia entre revisiones de «Teoría de grafos»

Contenido eliminado Contenido añadido
Sin resumen de edición
Sin resumen de edición
Línea 1:
=Teoría de Grafos=
 
Este es un Wikilibro que estamos escribiendo los estudiantes de que cursan de Teoría de Grafos en la Pontificia Universidad Javeriana. Por lo pronto es sólo un esbozo y está en un estado embrionario. . En la medida en que el seminario avance, el texto lo hará también. Por favor considere mirar la página de discusión y participe de la construcción de este proyecto.
 
El enfoque que se sigue en este curso intenta brindar una aproximación práctica con un énfasis en las implementaciones computacionales de algunos programas para grafos. En ese sentido hemos intentado seguir el orden de presentación de la inspiradora obra de Richard Johnsonbaugh, Matemáticas Discretas, sin embargo hemos apelado a texto original o cubierto bajo licencia GFDL, o cualquier otra que permita colocar dichos contenidos de acuerdo al espíritu del proyecto Wikibooks.
Línea 15:
 
* Conceptos Previos:
**[[Teoria_de_grafos:Relaciones de recurrencia|Relaciones de recurrencia]]
**[[Teoria_de_grafos:Algoritmo|Algoritmo]]
***[[Teoria_de_grafos:Algoritmo:Notacion|Notacion]]
Línea 25 ⟶ 26:
* [[Teoria_de_grafos:Referencias externas|Referencias externas]]
 
=='''¿Cómo se puede representar un grafo?'''==
 
En realidad no existe una manera única de representar un grafo; en la actualidad existen formas muy conocidas de representar un grafo:
 
*''Matriz de incidencia:''
*''Lista de incidencia:''
*''Matriz de adyacencia:''
*''Lista de adyacencia:''
 
 
Línea 38 ⟶ 31:
 
La teoria de grafos proporciona unas herramientas para resolver problemas que nos presentan cierto tipo de complejidad, y que no se habian podido resolver antes que Euler tratara de dar solucion al problema de los puentes de Konigsberg. se destacan entre ellos los siguientes:
== Problemas de grafos ==
 
* [[Coloramiento de grafos]]:
** the [[four-color theorem]]
** the [[perfect graph|strong perfect graph theorem]]
** the [[Erdös-Faber-Lovász conjecture|Erdős-Faber-Lovász conjecture]] (unsolved)
** the [[total coloring|total coloring conjecture]] (unsolved)
** the [[list edge-coloring|list coloring conjecture]] (unsolved)
 
* Graph substructure:
** [[Independent set]]
** [[Clique]]
 
* Route problems:
** [[Seven bridges of Königsberg]]
** [[Minimum spanning tree]]
** [[Steiner tree]]
** [[Shortest path problem]]
** [[Route inspection problem]] (also called the "Chinese Postman Problem")
** [[Traveling salesman problem]]
 
* [[Network flow]]s:
** [[Max flow min cut theorem]]
* [[Reconstruction conjecture]]
 
* Graph [[isomorphism]] problems (Graph matching)
** Canonical labeling
** Subgraph isomorphism and monomorphisms
** Maximal common subgraph