15

アルゴリズム設計マニュアル（178ページ）では、グラフのいくつかのプロパティについて説明しており、そのうちの1つが埋め込まれていてトポロジカルです。

埋め込みvs.トポロジカル

頂点とエッジに幾何学的位置が割り当てられている場合、グラフが埋め込まれます。したがって、グラフの描画は埋め込みであり、アルゴリズム的に重要な場合とない場合があります。

場合によっては、グラフの構造は、その埋め込みのジオメトリによって完全に定義されます。たとえば、平面内のポイントのコレクションが与えられ、それらすべてを訪問する最小コストのツアーを探す場合（つまり、巡回セールスマン問題）、基礎となるトポロジは、頂点の各ペアを接続する完全グラフです。重みは通常、ポイントの各ペア間のユークリッド距離によって定義されます。

ポイントのグリッドは、ジオメトリからのトポロジのもう1つの例です。n×mグリッドの多くの問題には、隣接するポイント間の歩行が含まれるため、エッジはジオメトリから暗黙的に定義されます。

私はそれを完全に理解していません：

  1. まず第一に、embeddedここで正確に何を意味するのでしょうか？頂点が独自の幾何学的位置を持っている限り、グラフを埋め込みと呼ぶことができますか？
  2. どういうany drawing of a graph is an embedding意味ですか？それは私がポイント1で言ったことを意味しますか？
  3. どういうTopological意味ですか？この説明では説明されていないと思います。
  4. この説明の例は本当に私を混乱させました。誰かが私にグラフのこれらの2つの用語を理解させるために最も簡単な言葉を使ってくれませんか？
  5. これらの2つの用語を理解することは本当に重要ですか？

ありがとう

4

3 に答える 3

5
  1. グラフは単なる頂点のセットとそれらに定義されたエッジのセットであることを思い出してください。したがって、頂点には独自の幾何学的位置はありません。グラフの描画は埋め込みと呼ばれ、描画されたグラフは埋め込みと呼ばれます。
  2. これは、グラフを描画する方法はすべて、そのグラフの埋め込みと呼ばれることを意味します。
  3. トポロジカル グラフは、頂点とエッジがそれぞれ点と弧であるグラフです。
于 2012-04-04T12:22:24.450 に答える
1

msjの回答に加えて。

グラフ = G(V, E)、ここでVは頂点のセットであり、Eは V からの頂点のセットのペアです。これは、Skiena によるグラフの定義です。このグラフが視覚的にどのように表示されるかについては言及されていないことに注意してください (つまり、そのトポロジーについては言及されていません)。

例 (たとえば、X、Y 座標系でa、が配置されている場所を定義していないことに注意してください)b

V = { a, b, c, d, e, f }とE = { (a,b), (b,c), (a,e) }

グラフを「描画」するには、X、Y 座標系などの幾何学的位置を割り当てます。

|
|           b (2,3)
|   a(1,2)
|
|
|____________________________
 Fig 1

図 1 は、指定された頂点のペアを描画する単純な埋め込みです。E

埋め込みグラフとトポロジカル グラフの違いは、「トポロジ」がどのようになるかです。「埋め込み」では、上記で説明したように手動で幾何学的位置を割り当てますが、トポロジカル グラフでは、グラフのトポロジがそれ自体を定義することに基づいて「ルール」を定義します。たとえばG(V,E)、「各ノードを 1 回だけ訪問する」という規則を指定して定義すると、「完全なグラフ」と呼ばれるトポロジが定義されます。

于 2016-10-07T05:21:56.883 に答える
0

Skiena は、各頂点が友人が住んでいるこの世界の地理的なポイントに関連付けられているため、埋め込みグラフの例として地理的友情グラフを使用します。

本からの抜粋 - 私の友達は私の近くに住んでいますか? – ソーシャル ネットワークは地理と切り離されていません。あなたの友人の多くは、たまたまあなたの近くに住んでいるか (例: 隣人)、または以前にあなたの近くに住んでいた (例: 大学のルームメイト) という理由だけで、あなたの友人です。

したがって、ソーシャル ネットワークを完全に理解するには、埋め込まれたグラフが必要です。このグラフでは、各頂点が、この世界の自分が住んでいる場所に関連付けられています。この地理情報は明示的にエンコードされていない可能性がありますが、グラフが本質的に平面に埋め込まれているという事実が、分析の解釈を形作ります。

于 2016-09-25T00:45:21.320 に答える