Zkouskovy priklad

Odeslat odpověď

Smajlíci
:D :) :( :o :shock: :? 8) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:

BBCode je zapnutý
[img] je zapnutý
[flash] je vypnutý
[url] je zapnuté
Smajlíci jsou zapnutí

Přehled tématu
   

Rozšířit náhled Přehled tématu: Zkouskovy priklad

Re: Zkouskovy priklad

od peci1 » 21. 1. 2012 01:06

peci1 píše:
Wegguy píše:Akorat bys tam asi musel dat tri vrcholy a udelat z toho K5, aby byl skutecne nadkubicky.
Spravna pripominka. A jeste potrebuje podobne osetrit i vrcholy se stupnem 3.
A hned jsem si tenhle pristup overil na zkousce :) Funguje perfektne, bez jedine vyhrady.

Takze vrchol s deg(v) = 2 nahradim za: (tady ASCII art uz moc nestaci... proste si tam predstavte K5 :) )

Kód: Vybrat vše

      o---o
     /  x  \
----o------o---
     \  v  /
        o
A vrchol s deg(v) = 3 za

Kód: Vybrat vše

      o---o
     /  x  \
----o------o---
     \  v  /
        o
        |
        |

Re: Zkouskovy priklad

od peci1 » 20. 1. 2012 01:03

Wegguy píše:Akorat bys tam asi musel dat tri vrcholy a udelat z toho K5, aby byl skutecne nadkubicky.
Spravna pripominka. A jeste potrebuje podobne osetrit i vrcholy se stupnem 3.

Re: Zkouskovy priklad

od Wegguy » 20. 1. 2008 16:22

Akorat bys tam asi musel dat tri vrcholy a udelat z toho K5, aby byl skutecne nadkubicky.

Re: Zkouskovy priklad

od gASK » 20. 1. 2008 15:30

Dejme tomu, že umím najít HK pro nadkubický graf. Výše popsaným převodem jsem schopen si libovolný graf převést na nadkubický graf a ten mu předhodit, takže pokud v původním grafu byla HK, on ji najde a naopak. Tedy jsem schopen zjistit existenci HK pro libovolný graf, což je jak víme NPÚ, takže původní problém musí být také NP-úplný. Nevidím na tom nic složitého ani problematického. Stejně tak nevím, v čem by měl být problém se smyčkama - jsou to normální hrany jako každé jiné (v zadání není nic o tom, že by neobsahoval smyčky či tak něco, jediná omezující podmínka je stupeň vrcholů).

EDIT: Tuetschekova verze bude taky fungovat a krom toho je to originální řešení :twisted:

Re: Zkouskovy priklad

od Tuetschek » 20. 1. 2008 15:24

Tuetschek píše:Tohle je fajn, ale uznaji to, kdyz jsou tam smycky? Neslo by to nejak bez nich?
Ted mi napadlo vrchol rozdvojit, pridat dalsi dva vrcholy a udelat si tam maly K4:

Kód: Vybrat vše

    o
   /|\
  / | \
->o-+--o->
  \ | /
   \|/
    o
A pro tohle pak dokazu, ze mam-li HK v tomhle, mam i HK v puvodnim grafu a naopak (HK v K4 se da dodelat jednoduse). Je tahle uvaha ale korektni?

Jako obecne ... ukazat ze nejaky podproblem je stejne tezky jako puvodni problem je v poradku, koukni se treba na 3-SAT a SAT.

Re: Zkouskovy priklad

od matoman » 20. 1. 2008 15:21

tiez sa pripajam k vyssie uvedenej otazke. A navyse to v tom nevidim. Ved opacny prevod teda na HK ze odstranime slucky. Ved nadkubicky graf nemusi vobec obsahovat slucky. A je vobec co dokazovat Prevod HK -> nadkubicky HK,resp. opacne ked je to vlastne iba jeho specialny pripad.
Tento priklad mi je nejaky celkom nejasny

Re: Zkouskovy priklad

od Tuetschek » 20. 1. 2008 15:10

beaver píše:Tak vezmeme si problem HK na obycejnem grafu G. To co bych chtel je, ze tuhle HK umim (polynomialne) prevest na HK pro nadkubicke grafy (tim ukazu, ze HK pro nadkubicke grafy je NPU problem, protoze obyc HK je taky NPU).

Rekneme, ze v G nejsou vrcholy se stupnem 1 (nebo mensim). Kdyby byly, pak tam nemuze HK existovat a umim ji vyloucit v polynomialnim case (coz pro nas neni vubec zajimave). Zaroven predpokladejme, ze zadny vrchol G neobsahuje smycku (tzn. hranu (v, v) pro nejake v). Kdyby graf smycky obsahoval, muzeme je beztrestne odstranit (HK to nijak neublizi).

Vsechny vrcholy v G maji ted stupen 2, nebo vetsi a neobsahuji smycky. Hurra - tak si tam ty smycky pridame (pro kazdy vrchol v, pridame hranu (v,v)). Pokud bereme neorientovane grafy, pak je stupen vsech vrcholu alespon 4.

Takze prevod tam uz mame a prevod zpet je taky jednoduchy - jen zahodime smycky. A to, ze jsou oba prevody polynomialni, je doufam videt. :D
Tohle je fajn, ale uznaji to, kdyz jsou tam smycky? Neslo by to nejak bez nich?

Re: Zkouskovy priklad

od Wegguy » 20. 1. 2008 13:57

Aha...v tom případě řešení z modrého asi funguje, včetně důkazu NP.

Re: Zkouskovy priklad

od gASK » 20. 1. 2008 13:54

V zadání je "maximální z hlediska inkluze" (měl jsem to u zkoušky), takže to je bráno tak, že je to taková množina, že do ní nelze přidat žádný další vrchol, aniž by přestala být nezávislá.

Re: Zkouskovy priklad

od Wegguy » 20. 1. 2008 13:42

No, mně ta definice max. nezávislé množiny s tím řešením taky nesedí. Max. množina = nedá se vybrat větší, barva nebarva.

Ale napadlo mě, co takhle navíc spojit každé dva červené vrcholy (= formule) hranou?

Re: Zkouskovy priklad

od gASK » 13. 1. 2008 13:34

Ok, v tom případě bych tam dal tři klauzule, pak by opět můj dotaz platil.

Ano, pokud to beru tak jak píšeš, tak to samozřejmě smysl dává. Jen to trochu koliduje s tím, co si představím pod pojmem "maximální nezávislá množina". Budiž tedy.

Re: Zkouskovy priklad

od twoflower » 13. 1. 2008 12:51

Ten tvuj priklad udela graf

Kód: Vybrat vše

o ----- o
| \      
|  \
|   \    
O    O
A otazku bych spis chapal takhle: "Lze vybrat na tom grafu takovou mnozinu (pouze) cernych vrcholu, ze je maximalni nezavisla (tj. nelze k ni pridat zadny cerveny vrchol)?" Pak je ta ekvivalence snad jasna..

Re: Zkouskovy priklad

od gASK » 13. 1. 2008 11:37

Ahoj všichni.
Mám také "problém" s jedním zkouškovým příkladem - konkrétně MMNM (Monochromatická maximální nezávislá množina). Pokud si dobře pamatuji, maximální nezávislá množina je největší nezávislá množina na daném grafu co do počtu vrcholů. Potom nechápu, jak může fungovat transformace libovolné formule ze SAT - například (a) AND (a) mi udělá graf O - o - O (O=červené, o=černé), kde MNM je složena výlučně z červených, přitom ta formule je splnitelná. Co mi uniká? Pamatuji si blbě definici MNM nebo je tam nějaký fígl? :?:

Re: Zkouskovy priklad

od beaver » 1. 1. 2008 13:54

Tak vezmeme si problem HK na obycejnem grafu G. To co bych chtel je, ze tuhle HK umim (polynomialne) prevest na HK pro nadkubicke grafy (tim ukazu, ze HK pro nadkubicke grafy je NPU problem, protoze obyc HK je taky NPU).

Rekneme, ze v G nejsou vrcholy se stupnem 1 (nebo mensim). Kdyby byly, pak tam nemuze HK existovat a umim ji vyloucit v polynomialnim case (coz pro nas neni vubec zajimave). Zaroven predpokladejme, ze zadny vrchol G neobsahuje smycku (tzn. hranu (v, v) pro nejake v). Kdyby graf smycky obsahoval, muzeme je beztrestne odstranit (HK to nijak neublizi).

Vsechny vrcholy v G maji ted stupen 2, nebo vetsi a neobsahuji smycky. Hurra - tak si tam ty smycky pridame (pro kazdy vrchol v, pridame hranu (v,v)). Pokud bereme neorientovane grafy, pak je stupen vsech vrcholu alespon 4.

Takze prevod tam uz mame a prevod zpet je taky jednoduchy - jen zahodime smycky. A to, ze jsou oba prevody polynomialni, je doufam videt. :D

Zkouskovy priklad

od joehill » 31. 12. 2007 11:10

Ahoj, koukam na zkouskove priklady z minulych let a s timhle prikladem nemuzu hnout:

Jaka je slozitost HK pro nadkubicke grafy (nadkubicky graf: Pro kazdy vrchol v plati deg(v) > 3)?
Navrhnete polynomialni algoritmus, nebo dokazte ze je NPU.

Na modrem je navrhovano reseni stylem prevodu HK na tento problem, ale to se mi zatim nedari, nevi nekdo, jak na to?

Nahoru