Zagadka: graf w SQL
Na początku wyjaśnię, co mnie natchnęło, by się tym zainteresować, otóż możliwość dodawania ludzi do znajomych na portalach społecznościowych. Im więcej, tym lepiej (upraszczając sprawę), stąd w skrajnym (niezdrowym) wypadku można był założyć konta fikcyjne, których celem było by zwiększanie ilości znajomych naszego oryginalnego (wiem, chore).
Dla upozorowania realności moglibyśmy założyć inne kona, które były by znajomymi tych kont i tak w kółko (a właściwie w graf). Doszlibyśmy do sytuacji, gdy istniałaby normalna sieć znajomości (graf, gdzie wierzchołki to ludzie, zaś krawędzie to ich znajomości), która była by dopięta nikłą ilością krawędzi do sieci którą utworzyliśmy. Na styku bylibyśmy oczywiście my (ew ktoś inny, normalny, wtajemniczony w sprawę).
Moje pytanie jest takie: jeśli mamy modelować taką sieć ludzi, którzy się znają (goldenline, n-k, youtube, etc), to jak policzyć ile jest w niej (potencjalnie fikcyjnych) podsieci o ilości ludzi co najmniej 2^n w niej przebywającej, a połączonej z resztą sieci nie więcej niż n krawędziami?
To jest pytanie zarówno jeśli chodzi o wydajność obliczeniową (czy to jest wykonalne?), o to jak to zaimplementować w SQL (jeśli nierealne wydajnościowo, to pomijając tą nierealność) nie używając do tego procedur osadzonych (chodzi mi o schemat bazy danych + zapytanie SQL które wyciągałoby, ile jest takich podsieci przy zadanym n).
Jeśli uważacie, że temat jet niewykonalny czasowo, to potraficie oszacować ile zajęło by na klastrze, na laptopie wyliczenie tego np dla 5000k userów, gdyby np krawędzi było 5-10% wszystkich możliwych, a n z przedziału <3,20> albo jakiegoś innego, normalnego?
To nie jest tak, że mam to zadane na jakiś przedmiot, że pisze komuś taki soft czy coś, pytania te przedstawiam wam, bo uznałem, że temat jest ciekawy, że warto coś takiego sobie rozkmninić. No i to trochę inne niż standardowe pytania o MySQL+PHP, którymi cała sieć jest uwalona.
Napisałem też o tym na programuj.com oraz na uc.
