グラフ - グラフ内の埋め込みとトポロジの違いは何ですか？ <a href="http://www.algorist.com/" rel="noreferrer">Algorithm Design Manual</a>で

Question

、ページ178は、グラフのいくつかのプロパティを記述し、そのうちの一つは、埋め込まれトポロジカルれる：頂点と エッジが幾何学的な位置を割り当てられている場合、グラフが埋め込まれトポロジカル

対埋め込み

。従って、グラフ の任意の図は、アルゴリズム的に重要であるかもしれないし、そうでないかもしれない埋め込みである。

時々、グラフの構造は埋め込みの形状によって完全に定義されます。例えば、飛行機内のポイントの集合 が与えられ、 のすべてを訪問する最小コストのツアーを求める（つまり、旅行セールスマンの問題）場合、基本的なトポロジ は、各頂点のペアを接続する完全なグラフです。重み「 」は、典型的には、各対「 」の間のユークリッド距離によって定義される。

点のグリッドは、ジオメトリからのトポロジの別の例です。 n×mグリッド上の多くの問題は、隣接する ポイント間を歩くことを伴うので、ジオメトリからエッジが暗黙的に定義されます。

私はかなりそれを理解していない：すべての

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

おかげ

Answer 1

1. 私はグラフがちょうど頂点の集合とそれらに定義された辺の集合であるので、頂点が自分の幾何学的な位置を持っていないことを思い出させます。グラフの描画は埋め込みと呼ばれ、描画されたグラフは埋め込みと呼ばれます。
2. グラフを描画する方法は、そのグラフの埋め込みと呼ばれます。
3. トポロジカルグラフは、頂点とエッジがそれぞれ点と弧であるグラフです。各頂点は、友人が住むこの世界の地理的位置に関連付けられているため

Answer 2

Skienaは、埋め込まれたグラフの一例として、地理的な友情のグラフを使用しています。

本の抜粋 - 私の友人は私の近くに住んでいますか？ - ソーシャルネットワークは地理学と離婚していません。あなたの友人の多くは、あなたの近くに住んでいる（例えば、隣人）、またはあなたの近くで暮らしていた（例えば、大学のルームメイト）ために、あなたの友人の多くです。

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

Answer 3

msjの回答に加えて。 Vは頂点が設定され、EはVの頂点のペアに設定されます。これはSkienaのグラフの定義です。このグラフがどのように視覚的に表示されるかについては言及されていません（つまり、そのトポロジは言及されません）。

例（a、bがY座標系、たとえばXに配置されている場合、それは定義されていないことに注意）

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)を指定し、ルールを定義します。たとえば、「各ノードを正確に訪問する」と言うと、「完全なグラフ」と呼ばれるトポロジーを定義します。