圖形上的點對數

圖上有n個點。 m對這些點連接在一起。沒有兩個相互交叉。現在第（m + 1）對必須繪製成不與任何其他線段相交。給定點和連接對的數目，使得第（m + 1）個線段是不可能的。圖形上的點對數

例如：3點和2對：1-2和2-3。現在連接第三對不是不可能的。所以這是被接受的。

如何判斷是否在給定的情況下，連接另一對是不可能或不？

你被允許添加的邊緣後，重新繪製圖形，或是節點的位置和連接它們的特定曲線是否固定？ – templatetypedef

您可能會重繪。然而，在連接m對之後，不應該添加任何配置的新邊緣。 –

也許閱讀[平面圖]（https://en.wikipedia.org/wiki/Planar_graph）和[瓦格納定理]（https://en.wikipedia.org/wiki/Wagner%27s_theorem）。 – MvG

線段必須是直線還是曲線？您可以通過查看凸多面體的歐拉特徵來獲得答案。如果圖形包含的邊多於邊，則可以繪製額外的線。嘗試繪製僅包含三角形面圖，並猜測之間V，E的關係，和F隨後嘗試通過感應來證明這一點

2016-02-25 10:49:38 nielsle

回答