1つのサボテングラフタスク

入学試験の時間が始まります。これは興味深い問題を解決することを意味します。 数年前、 コンピューターサイエンスセンターは応募者にサボテングラフのタスクを処理するよう招待しましたが、今日はそれについてお話します。 自分で問題について考えてから、解決策を確認してください。

ところで、 CSセンターへの募集はすでに進行中です。 今年は、サンクトペテルブルクだけでなく、ノボシビルスクでもフルタイムの登録が可能です。 さあ-教室でさらに面白い。

挑戦する

サボテンは、任意の2つのサイクルに最大1つの共通の頂点がある単純な連結グラフです。 n個の頂点を持つサボテンのエッジの最大数が $$$\ operatorname {floor} \ frac {3} {2}（n-1）$ 。

* $$$\ operatorname {floor}$ -切り捨て。

解決策

まず、このグラフの仕組みを理解する必要があります。 図に示されているグラフの例は、これに役立ちます。 近くは本物のサボテンです。 これにより、この名前の理由を理解できます。

頂点が3つ以上あるサイクルは、長さ3のサイクルと単純なパスを置き換えることで「引き締め」られます。 この場合、グラフ内の頂点とエッジの総数は変化せず、グラフ自体はサボテンのままです。 以下は、グラフを「プル」する例です。

次に、どのサイクルにも存在しないエッジがあるサボテンを考えます。 これらのエッジのいずれか2つを上に引くことができます。 その結果、2つのエッジと2つの頂点がグラフから消えます。 次に、グラフに長さ3のサイクルを追加します。その頂点の1つはグラフの既存の頂点になります。 頂点の数は同じになり、エッジの数は1つ増えます。

上の図は、上記の操作の例を示しています。 左の図は、サイクルの外側のエッジが強調表示されているサボテンを示しています。 中央の図では、同じサボテンですが、rib骨が締め付けられています。 その中で、2つのエッジが消えただけでなく、2つのピークが少なくなりました。 最後に、右の図は、3つの新しいエッジと2つの頂点が表示された別の三角形を追加したサボテンを示しています。 その結果、操作の前後の頂点の数は変化せず、エッジの数が増加しました。

したがって、サボテンの最大数のエッジは、それが完全に三角形で構成され、場合によってはサイクル上にない1つのエッジで構成される場合に達成されます。 このようなサボテンは、次のいずれかで始まる極端な三角形ブロックを連続して追加することで構築できます $$$K_3$ どちらかで $$$K_2$ 、パリティに応じて $$$n$ 。 （ $$$K_n$ -完全なグラフオン $$$n$ 各ブロックが追加されると、2つの頂点と3つのエッジが追加され、そこから問題で必要なステートメントがすぐに続きます。