|
Un grafo en matemáticas e informática es una generalización del concepto simple de un conjunto de puntos, llamados vértices
==Problemas y algoritmos==
==Problemas y algoritmos==
====El teorema de los cuatro colores====
=====the strong perfect graph theorem=====
=====the Erd\x{0151}s-Faber-Lov\x{00E1}sz conjecture (unsolved)=====
===== the total coloring conjecture (unsolved)=====
===== the list coloring conjecture (unsolved)=====
==== Graph substructure:=====
===== Independent set ===== ▼ ===== Clique =====
==== RouteGraph problemssubstructure: =====
===== Seven bridges ofIndependent K\x{00F6}nigsbergset =====
===== Minimum spanning treeClique =====
===== Steiner tree =====
===== Shortest path problem ===== ▼ ===== Route inspection problem (also called the "Chinese Postman Problem") ===== ▼ ===== Traveling salesman problem ===== ▼
==== NetworkRoute flowsproblems: ====
===== Max flowSeven minbridges cutof theoremK\x{00F6}nigsberg =====
===== ReconstructionMinimum conjecturespanning tree =====
▲ ===== IndependentSteiner settree =====
▲ ===== Shortest path problem =====
▲ ===== Route inspection problem (also called the "Chinese Postman Problem") =====
▲ ===== Traveling salesman problem =====
==== Network flows: ====
==== Graph isomorphism problems (Graph matching)==== ▼ ===== CanonicalMax flow min cut labelingtheorem =====
==== Reconstruction conjecture ====
===== Subgraph isomorphism and monomorphisms ===== ▼▲ ==== Graph isomorphism problems (Graph matching)====
===== Maximal common subgraph ===== ▼===== Canonical labeling =====
▲ ===== Subgraph isomorphism and monomorphisms =====
▲ ===== Maximal common subgraph =====
==== Important algorithms ====
===== Dijkstra's algorithm =====
===== Kruskal's algorithm =====
===== Nearest neighbour algorithm =====
===== Prim's algorithm =====
| 