https://orsj-ml.org/orwiki/wiki/index.php?action=history&feed=atom&title=%E5%B9%BE%E4%BD%95%E3%82%B0%E3%83%A9%E3%83%95
幾何グラフ - 版の履歴
2026-04-09T19:13:15Z
このウィキのこのページに関する変更履歴
MediaWiki 1.35.3
https://orsj-ml.org/orwiki/wiki/index.php?title=%E5%B9%BE%E4%BD%95%E3%82%B0%E3%83%A9%E3%83%95&diff=9701&oldid=prev
Imahori: 基礎編と用語編のマージ
2008-03-13T14:24:30Z
<p>基礎編と用語編のマージ</p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="ja">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">2008年3月13日 (木) 14:24時点における版</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >1行目:</td>
<td colspan="2" class="diff-lineno">1行目:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>'''【きかぐらふ (geometric graph)】'''</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>'''【きかぐらふ (geometric graph)】'''</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">=== 概要 ===</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>平面に, 辺が交差しないように実際に描かれた平面グラフを幾何グラフという. 地図における行政区境界を表わす図や, ユークリッド距離のもとでの最小全域木などがその例である.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>平面に, 辺が交差しないように実際に描かれた平面グラフを幾何グラフという. 地図における行政区境界を表わす図や, ユークリッド距離のもとでの最小全域木などがその例である.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">詳しくは</del>[[<del class="diffchange diffchange-inline">《幾何グラフ》</del>|<del class="diffchange diffchange-inline">基礎編：幾何グラフ</del>]]<del class="diffchange diffchange-inline">を参照.</del></div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">=== 詳説 ===</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> 頂点と辺の間の接続関係を指定することによって定義される抽象的なグラフに対して, 頂点と辺を実際に平面に描いて表したグラフを</ins>[[<ins class="diffchange diffchange-inline">幾何グラフ]] (geometric graph) という. 特に, 平面グラフを辺が互いに端点以外では交差しないように描いた幾何グラフが重要である. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> <math>S=\{ {\rm P}_1, {\rm P}_2, \cdots , {\rm P}_n\}\, </math> を平面上に指定された有限個の点の集合とする. 簡単のために, 以下では <math>S\, </math> に属すどの 4 点も同一円周上にはないものと仮定する. <math>S\, </math> に属す 2 点を通り他の点を内部に含まない円が存在するときその 2 点を辺で結ぶことによって, 一つの幾何グラフが得られる. この幾何グラフは <math>S\, </math> に対する[[ドロネー図]] (Delaunay diagram) とよばれる. ドロネー図は <math>S\, </math> の[[凸包]] (convex hull) の内部を三角形に分割した図形となる. この三角形分割はできるだけふっくらとした三角形を使った分割となっているため, 有限要素法などのためのメッシュとしても使われている. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> ドロネー図の辺は, 互いに近い点同士をつないだものとみなすことができる. したがって, ドロネー図は不規則に配置された点に対して「隣り同士」の関係を定義するものとみなすことができる. 実際, 次に示すように, 近さに基づいて定義されたいくつかのグラフはドロネー図の部分グラフとなっている. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> <math>{\rm P}_i, {\rm P}_j \in S\, </math> に対して, <math>{\rm P}_i\, </math> と <math>{\rm P}_j\, </math> の距離を半径とし <math>{\rm P}_i\, </math> を中心とする円と <math>{\rm P}_j\, </math> を中心とする円の共通部分に <math>S\, </math> の他の要素が含まれないとき <math>{\rm P}_i\, </math> と <math>{\rm P}_j\, </math> を線分で結ぶことによってできる幾何グラフは, [[ガブリエルグラフ]] (Gabriel graph) とよばれる. ガブリエルグラフはドロネー図の部分グラフである. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> <math>{\rm P}_i, {\rm P}_j \in S\, </math> に対して, <math>{\rm P}_i\, </math> と <math>{\rm P}_j\, </math> の距離を半径とし <math>{\rm P}_i\, </math> を中心とする円と <math>{\rm P}_j\, </math> を中心とする円のどちらにも<math>S\, </math> に属す他の点が含まれないとき <math>{\rm P}_i\, </math> と <math>{\rm P}_j\, </math> を線分で結ぶことによってできる幾何グラフは[[相対近傍グラフ]] (relative neighborhood graph)とよばれる. 相対近傍グラフはガブリエルグラフの部分グラフである. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> 各 <math>{\rm P}_i \in S\, </math> に対して, <math>{\rm P}_i\, </math> を始点とし, <math>{\rm P}_i\, </math> に最も近い<math>S-\{ {\rm P}_i \}\, </math> の要素を終点とする有向辺を集めてできるグラフは[[最近傍グラフ]] (nearest neighbor graph) とよばれる. 最近傍グラフにおいて有向辺で結ばれている 2点の間に線分をひくことによって得られる幾何グラフは, ガブリエルグラフの部分グラフである. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> <math>S\, </math> の凸包の辺から成る図形も幾何グラフである. この幾何グラフもドロネー図の部分グラフである. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> <math>S\, </math> に属す点を頂点とする木 (連結で無サイクルなグラフ) で, 辺の長さの和が最小のものを, [[最小全域木]](minimum spanning tree)という. 最小全域木もドロネー図の部分グラフである. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> <math>S\, </math> に対するドロネー図は <math>{\rm O}(n\log n)\, </math> の計算量で求めることができる. したがって上に述べた幾何グラフは, まずドロネー図を計算し, その辺のみを候補として辺を探すことにより効率よく構成することができる. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> 新たに頂点を設けてもよいという条件のもとで <math>S\, </math> に属すすべての頂点をつなぐ辺長の和が最小の木を[[シュタイナー木]] (Steiner tree) という. シュタイナー木の効率のよい構成法は知られていない. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> <math>S\, </math> に属す点の対でその距離が最小のものを[[最近点対]] (nearest pair) という. 最近点対はドロネー図の辺である. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> <math>S\, </math> に属す点の対でその距離が最大のものを[[最遠点対]] (farthest pair)という. 最遠点対は <math>S\, </math> の凸包の頂点のいずれかの対によって実現される. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> 平面上に描かれた多角形 <math>T\, </math> に, <math>T\, </math> の内部のみを通過するすべての対角線を加えた幾何グラフを <math>T\, </math> の[[可視グラフ]] (visibility graph)という. このグラフでは一般に辺が交差するため, 平面グラフとは限らない. <math>T\, </math> のある頂点からもう一つの頂点へ移動する <math>T\, </math> 内の最短経路は, 可視グラフの中で最短経路を探すことによって得られる. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> 多角形 <math>T\, </math> 内のすべての点を見渡すことのできる, できるだけ少数の監視点を<math>T\, </math> 内に配置する問題は, [[美術館監視問題]] (art gallery problem)とよばれる. この問題の解法にも可視グラフが役立つ.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">[[Category:計算幾何</ins>|<ins class="diffchange diffchange-inline">きかぐらふ</ins>]]</div></td></tr>
</table>
Imahori
https://orsj-ml.org/orwiki/wiki/index.php?title=%E5%B9%BE%E4%BD%95%E3%82%B0%E3%83%A9%E3%83%95&diff=8348&oldid=prev
2007年8月8日 (水) 12:11にKanda.kによる
2007-08-08T12:11:14Z
<p></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="ja">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">2007年8月8日 (水) 12:11時点における版</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l2" >2行目:</td>
<td colspan="2" class="diff-lineno">2行目:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>平面に, 辺が交差しないように実際に描かれた平面グラフを幾何グラフという. 地図における行政区境界を表わす図や, ユークリッド距離のもとでの最小全域木などがその例である.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>平面に, 辺が交差しないように実際に描かれた平面グラフを幾何グラフという. 地図における行政区境界を表わす図や, ユークリッド距離のもとでの最小全域木などがその例である.</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">詳しくは[[《幾何グラフ》|基礎編：幾何グラフ]]を参照.</ins></div></td></tr>
</table>
Kanda.k
https://orsj-ml.org/orwiki/wiki/index.php?title=%E5%B9%BE%E4%BD%95%E3%82%B0%E3%83%A9%E3%83%95&diff=6312&oldid=prev
Orsjwiki: "幾何グラフ" を保護しました。 [edit=sysop:move=sysop]
2007-07-19T23:41:07Z
<p>"幾何グラフ" を保護しました。 [edit=sysop:move=sysop]</p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<tr class="diff-title" lang="ja">
<td colspan="1" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="1" style="background-color: #fff; color: #202122; text-align: center;">2007年7月19日 (木) 23:41時点における版</td>
</tr><tr><td colspan="2" class="diff-notice" lang="ja"><div class="mw-diff-empty">(相違点なし)</div>
</td></tr></table>
Orsjwiki
https://orsj-ml.org/orwiki/wiki/index.php?title=%E5%B9%BE%E4%BD%95%E3%82%B0%E3%83%A9%E3%83%95&diff=2469&oldid=prev
122.17.2.240: 新しいページ: ''''【きかぐらふ (geometric graph)】''' 平面に, 辺が交差しないように実際に描かれた平面グラフを幾何グラフという. 地図における行...'
2007-07-11T02:54:31Z
<p>新しいページ: ''''【きかぐらふ (geometric graph)】''' 平面に, 辺が交差しないように実際に描かれた平面グラフを幾何グラフという. 地図における行...'</p>
<p><b>新規ページ</b></p><div>'''【きかぐらふ (geometric graph)】'''<br />
<br />
平面に, 辺が交差しないように実際に描かれた平面グラフを幾何グラフという. 地図における行政区境界を表わす図や, ユークリッド距離のもとでの最小全域木などがその例である.</div>
122.17.2.240