グラフの「圧縮」に関するスタックオーバーフローについて質問があります。有限集合 T からのタグと有限集合 O からのオブジェクトがあるとします。さらに、T の集合の要素から集合 O の要素への (単方向の) リンクがあります。たとえば、すべてのリンクは次の形式です。
(a,b) ここで、a は T に属し、b は O に属します。セット O は T に比べて巨大になる可能性があり、その結果、グラフが巨大になる可能性があります。しかし、例を挙げましょう
O={o1,o2,o3}} および T={t1,t2,t3} とします。
許可されたリンクの完全なセットがあります
グラフに非表示ノード h を挿入すると、リンク付きのグラフを作成できます
(o1,h)、(o2,h)、(o3,h)、(h,t1)、(h,t2)、(h,t3)
次に、次のように定義すると、タグ付けが保持されます。
「オブジェクト o は、o から t へのパスがある場合、タグ t を持ちます」。
ご覧のとおり、定義は非表示ノードで不変です。
さらに、以前は 9 つのリンクがありましたが、ノードの数が 1 つ増えて 6 つになりました。
N 個のオブジェクトと M 個のタグを持つ完全にリンクされたケースの場合、ゲインは次のようになります。
(NM)/(N+M) N が増加するとゲインが M になる傾向があります。
あなたはそのような研究を知っていますか？これはどのカテゴリの問題に属しますか? また、オンラインのケースにも非常に興味があります。
前もって感謝します。