V2EX  ›  英汉词典

Overlap Graph

Definition / 释义

overlap graph(重叠图):图论与算法中的一种交集图概念。最常见用法是指区间的重叠图:把每个区间看作一个顶点;如果两个区间有交集但互不包含(即“重叠”而非“包含”),就在两顶点之间连一条边。此概念也可推广到其他对象的“重叠关系”建图(不同领域定义细节可能略有差异)。

Pronunciation / 发音(IPA)

/ˌoʊvərˈlæp ɡræf/

Examples / 例句

The overlap graph connects intervals that intersect without one containing the other.
重叠图把那些相交但不存在包含关系的区间连接起来。

By analyzing the overlap graph, we can detect conflicts in the schedule and minimize resource contention.
通过分析重叠图,我们可以发现日程中的冲突,并尽量减少资源争用。

Etymology / 词源

overlapover-(在……之上/越过) + lap(下摆、覆盖的部分) 组合而来,原义含“部分覆盖/压住”。在数学与计算机科学里引申为“部分相交、彼此有共同部分”。graph 源自希腊语词根,现代学术语境中常指“图(由顶点与边构成的结构)”。合起来 overlap graph 即“用图来表示重叠关系”。

Related Words / 相关词

Notable Works / 典籍与著作

  • Martin Charles Golumbic, Algorithmic Graph Theory and Perfect Graphs(讨论多类交集图/完美图相关主题,常涉及区间图与其变体如重叠关系图的语境)
  • Alan M. McConnell, Jeremy P. Spinrad, Modular Decomposition and Transitive Orientation(在可比较图、交集图等相关图类的研究语境中出现)
  • The Handbook of Graph Theory(图论工具书中与交集图、区间图及相关变体的章节常会提及 overlap graph 这一类概念)
关于   ·   帮助文档   ·   自助推广系统   ·   博客   ·   API   ·   FAQ   ·   Solana   ·   913 人在线   最高记录 6679   ·     Select Language
创意工作者们的社区
World is powered by solitude
VERSION: 3.9.8.5 · 11ms · UTC 21:50 · PVG 05:50 · LAX 14:50 · JFK 17:50
♥ Do have faith in what you're doing.