NAGY gráfban keresek 100csucsú teljes részgráfot. Létezik rá valami működő algoritmust? Ha igen, akkor szívesen fogadnám.

Attól függ mit értesz működő algoritmus alatt. Ha azt hogy egy tetszőleges (véges méretű) gráfra az algoritmus véges idő alatt lefut és helyes eredményt ad akkor triviálisan adható rá ilyen algoritmus.Az más kérdés hogy exponenciális futási idejű.

Triviális alg.: A gráfból válassz ki 100 csúcsot az összes lehetséges módon és ellenőrizd hogy teljes gráfot alkotnak-e! Vagy ha csak pl. 1 db elég akkor az első igenpéldánynál állj meg!

------------------------------

Gyorsítás: Irányítatlan hurokél mentes gráfon melyben minden pontból legalább 100 él van olyan gráfon vizsgáljuk és nincs többszörös él.

Ha nem ilyen a gráfunk akkor alakítsuk át ilyenné mivel az így kapott gráfon a probléma minden megoldása megegyezik az eredeti gráfnak minden megoldásával és fordítva.

Dehát az eredeti gráf G amin dolgozunk az f(G) gráf.

Vagyis az összes hurokélet töröljük, irányítatlanságot megszüntetjük és az összes pontot töröljük melybe 100-nál kevesebb él fut be (ez eddig lineáris idejű). (Ezen a gráfon dolgozunk.)

Általános módszer:

Kiválasztunk egy pontot, az élei mentén kiválasztunk 100 pontot és egyre több pontot az összes lehetséges módon, de mindig csak az élek mentén, dehát 2 csúcsó telj gráf, 3 csúcsú 4 csúcsú ... stb, ha N csúcsból nem lehet N+1 csúcsot kiválasztani akkor visszalépünk és máshogy próbálkozunk az összes lehetséges módon. (Több nagyságrendet is lefaraghatunk a futási időből, de így is exponenciális idejű.)

Speciális esetben:

Ha lehet akkor még szűkítsük a ponthalmazt ha ismert ilyen egyedi tulajdonsága a gráfnak és ezen a ponthalmazon hajtsuk végre az általános módszert. Ha lehet akkor a következő pontot valamilyen heurisztikus módszer szerint válasszuk ki, így akár polinom idejű is lehet vagyis akár kivárható futási idejű is.

Ui.: NP - teljes probléma, de gyakorlatilag ha sikerül jól heurisztikus pontkiválasztó algoritmust találni akkor megoldható, vagy ha elég kicsi lett az f(G) gráf, vagy ha elégé teljeshez közeli az egész gráf akkor várhatóan véletlenszerűen is találunk.

Mért lenne NP telejes probléma? Már a brute force algoritmus, amit az előző hozzászóló írt is "csak" n^100 nagyságrendű max. Bár ettől még a brute force tényleg használhatatlan lehet.

A többi dologgal amit leírt egyetértek. Még esetleg annyit lehet csinálni, hogy a felesleges csúcsok eltávolítása után esetlegesen több darabra széteső gráfon (ill lehet, hogy már kezdetben is több különálló része volt) csak külön külön az egyes darabokon belül kell 100 pontokat kiválasztani.

Tehát ha marad pl 2000 pont, es a gráf "szétesik" 2x1000 pontra, akkor csak 2 * (1000 alatt a 100) esetet kell vizsgálni, nem pedig 2000 alatt a 100-at.