グラフ理論の問いです。

質問

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

回答No.2

178-tall · ベストアンサー

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

… だろう、ということ？

お礼

有難う御座います。

補足

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

回答No.4

jcpmutura

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

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

お礼

誠に有難う御座います。

補足

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

回答No.3

178-tall

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

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

お礼

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

補足

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

回答No.1

maiko0333

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

お礼

有難う御座います。

補足

御証明ください。