## 摘要

Methods of statistical mechanics are applied to two important NP-complete combinatorial optimization problems. The first is the chromatic number problem, which seeks the minimal number of colors necessary to color a graph such that no two sites connected by an edge have the same color. The second is partitioning of a graph into q equal subgraphs so as to minimize intersubgraph connections. Both models are mapped into a frustrated Potts model, which is related to the q- state Potts spin glass. For the first problem, we obtain very good agreement with numerical simulations and theoretical bounds using the annealed approximation. The quenched model is also discussed. For the second problem we obtain analytic and numerical results by evaluating the groundstate energy of the q=3 and 4 Potts spin glass using Parisi's replica symmetry breaking. We also perform some numerical simulations to test the theoretical result and obtain very good agreement.

原文 | ???core.languages.en_GB??? |
---|---|

頁（從 - 到） | 513-529 |

頁數 | 17 |

期刊 | Journal of Statistical Physics |

卷 | 48 |

發行號 | 3-4 |

DOIs | |

出版狀態 | 已出版 - 8月 1987 |