ガブリエルグラフ

出典: ORWiki

【がぶりえるぐらふ (Gabriel graph)】

平面上に配置された有限個の頂点に対して, 次の条件が満たされる2頂点 $\mathrm{P},\mathrm{Q} \,$ の間を辺で結んでできるグラフをガブリエルグラフという: $\mathrm{P} \,$ を中心とし $\mathrm{Q} \,$ を通る円と $\mathrm{Q} \,$ を中心とし $\mathrm{P} \,$ を通る円の内部に同時に含まれる頂点は存在しない. ガブリエルグラフは, ドロネーグラフの部分グラフであり, 相対近傍グラフを部分グラフとして含む.