algorithm - グラフが平面になるようにスター グラフ間のエッジの数を制限する

Question

星形グラフのみで構成されるグラフGがあります。スター グラフは、他のすべてのノードへのエッジを持つ 1 つの中央ノードで構成されます。H ₁、H 2 _、 …、H _nを、 Gに存在するさまざまなサイズのさまざまな星形グラフとします。任意のスター グラフの中心であるすべてのノードのセットをRと呼びます。

ここで、これらのスター グラフが他のスター グラフにエッジを構築し、Rのどのノード間にもエッジが発生しないとします。次に、グラフが平面のままである場合、RのノードとRにないノードの間に最大でいくつのエッジが存在しますか?

そのようなエッジの数の上限が必要です。私が念頭に置いている上限の 1 つは、 Rが頂点の 1 つのセットであり、残りの頂点が別のセットAを形成する 2 部平面グラフと見なすことです。これらのセット ( RとA ) の間のエッジに関心があります。これは平面の 2 部であるため、このようなエッジの数はGのノード数の 2 倍に制限されます。

私が感じているのは、おそらくAのノードの 2 倍にRのノード数を加えた、より良い境界があるということです。

私の直感を反証していただけるなら、それもいいですね。うまくいけば、あなたの何人かが、いくつかの関連する議論とともに適切な境界を思いつくことができます.

Answer 1

それがあなたにできる最善のことです。任意の平面グラフ G を取り、その面 - 頂点の入射グラフ H を作成します。面にはすべて 4 つのエッジがあります。R を G の面の集合とし、H の辺を使用して任意の方法で星を構成します。これにより、2 部平面グラフの境界が達成されます。