Wikilibros

Diferencia entre revisiones de «Teoría de grafos»

Explorar historial interactivamente
← Edición anteriorEdición siguiente →
Contenido eliminado Contenido añadido
VisualWikitexto
Sin resumen de edición
Sin resumen de edición
Línea 13:
 
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:
==== RouteGraph problems: ====▼
 
* [[Graph coloring]]:
===Coloramiento de grafos===
** the [[four-color theorem]]
====El teorema de los cuatro colores====
=====** 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:=====▼
▲=====the strong perfect graph theorem=====
=====** [[Independent set =====]]▼
=====the Erd\x{0151}s-Faber-Lov\x{00E1}sz conjecture (unsolved)=====
** [[Clique]]
▲===== the total coloring conjecture (unsolved)=====
▲===== the list coloring conjecture (unsolved)=====
 
* Route problems:
▲==== Graph substructure:=====
** [[Seven bridges of Königsberg]]
▲===== Independent set =====
=====** [[Minimum spanning tree =====]]▼
===== Clique =====
=====** [[Steiner tree =====]]▼
=====** [[Shortest path problem =====]]▼
=====** [[Route inspection problem]] (also called the "Chinese Postman Problem") =====▼
=====** [[Traveling salesman problem =====]]▼
 
* [[Network flow]]s:
▲==== Route problems: ====
=====** [[Max flow min cut theorem =====]]▼
===== Seven bridges of K\x{00F6}nigsberg =====
====* [[Reconstruction conjecture ====]]▼
▲===== Minimum spanning tree =====
▲===== Steiner tree =====
▲===== Shortest path problem =====
▲===== Route inspection problem (also called the "Chinese Postman Problem") =====
▲===== Traveling salesman problem =====
 
====* Graph [[isomorphism]] problems (Graph matching)====▼
==== Network flows: ====
=====** Canonical labeling =====▼
▲===== Max flow min cut theorem =====
=====** Subgraph isomorphism and monomorphisms =====▼
▲==== Reconstruction conjecture ====
=====** Maximal common subgraph =====▼
▲==== Graph isomorphism problems (Graph matching)====
▲===== Canonical labeling =====
▲===== Subgraph isomorphism and monomorphisms =====
▲===== Maximal common subgraph =====
 
 
 
==== Important algorithms ====
 
===== Dijkstra's algorithm =====
===== Kruskal's algorithm =====
===== Nearest neighbour algorithm =====
===== Prim's algorithm =====
Obtenido de «https://es.wikibooks.org/wiki/Teoría_de_grafos»