こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

解決済みの質問

グラフ理論の問いです。

2n 個の点を、2つずつペアにして、交わらない n 本の直線で結べますか。

投稿日時 - 2018-08-13 15:54:33

QNo.9527173

すぐに回答ほしいです

質問者が選んだベストアンサー

あるペアを「直線分」で結ぶ。
  ↓
他のある「点のペア」を「直線分」で結ぶ。
  ↓
その二本の「直線分」が交わることもある。

… だろう、ということ?
  

投稿日時 - 2018-08-14 09:23:44

補足

いえ、交わらない結び方が必ずあるということを証明して頂きたいのです。超立方体を部分・下位の超立方体(超・厚みが1の超・正方形タイルや超・辺長どもが1の超ファイバーも含む)で充填する仕方を、タイリング・テセレーションの仕方と同じく、完全マッチングで算出・構成できることを示して頂きたいのです。(その、下位の物の重心を結んだグラフの完全マッチングで、何とかなりますでしょうか。)

投稿日時 - 2018-08-14 10:34:57

お礼

有難う御座います。

投稿日時 - 2018-08-14 10:25:17

このQ&Aは役に立ちましたか?

0人が「このQ&Aが役に立った」と投票しています

回答(4)

ANo.4

いいえ
平行でない直線は必ず交わります。

2n個の点を,2つずつペアにして、交わらないn本の線分で結ぶ事はできますが、
交わらない直線で結ぶ事はできません。

投稿日時 - 2018-08-14 19:42:34

補足

178-tall 様への補足コメント通り、直線と申しましたのは、直線分の間違いでした。そして、元々の問い自体は解けました。そこで、初めの補足コメントに御座います、完全マッチング云々の問いの御回答を宜しくお願い申し上げます。

投稿日時 - 2018-08-15 08:03:08

お礼

誠に有難う御座います。

投稿日時 - 2018-08-15 07:56:52

ANo.3

どうやら、「超グラフ」の御題らしい。

ならば、御題の「n 本の直線」の「直線」を無視すれば?
  

投稿日時 - 2018-08-14 17:08:26

補足

確かに、直線分と仰る物を知らずに直線と誤記しました。お詫び申し上げます。
また、元々の問いは、小島寛之『無限を読みとく数学入門』の115~117ページに証明がありました。
そこで、補足コメントの完全マッチング云々の問いへの御回答を宜しくお願い申し上げます。

投稿日時 - 2018-08-15 08:12:55

お礼

またまた誠に有難う御座います。

投稿日時 - 2018-08-15 07:58:15

ANo.1

2次元以上なら普通に可能でしょう。

投稿日時 - 2018-08-13 16:00:22

補足

御証明ください。

投稿日時 - 2018-08-14 06:39:30

あなたにオススメの質問