图同构问题是什么？
What is the graph isomorphism problem?
它问两幅图是否只是顶点重命名后的同一结构。该问题既未被证明为NP完全，也未被证明有高效算法，是计算复杂性中的著名灰色地带。
It asks whether two graphs are the same up to renaming vertices. Despite huge effort, it is neither proved NP-complete nor known easy—a famous gray zone of complexity.
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-11-03
来源 · Source
计算复杂性理论；《算法导论》
Computational complexity theory; Introduction to Algorithms
独立核验依据 · Independent verification: 核验依据 1 ISBN 9787111407010（豆瓣书目条目: 算法导论）；本条出处含多部著作，此标识只担保上面点名的这部
#图论 #同构 #复杂性
库拉托夫斯基定理是什么？
What is Kuratowski's theorem?
它给出平面图的特征：一个图是平面的，当且仅当它不含可收缩为 K₅（五顶点完全图）或 K₃,₃（三分图）的子图。这为平面性提供了判定标准。
A graph is planar iff it contains no subgraph contractible to K₅ or K₃,₃. This gives a clean criterion for planarity.
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-08-23 · 2 条独立证据
来源 · Source
Courant & Robbins,《What Is Mathematics?》Oxford University Press,1996 第二版;中译《什么是数学》
R. Courant and H. Robbins, What Is Mathematics?, Oxford University Press, 1996; Chinese ed.
独立核验依据 · Independent verification: 核验依据 2 OPENLIBRARY 标识 /works/OL811195W：What is mathematics?（按标题
#图论 #平面 #禁子图
谱图论是什么？
What is spectral graph theory?
谱图论用图邻接矩阵或拉普拉斯矩阵的特征值研究图的结构，如连通性、社群划分。它是机器学习中图神经网络的重要数学基础。
Spectral graph theory uses eigenvalues of adjacency or Laplacian matrices to study structure like connectivity and communities. It underpins graph neural networks in ML.
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 来源待核验 · Source pending review
来源 · Source
出处备注：本题原挂出处与答案内容不符，已撤回；具体书目待补，暂不展示来源。
本题原挂出处与答案内容不符，已撤回；具体书目待补。
Previous citation withdrawn as unsupported for this answer; a specific source is pending.
#图论 #谱 #特征值
项目管理的‘关键路径’是怎么算出来的？
How is the 'critical path' in project management computed?
把任务画成有向图，沿每条路径累加工期，最长的一条就是关键路径；它上的任何延误都会拖慢整个项目。缩短非关键路径不影响总工期。
Draw tasks as a directed graph and sum durations along each path; the longest path is the critical path, where any delay delays the whole project. Shortening non-critical paths does not change total time.
难度 专业 · 适合 大众
CC BY 4.0 · 来源待核验 · Source pending review
来源 · Source
出处备注：著录仅给书名，无版次与年份；同一书名常对应多个版次，不臆测具体版本。
《运筹学》Hillier 与 Lieberman
Introduction to Operations Research by Hillier and Lieberman
#调度 #关键路径
什么是哈密顿回路？
What is a Hamiltonian cycle?
哈密顿回路是经过每个顶点恰好一次并回到起点的回路。寻找它属于 NP 完全问题，与欧拉回路（走边）不同，它要求走遍顶点。
A Hamiltonian cycle visits every vertex exactly once and returns; finding one is NP-complete, unlike Euler circuits which traverse edges.
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-11-04
来源 · Source
S. A. Cook,《The complexity of theorem-proving procedures》,Proceedings of the third annual ACM symposium on Theory of c,1971 (DOI: 10.1145/800157.805047)
S. A. Cook, 'The complexity of theorem-proving procedures', Proceedings of the third annual ACM symposium on Theory of c, 1971, DOI: 10.1145/800157.805047
独立核验依据 · Independent verification: 核验依据 1 Crossref DOI 10.1145/800157.805047
#图论 #回路
拉姆齐理论说什么？
What does Ramsey theory say?
拉姆齐理论表明：足够大的结构中必然出现某种有序模式。例如任意6人聚会，必有3人互相认识或3人互不认识。
Ramsey theory: large enough structures force order; among any 6 people, 3 mutually know or 3 mutually don't know each other.
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-08-23 · 2 条独立证据
来源 · Source
Graham, Knuth, Patashnik,《Concrete Mathematics》第2版,Addison-Wesley,1994
R. L. Graham et al., Concrete Mathematics, 2nd ed., Addison-Wesley, 1994
独立核验依据 · Independent verification: 核验依据 2 OPENLIBRARY 标识 /works/OL3951639W：Concrete mathematics（按标
#图论 #组合
什么是无向图的最大流—最小割定理?它和线性规划的对偶性有何联系?
State the max-flow min-cut theorem for undirected networks and relate it to linear programming duality.
定理断言网络中 s 到 t 的最大流量等于把 s 与 t 分开的最小割的容量。将最大流写成线性规划后,其对偶问题恰是最小割的整数规划松弛,且约束矩阵的全单模性保证对偶最优解取整值,从而对偶间隙为零——这是 LP 对偶在组合优化中最经典的实例之一。
The theorem says the maximum flow from s to t equals the minimum capacity of an s-t cut. Formulating max-flow as a linear program, its dual is precisely the relaxation of the min-cut integer program; total unimodularity of the constraint matrix guarantees integral dual optima, so there is no duality gap — one of the classic instances of LP duality in combinatorial optimization.
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-10-03 · 2 条独立证据
来源 · Source
Ahuja、Magnanti 与 Orlin《Network Flows》第 6 章,Cormen 等《Introduction to Algorithms》第 26 章亦有完整证明
Ahuja, Magnanti and Orlin, Network Flows, Chapter 6; also Cormen et al., Introduction to Algorithms, Chapter 26 for a full proof
独立核验依据 · Independent verification: 核验依据 1 ISBN 978-0-262-04630-5 · 核验依据 2 ISBN 9780691079516 (1957)
#最大流最小割 #线性规划对偶
谱图论研究什么？
What does spectral graph theory study?
谱图论用图的邻接矩阵或拉普拉斯矩阵的特征值来刻画图的性质，例如第二小拉普拉斯特征值（代数连通度）衡量图的连通强弱，Fiedler 向量用于图划分。
Spectral graph theory uses eigenvalues of adjacency/Laplacian matrices; e.g. the algebraic connectivity (2nd-smallest Laplacian eigenvalue) measures how connected a graph is.
难度 进阶 · 适合 高中(15-18)
CC BY 4.0 · 来源待核验 · Source pending review
来源 · Source
出处备注：本题原挂出处与答案内容不符，已撤回；具体书目待补，暂不展示来源。
本题原挂出处与答案内容不符，已撤回；具体书目待补。
Previous citation withdrawn as unsupported for this answer; a specific source is pending.
#图论 #谱图论
四色定理是什么？
What is the four-color theorem?
它说任意平面地图都可用四种颜色给相邻区域上色而不冲突。它是首个主要依赖计算机验证证明的数学定理。
Any planar map can be colored with four colors so neighbors differ; the first major theorem proved largely by computer.
难度 进阶 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-10-04 · 2 条独立证据
来源 · Source
《图论》Diestel
Graph Theory by Reinhard Diestel
独立核验依据 · Independent verification: 核验依据 1 ISBN 9783662575604 (2018) · 核验依据 2 ISBN 9780582249936 (1996)
#图论 #着色
什么是树（tree）？
What is a tree in graph theory?
树是连通且无环路的无向图，n 个顶点的树恰有 n−1 条边。它常用于表示家谱、文件目录和决策结构。
A tree is a connected graph with no cycles; n vertices have exactly n−1 edges. Used for family trees, file systems, decisions.
难度 进阶 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-08-23 · 2 条独立证据
来源 · Source
Graham, Knuth, Patashnik,《Concrete Mathematics》第2版,Addison-Wesley,1994
R. L. Graham et al., Concrete Mathematics, 2nd ed., Addison-Wesley, 1994
独立核验依据 · Independent verification: 核验依据 2 OPENLIBRARY 标识 /works/OL3951639W：Concrete mathematics（按标
#图论 #树
图着色是什么？
What is graph coloring?
图着色给顶点（或边）分配颜色使相邻者不同色，最少需要的颜色数称为色数。它应用于排课、寄存器分配与频率规划。
Graph coloring assigns colors to vertices so neighbors differ; the minimum number is the chromatic number. It applies to scheduling, register allocation and frequency planning.
难度 进阶 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-08-23 · 2 条独立证据
来源 · Source
Courant & Robbins,《What Is Mathematics?》Oxford University Press,1996 第二版;中译《什么是数学》
R. Courant and H. Robbins, What Is Mathematics?, Oxford University Press, 1996; Chinese ed.
独立核验依据 · Independent verification: 核验依据 2 OPENLIBRARY 标识 /works/OL811195W：What is mathematics?（按标题
#图论 #着色 #色数
最小生成树是什么？
What is a minimum spanning tree?
在带权连通图中，最小生成树是以最小总边权连接所有顶点的无环子图。克鲁斯卡尔与普里姆算法可高效求出它，用于网络布线。
In a weighted connected graph, a minimum spanning tree connects all vertices with smallest total edge weight, acyclic. Kruskal's and Prim's algorithms find it for network design.
难度 进阶 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-08-23 · 2 条独立证据
来源 · Source
Courant & Robbins,《What Is Mathematics?》Oxford University Press,1996 第二版;中译《什么是数学》
R. Courant and H. Robbins, What Is Mathematics?, Oxford University Press, 1996; Chinese ed.
独立核验依据 · Independent verification: 核验依据 2 OPENLIBRARY 标识 /works/OL811195W：What is mathematics?（按标题
#图论 #生成树 #最优化
什么是欧拉路径与欧拉回路？
What are Eulerian paths and circuits?
欧拉路径走遍每条边恰好一次；若起点终点相同则为欧拉回路。一个连通图存在欧拉回路当且仅当每个顶点度数为偶数。
An Eulerian path uses every edge once; a circuit returns to start. A connected graph has an Euler circuit iff every vertex has even degree.
难度 进阶 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-08-23 · 2 条独立证据
来源 · Source
Graham, Knuth, Patashnik,《Concrete Mathematics》第2版,Addison-Wesley,1994
R. L. Graham et al., Concrete Mathematics, 2nd ed., Addison-Wesley, 1994
独立核验依据 · Independent verification: 核验依据 2 OPENLIBRARY 标识 /works/OL3951639W：Concrete mathematics（按标
#图论 #路径
地铁线路图为什么能把弯弯曲曲的线画得又直又整齐？
Why do subway maps draw curvy lines as straight and tidy?
为了易读，制图者舍弃真实地理，只用水平和45度线段表示走向，站距也均匀化。这是用图论抽象保留连接关系、牺牲几何精度的典范。
For readability, mapmakers drop real geography and use only horizontal and 45° segments with even spacing. It is graph theory abstracting connections while sacrificing geometric accuracy.
难度 进阶 · 适合 大众
CC BY 4.0 · 已核验 · Verified 2026-10-03
来源 · Source
《什么是数学》(柯朗)（拓扑章）
What Is Mathematics? (Courant), chapter on topology
#图论之美 #示意图
“小世界”网络是什么？
What are small-world networks?
小世界网络兼具高聚簇与短平均路径，如社交网络中“六度分隔”现象。瓦茨-斯特罗加茨模型用少量随机长边解释这种结构。
Small-world networks combine high clustering with short average paths, like 'six degrees of separation' in social networks. The Watts–Strogatz model explains it with few random long links.
难度 进阶 · 适合 初中(12-15)
CC BY 4.0 · 来源待核验 · Source pending review
来源 · Source
出处备注：著录含书名，但缺版次 / 出版社 / 年份中的一部分，需编辑补全后才能做独立比对。
Milgram, S. (1967), 《小世界问题》, 今日心理学
Milgram, S. (1967), The Small World Problem, Psychology Today
#图论 #网络 #小世界
最短路径算法（如 Dijkstra）做什么？
What does a shortest-path algorithm (e.g. Dijkstra) do?
它在带权图上求从起点到其余各点的最短距离。做法是贪心：每轮从没定下最终距离的点里挑当前距离最小的一个钉死，再用它松弛相邻边。这一步成立的前提是边权全部非负；一旦出现负权边就可能给出错的答案，那得换 Bellman–Ford。代价看实现：朴素做法的开销随顶点数的平方增长，配最小堆只多出一个对数因子。它常被混成旅行商问题，其实后者至今没有已知的多项式算法。
It finds the shortest distances from a source to every other node in a weighted graph. The method is greedy: each round it fixes the unsettled vertex with the smallest current distance and relaxes its outgoing edges. That step is valid only when every edge weight is non-negative; a single negative edge can break the answer, and that is where Bellman-Ford belongs. Cost depends on implementation: the naive version grows with the square of the number of vertices, while a min-heap adds only a logarithmic factor. It often gets confused with the travelling salesman problem, which is the one with no known polynomial-time algorithm.
难度 进阶 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-10-03 · 2 条独立证据
来源 · Source
《算法导论》Cormen 等
Introduction to Algorithms by Cormen Leiserson Rivest and Stein
独立核验依据 · Independent verification: 核验依据 1 ISBN 978-0-262-04630-5 · 核验依据 2 ISBN 9780691079516 (1957)
#图论 #最短路
为什么城市供水或通信网络要做‘冗余’？这和割集有关吗？
Why do water or communication networks build in redundancy, and does it relate to cuts?
最小割告诉我们：只要存在一条把系统切断的薄弱链路集合，系统就会瘫痪。增加平行路径能提高最小割的容量，从而提升鲁棒性。
The min-cut shows that a small set of links can disconnect the system. Adding parallel paths raises the min-cut capacity, improving robustness against failures.
难度 进阶 · 适合 大众
CC BY 4.0 · 已核验 · Verified 2026-10-03 · 2 条独立证据
来源 · Source
Ahuja、Magnanti 与 Orlin《Network Flows》第 6 章,Cormen 等《Introduction to Algorithms》第 26 章亦有完整证明
Ahuja, Magnanti and Orlin, Network Flows, Chapter 6; also Cormen et al., Introduction to Algorithms, Chapter 26 for a full proof
独立核验依据 · Independent verification: 核验依据 1 ISBN 978-0-262-04630-5 · 核验依据 2 ISBN 9780691079516 (1957)
#网络流 #鲁棒性
图的连通性与割点是什么？
What are graph connectivity and cut vertices?
连通图指任意两点间都有路径；割点是删去后使图不再连通的顶点。衡量连通性强弱是网络可靠性分析的核心。
A connected graph has a path between any two vertices; a cut vertex breaks connectivity when removed. Measuring connectivity is central to network reliability.
难度 进阶 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-08-23 · 2 条独立证据
来源 · Source
Courant & Robbins,《What Is Mathematics?》Oxford University Press,1996 第二版;中译《什么是数学》
R. Courant and H. Robbins, What Is Mathematics?, Oxford University Press, 1996; Chinese ed.
独立核验依据 · Independent verification: 核验依据 2 OPENLIBRARY 标识 /works/OL811195W：What is mathematics?（按标题
#图论 #连通 #割点
平面图是什么？
What is a planar graph?
平面图是能画在平面上而边不相交的图。库拉托夫斯基定理刻画了哪些图是平面的，平面图的着色正是四色定理的背景。
A planar graph can be drawn on a plane with no crossing edges. Kuratowski's theorem characterizes planar graphs; their coloring is the setting of the four-color theorem.
难度 进阶 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-08-23 · 2 条独立证据
来源 · Source
Courant & Robbins,《What Is Mathematics?》Oxford University Press,1996 第二版;中译《什么是数学》
R. Courant and H. Robbins, What Is Mathematics?, Oxford University Press, 1996; Chinese ed.
独立核验依据 · Independent verification: 核验依据 2 OPENLIBRARY 标识 /works/OL811195W：What is mathematics?（按标题
#图论 #平面 #嵌入
什么是无标度网络的幂律度分布？为什么这类网络中枢纽节点的存在会显著缩短平均路径长度？
What is the power-law degree distribution of a scale-free network, and why do hub nodes in such networks dramatically shorten average path lengths?
无标度网络的度分布满足 P(k) ∝ k^(−γ)，节点连接数没有典型尺度，少数高度数的枢纽与大量低度数节点共存。随机游走或最短路经过枢纽即可实现大跨度跳跃，使任意两点间的距离主要由“到枢纽的一两步”构成，故平均路径长度随网络增长仅呈对数级上升。
A scale-free network has degree distribution P(k) ∝ k^(−γ): there is no typical node degree, and a few high-degree hubs coexist with many low-degree nodes. Since shortest paths can hop across large distances via one or two hubs, distances between arbitrary nodes consist mostly of steps toward a hub, so average path length grows only logarithmically with network size.
难度 进阶 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-11-04
来源 · Source
Barabási 与 Albert,《Emergence of Scaling in Random Networks》,Science,1999 (DOI: 10.1126/science.286.5439.509)
Barabási, A.-L. & Albert, R., 'Emergence of Scaling in Random Networks', Science, 1999, DOI: 10.1126/science.286.5439.509
独立核验依据 · Independent verification: 核验依据 1 Crossref DOI 10.1126/science.286.5439.509
#无标度网络 #幂律分布
地球上任意两个人之间真的大约只要六次朋友的朋友就能连上吗?
Are any two people on Earth really connected through about six friend-of-a-friend steps?
小世界实验给出过耐人寻味的支持:1967年米尔格拉姆让内布拉斯加的志愿者把信件只交给认识的人转寄,平均经五六人到达波士顿目标。1998年沃茨与斯托加茨用数学解释了它为何可能——只需在大量「近邻连接」中掺入极少数随机远程连接,网络的平均最短路径就会骤降,同时局部抱团结构保留。社交网络时代的亿级数据分析显示平均链长约四五跳,但「可达」不等于「可达且愿意转发」,六度更多揭示了人类关系网的稀疏枢纽结构,而非保证人人都能借道。
The small-world experiment offers suggestive support: in 1967 Milgram had Nebraska volunteers forward letters only through acquaintances, reaching Boston targets in five or six hops on average. In 1998 Watts and Strogatz explained why this is possible — adding just a few random long-range links to a heavily local network collapses average shortest paths while keeping tight clusters. Billion-scale social-network data puts mean chain length around four to six hops, yet reachability is not willingness-to-forward; six degrees exposes the sparse hub structure of human networks rather than guaranteeing any route.
难度 进阶 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-11-02
来源 · Source
Watts 与 Strogatz,《Collective dynamics of small-world networks》,Nature 第393卷,1998
D. J. Watts and S. H. Strogatz, Collective dynamics of small-world networks, Nature 393, 1998
独立核验依据 · Independent verification: 核验依据 1 CROSSREF 标识 10.1038/30918：Collective dynamics of ‘small-
#小世界网络 #六度分隔 #随机图
完全不靠计算机,数学家怎样证明五种颜色必定够用?同样的论证又为何推不到四种颜色?
Without any computer at all, how did mathematicians prove that five colors always suffice, and why does the very same argument fall short at four?
平面图必有度数不超过5的顶点:先删掉它,把剩下的图递归地染好五色,再把顶点放回。若五个邻居没占满五种颜色,补上空色即可;若占满了,就在两种颜色的子图中沿连通块做肯普链交换,总能腾出一个颜色——五色定理由此纯手工成立。而染四色时,度5顶点的五个邻居只分得四种颜色,两条交换链会在交叉之处互相拆台,肯普1879年的证明恰恰漏在这里。
Every planar graph has a vertex of degree at most five: delete it, color the remaining graph recursively with five colors, and put the vertex back. If its five neighbors fail to use all five colors, fill in a free one; if they do, perform a Kempe-chain swap along connected components of some two colors and a slot always opens up — which proves the five-color theorem entirely by hand. With only four colors, however, the five neighbors share four colors and two swapping chains can cross and undo each other; Kempe's 1879 proof broke precisely here.
难度 进阶 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-11-04
来源 · Source
Kempe,《On the Geographical Problem of the Four Colours》,American Journal of Mathematics,1879 (DOI: 10.2307/2369235)；P. J. Heawood,Quarterly Journal of Pure and Applied Mathematics 第24卷332页,1890年
Kempe, 'On the Geographical Problem of the Four Colours', American Journal of Mathematics, 1879, DOI: 10.2307/2369235; P. J. Heawood, Quarterly Journal of Pure and Applied Mathematics 24, 332 (1890)
独立核验依据 · Independent verification: 核验依据 1 Crossref DOI 10.2307/2369235
#肯普链 #五色定理 #平面图着色
肯普1879年的四色定理证明风光了十一年才被推翻——漏洞藏在哪里？它为何反而带来了五色定理？
Kempe announced a four color theorem proof in 1879 that stood for eleven years before being refuted — where did the flaw lie, and how did it still deliver the five color theorem?
漏洞藏在肯普设计的「肯普链」颜色交换操作里：他声称交换两种颜色总能消去一种多余的颜色，希伍德1890年举出反例，说明某些构型下两次交换会互相干扰、无法完成。不过整套方法只需放宽到五种颜色就完全成立，五色定理由此诞生。这段历史也表明，一个流传十余年、备受推崇的「证明」，仍可能埋藏着只在罕见情形才触发的缺陷。
The flaw hid in the color-switching move known as a Kempe chain: Kempe claimed that swapping two colors always eliminates one surplus color, but in 1890 Heawood exhibited configurations where two such swaps interfere and cannot be carried out. Relax the claim to five colors, however, and the whole machinery works perfectly — hence the five color theorem. The episode shows that even a celebrated proof admired for over a decade can harbor defects triggered only in rare cases.
难度 进阶 · 适合 初中(12-15)
CC BY 4.0 · 来源待核验 · Source pending review
来源 · Source
出处备注：著录仅给书名，无版次与年份；同一书名常对应多个版次，不臆测具体版本。
Heawood,《Map-Colour Theorem》,Quarterly Journal of Mathematics 第24卷,1890
P. J. Heawood, Map-Colour Theorem, Quarterly Journal of Mathematics 24, 1890
#肯普链 #五色定理 #反例
什么是图（点线和线）？
What is a graph (dots and lines)?
图由一些点（顶点）和连接点的线（边）组成，用来表示关系，例如朋友关系网。
A graph has dots (vertices) joined by lines (edges) to show relationships, like a friendship network.
难度 入门 · 适合 小学低段(6-8)
CC BY 4.0 · 已核验 · Verified 2026-08-23 · 2 条独立证据
来源 · Source
Graham, Knuth, Patashnik,《Concrete Mathematics》第2版,Addison-Wesley,1994
R. L. Graham et al., Concrete Mathematics, 2nd ed., Addison-Wesley, 1994
独立核验依据 · Independent verification: 核验依据 2 OPENLIBRARY 标识 /works/OL3951639W：Concrete mathematics（按标
#图论 #基础
无标度网络是什么？
What is a scale-free network?
无标度网络的节点度数服从幂律分布：极少数“枢纽”节点连接极多，多数节点连接很少。这使它对抗随机故障强、但对针对性攻击脆弱。
Scale-free networks follow a power-law degree distribution with few hubs and many tiny nodes; robust to random failure but fragile to targeted attacks.
难度 入门 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-11-04
来源 · Source
Barabási 与 Albert,《Emergence of Scaling in Random Networks》,Science,1999 (DOI: 10.1126/science.286.5439.509)
Barabási, A.-L. & Albert, R., 'Emergence of Scaling in Random Networks', Science, 1999, DOI: 10.1126/science.286.5439.509
独立核验依据 · Independent verification: 核验依据 1 Crossref DOI 10.1126/science.286.5439.509
#图论 #无标度
什么是网络中心性？
What is network centrality?
中心性衡量节点在网络中的重要程度。度数中心性看连接数，介数中心性看经过它的最短路径多少，特征向量中心性（如 PageRank）还考虑邻居的重要性。
Centrality measures node importance: degree counts links, betweenness counts shortest paths through it, eigenvector centrality (like PageRank) weights influential neighbors.
难度 入门 · 适合 大众
CC BY 4.0 · 来源待核验 · Source pending review
来源 · Source
出处备注：本题原挂出处与答案内容不符，已撤回；具体书目待补，暂不展示来源。
本题原挂出处与答案内容不符，已撤回；具体书目待补。
Previous citation withdrawn as unsupported for this answer; a specific source is pending.
#图论 #中心性
小世界网络是什么？
What is a small-world network?
小世界网络兼具“高聚集”与“短平均距离”：多数朋友彼此认识，但少数长程连接让任意两人平均只需几步可达（六度分隔）。它是社交与神经网络的特征。
Small-world networks have high clustering yet short average path lengths (six degrees of separation); a hallmark of social and neural networks.
难度 入门 · 适合 高中(15-18)
CC BY 4.0 · 来源待核验 · Source pending review
来源 · Source
出处备注：著录含书名，但缺版次 / 出版社 / 年份中的一部分，需编辑补全后才能做独立比对。
Milgram, S. (1967), 《小世界问题》, 今日心理学
Milgram, S. (1967), The Small World Problem, Psychology Today
#图论 #小世界
哥尼斯堡的七座桥为什么注定无法一次走遍而不重复?
Why was Konigsberg's seven-bridge walk doomed from the start?
1736年欧拉把陆地缩成点、桥画成线,发现能否一次走完只取决于每个点连出的线条数(度数):要想一笔不重复地走完,中途经过的点必须成进成出即度数为偶,只有起点和终点允许奇数。哥尼斯堡四块陆地全是奇度(3、3、3、5),一个奇点都不将就,所以任何路线必然重复某座桥。这项分析诞生了图论与拓扑学的思想雏形——问题的答案藏在连接方式里,与桥的长短宽窄毫无关系。
In 1736 Euler shrank each landmass to a point and each bridge to a line, showing that a single non-repeating tour depends only on how many lines meet at each point (its degree): every intermediate stop needs an even degree, with only start and end allowed odd. All four Konigsberg landmasses had odd degrees (3, 3, 3, 5), so some bridge must be repeated. That argument launched graph theory and prefigured topology — connectivity alone decides, lengths and widths are irrelevant.
难度 入门 · 适合 大众
CC BY 4.0 · 已核验 · Verified 2026-10-04 · 2 条独立证据
来源 · Source
Wilson,《Introduction to Graph Theory》第4版,Longman,1996
R. J. Wilson, Introduction to Graph Theory, 4th ed., Longman, 1996
独立核验依据 · Independent verification: 核验依据 1 ISBN 9783662575604 (2018) · 核验依据 2 ISBN 9780582249936 (1996)
#图论 #欧拉路径 #一笔画
为什么涂色地图的问题可以原封不动地搬进图论,变成给平面图的顶点染色?
Why can the map-coloring problem be translated wholesale into graph theory as coloring the vertices of a planar graph?
把每个国家看成一个点,两国接壤就连一条边,地图立刻化为一幅平面图;相邻国家不同色,恰好等价于相邻顶点不同色。转化之后,边界的歪斜形状、飞地之类的几何细节全部消失,只剩下纯粹的连接关系,还能借助欧拉公式推出平面图必有度数不超过5的顶点这样的利器。四色问题的全部现代研究,正是在这张对偶图上展开的。
Turn every country into a dot and join two dots whenever the countries share a border: the map becomes a planar graph, and requiring neighboring countries to differ in color is exactly requiring adjacent vertices to differ. After the translation, crooked borders and enclaves vanish, leaving pure connectivity, and tools such as Euler's formula apply — for instance, that every planar graph has a vertex of degree at most five. All modern work on the four-color problem unfolds on this dual graph.
难度 入门 · 适合 大众
CC BY 4.0 · 已核验 · Verified 2026-10-04 · 2 条独立证据
来源 · Source
R. Diestel,《Graph Theory》第5版,Springer GTM 173,2016年
R. Diestel, Graph Theory, 5th ed., Springer GTM 173 (2016)
独立核验依据 · Independent verification: 核验依据 1 ISBN 9783662575604 (2018) · 核验依据 2 ISBN 9780582249936 (1996)
#对偶图 #平面图 #图染色