之间图论和组合数学相似
图论和组合数学有(在联盟百科)4共同点: 一笔画问题,四色定理,邮递员问题,NP完全。
一笔画问题
一笔画问题是图论中一个著名的问题。一笔画问题起源于柯尼斯堡七桥问题。数学家欧拉在他1736年发表的论文《柯尼斯堡的七桥》中不仅解决了七桥问题,也提出了一笔画定理,顺带解决了一笔画问题Janet Heine Barnett, 。一般认为,欧拉的研究是图论的开端。 与一笔画问题相对应的一个图论问题是哈密顿问题。.
一笔画问题和图论 · 一笔画问题和组合数学 ·
四色定理
四色定理是一个著名的数学定理:如果在平面上劃出一些邻接的有限区域,那么可以用四种颜色来给这些区域染色,使得每两个邻接区域染的颜色都不一样;另一个通俗的说法是:每个无外飞地的地图都可以用不多於四种颜色来染色,而且不會有两个邻接的区域颜色相同。被称为邻接的两个区域是指它们有一段公共的边界,而不仅仅是一个公共的交点。例如右图左下角的圆形中,红色部分和绿色部分是邻接的区域,而黄色部分和红色部分则不是邻接区域。 “是否只用四种颜色就能为所有地图染色”的问题最早是由一位英国制图员在1852年提出的,被称为“四色问题”或“四色猜想”。人们发现,要证明宽松一点的“五色定理”(即“只用五种颜色就能为所有地图染色”)很容易,但四色问题却出人意料地异常困难。曾经有许多人发表四色问题的证明或反例,但都被证实是错误的。 1976年,数学家凱尼斯·阿佩爾和沃夫冈·哈肯借助电子计算机首次得到一个完全的证明,四色问题也终于成为四色定理。这是首个主要借助计算机证明的定理。这个证明一开始并不为许多数学家接受,因为不少人认为这个证明无法用人手直接验证。尽管随着计算机的普及,数学界对计算机辅助证明更能接受,但仍有数学家希望能够找到更简洁或不借助计算机的证明。.
邮递员问题
邮递员问题(也称邮路问题,Route Inspection Problem,或中国邮路问题,China Route Inspection Problem,或中国邮递员问题Chinese Postman Problem)是一个图论问题。此問題為在一個連通的無向圖中找到一最短的封閉路徑,且此路徑需通過所有邊至少一次。 簡單來說,邮递员问题就是在一個已知的地區,郵差要設法找到一條最短路徑,可以走過此地區所有的街道,且最後要回到出發點, 此問題是圖遍歷問題的一種。无向图的中国邮路问题是容易解决的,是P问题;而有向图的中国邮路问题是NP完全问题。中国邮递员问题由管梅谷教授在1960年提出,而美國國家標準和技術研究院(NIST)的 Alan Goldman 首先將此問題命名为中国邮路问题。.
图论和邮递员问题 · 组合数学和邮递员问题 ·
NP完全
NP完全或NP完備(NP-Complete,縮寫為NP-C或NPC),是計算複雜度理論中,決定性問題的等級之一。NPC問題,是NP(非決定性多項式時間)中最難的決定性問題。因此NP完備問題應該是最不可能被化簡為P(多項式時間可決定)的決定性問題的集合。若任何NPC問題得到多項式時間的解法,那此解法就可應用在所有NP問題上。更詳細的定義容下敘述。 一個NPC問題的例子是子集合加總問題,題目為 這個問題的答案非常容易驗證,但目前沒有任何一個夠快的方法可以在合理的時間內(意即多項式時間)找到答案。只能一個個將它的子集取出來一一測試,它的時間複雜度是Ο(2n),n是此集合的元素數量。.
上面的列表回答下列问题
- 什么图论和组合数学的共同点。
- 什么是图论和组合数学之间的相似性
图论和组合数学之间的比较
图论有49个关系,而组合数学有24个。由于它们的共同之处4,杰卡德指数为5.48% = 4 / (49 + 24)。
参考
本文介绍图论和组合数学之间的关系。要访问该信息提取每篇文章,请访问: