私は現在、グラフの部分グラフを生成する効率的なアルゴリズムを持っています（ブーストライブラリを使用しています）。私の疑問は、一見明らかだが、理論的な面ではより多くの答えがある：無向グラフ、重み付けされていないグラフGの部分グラフSは、G自体を除いて、Gと同じ辺数を持つことができるか？ Sが持つことができる頂点の数に制約はありません。元のグラフと同じ辺数の部分グラフ
私の最初の推測はNoでなければなりませんが、厳密な数学的議論ではなく、「常識と手書き」に基づいています。サブグラフに従わなければならない基準の数学的集合を誰かが知っているのですか？
おかげで、 VV
はい。 Gに孤立した頂点がある場合（1つは辺が内外にありません）、その頂点を削除して得られたGの部分グラフは、同じ数の辺を持ちますが、厳密には少ない頂点しかありません。
Gに孤立した頂点がないとします。 Gの任意の（厳密にはGではない）部分グラフは、Gのすべての頂点を含むか、またはGのいくつかの頂点vを省略しなければならない。前者の場合、Gのすべての辺を持つことはできないか、Gである。後者の場合、v少なくとも1つのインシデントエッジ（前提条件）があり、サブグラフには両方のエンドポイントが含まれていないため、eを含めることはできません。すなわち、vを含んでいません。したがって、Gの任意の部分グラフは、G自体よりも厳密に少ないエッジを有する。
はい - グラフGをisolated vertexとします。この頂点を削除するとGの適切なサブグラフが得られ、そのエッジセットはGのものとまったく同じです。
グラフに孤立した頂点がない場合、答えは「いいえ」です。頂点を削除すると、頂点までのすべての辺incidentが削除されます。各頂点に少なくとも1つのそのようなエッジがあるので（孤立した頂点がないことを覚えておいてください）、エッジの数が減少します。