離散数学、双対グラフの書き方について

質問

双対グラフの書き方が分かりません
枝と枝に囲まれている部分を一つの頂点と見立てて、最後に全てを繋げて作っていくそうですが
自分の中では下の画像の様に、新しい頂点を繋げているだけなのですがここから先がいまいちよく分かっていません

回答No.4

stomachman · ベストアンサー

ANo.1へのコメントについてです。
　どうも、「領域」だけはお分かりだけど、それ以上はさっぱり、ってことでしょうか。丸投げっぽいけど、ちょっと詳しくやりましょうかね。
　「書き方」的に言うと、えとですね、元の平面グラフの辺に注目するんです。で、元のグラフの各辺eについて、領域の組{p, q}すべてについて、「その辺eだけを横切ってp, qを互いにつなぐように双対グラフの辺が描けるなら、それを1本だけ描く」んです。（ただし{p, q}と{q, p}は同じものとみなして、区別しません。）
　「領域の組{p, q}すべて」とは言っても、「その辺eだけを横切ってp, qを互いつなぐ」ことができるためには、pとqはどちらも「その辺e」を境界に持つ領域でなくてはならないのは明らか。pとqは「eを隔てて互いに隣接」している訳です。逆に言えば、p=qの場合も含めて、元のグラフのどの辺eも「eを隔てて互いに隣接」するようなどれかの領域の組{p, q}を丁度一組だけ持つ。ですから、「元のグラフのあるひとつの辺eだけを横切ってある領域の組{p, q}のpとqを互いに繋ぐ双対グラフの辺と、eだけを横切って別の領域の組{s, t}（≠{p, q}）のsとtを互いに繋ぐ双対グラフの辺とが両方存在する、ということはない」。
　というわけで結局、元のグラフの辺と双対グラフの辺とは1:1対応し、双対グラフの辺の数は元のグラフの辺の数と同じです。

回答No.3

Tacosan

「面に囲まれている部分」って, いったいどこのこと?

例えば「領域A と領域C の境界になっている辺」はどれ?

回答No.2

Tacosan

領域A と領域C の境界になっている辺がどれか, わかりますか?

補足

境界となっているのは面に囲まれている部分を指すのではないのでしょうか？

回答No.1

stomachman

「枝と枝に囲まれている部分」に頂点を対応させた上で、互いに隣接している部分同士に対応する頂点同士をつなぐだけです。「ここから先」はありません。

補足

http://uploda.cc/img/img52dbd66e0e802.jpg

上の画像が答えとなっているのですが、互いに隣接している同士だけという条件だけでは
頂点aにループがあるのと頂点aとcには枝が２本あるのがわからないのですが1*や2*などがありますが
この枝には何か規則等があるのでしょうか？