Pýtame sa, či existuje šestica vektorov x1,2, x1,3, x1,4, x2,3, x2,4, x3,4 v trojrozmernom priestore, ktorá charakterizuje súvislosť obyčajných grafov so štyrmi vrcholmi týmto spôsobom: Graf s hranami h1, h2, ..., hn je súvislý vtedy a len vtedy, keď sa každý vektor v trojrozmernom priestore dá napísať ako lineárna kombinácia vektorov xh1, xh2, ..., xhn.
Ekvivalentná formulácia príkladu: Pýtame sa, či existuje šestica bodov x1,2, x1,3, x1,4, x2,3, x2,4, x3,4 v trojrozmernom priestore s nasledovnou vlastnosťou: Graf s hranami h1, h2, ..., hn je nesúvislý vtedy a len vtedy, keď existuje rovina prechádzajúca počiatkom súradnicového systému obsahujúca súčasne všetky body xh1, xh2, ..., xhn.
11 komentárov:
Dobrý tetraéder nie je zlý :-)
goober: Tak tejto "nápovede" nerozumiem ani ja :) Počkajme si ale pár dní či nezareaguje aj niekto ďalší.
goober: Už som to pochopil (som teda riadne hlúpy). Pomýlilo ma to, že moja všeobecná konštrukcia vedie k odlišnej konfigurácii bodov a keď som si prečítal Tvoju nápovedu, tak ma hneď nenapadlo, že úloha má nekonečne veľa na prvý pohľad nie veľmi podobných riešení.
Ja som povodne uplne nepochopil zadanie, ale po gooberovom hinte sa mi trochu vyjasnilo.
Je to myslene takto? Mame n+1 vrcholovy graf. Vrcholom priradime vrcholy nedegenerovaneho simplexu teda napr.
v_0=0, v_1=e_1, ... v_n=e_n, kde e_i je baza R^n. Potom x_ij=v_i-v_j, ak i>j a je v tom grafe prislusna hrana, inak x_ij=0.
Brano: Vektory x_(1,2), x_(1,3), ..., x_(3,4) majú byť fixné (pre všetky grafy na štyroch vrcholoch) a také, že platí: (Akýkoľvek) graf na vrcholoch 1,2,3,4 s určený hranami (i_1,j_1),...,(i_k,j_k) je súvislý vtedy a len vtedy, keď je span vektorov x_(i_1,j_1),...,x_(i_k,j_k) rovný R^3.
Riešení (šestíc vektorov, ktoré majú vlastnosť uvedenú vyššie) je nekonečne veľa a goober našiel jedno z nich...
A máš pravdu, že podobná konštrukcia funguje aj vo viacrozmernom priestore, len tam je to už ťažšie na predstavivosť.
Tento príklad možno znie neprehľadne, ale podľa mňa je principiálne zaujímavý, pretože poukazuje na úzku súvislosť teórie grafov a lineárnej algebry. Ja som sa tomu príkladu prepracoval cez pojem Laplacianu grafu.
Tak teraz tomu nerozumiem. Ak by tie vektory boli fixne pre vsetky grafy, tak ich span nebude zavisiet od toho aky to je graf a teda ani od toho ci je suvisly nie? A Ak su tie vektory funkcie zavisle od vyberu grafu, tak potom si myslim, ze tak ako som to napisal by malo byt korektne. To, ze tie moje x_ij (a myslim, ze goober to myslel takto) rozhodnu o suvislosti sa da nahliadnut jednoducho napr. indukciou vzhladom na dlzku cesty.
Braňo: Ja som to zadanie myslel tak, že fixných je tých 6 vektorov x_(1,2), x_(1,3), ..., x_(3,4); prítomnosť/neprítomnosť hrán v grafe určuje to, ktoré z týchto vektorov vyberieš.
Príklad 1: Predpokladajme, že máš graf (s vrcholmi očíslovanými 1,2,3,4), ktorého množina hrán je {(1,2), (1,3), (1,4)}. Vyberieš z danej šestice fixných vektorov len tri vektory a to konkrétne x_(1,2), x_(1,3), x_(1,4). Keďže daný graf je súvislý, tak span týchto troch vektorov musí byť R^3.
Príklad 2: Máš graf na množine vrcholov 1,2,3,4, ktorého množina hrán je {(1,2), (1,3), (2,3)}. Tento graf je nesúvislý (4 je izolovaný vrchol), preto x_(1,2), x_(1,3), x_(2,3) musia byť kolineárne (ich span nie nie R^3).
Aha tak uz mi je to jasne. Potom x_ij=v_i-v_j a to ze x_ij nezaradim do mnoziny z ktorej budem robit span je to iste ako to ze tam zaradim x'_ij=0 ako som to napisal povodne. Inak ma napadlo, ze sa to da pekne zovseobecnit na orientovane grafy. Znova x_ij=v_i-v_j aj pre i>j aj pre i<j a zaradime ho tam, ak v grafe mame orientovanu hranu z j do i. A potom bude obojstranne(?) suvisly - (neviem ako sa to vola, ale myslim tym, ze z kazdeho vrcholu sa bude dat dostat do kazdeho a aj spat) prave vtedy ked tie vybrane x_ij vygeneruju cely priestor tak, ze sa pouziju iba kladne koeficienty. Pre stvorvrcholovy graf teda treba 12 vektorov.
Sranda, nevidim tu nikde edit. Tak len taka drobnost: nie kladne koeficienty, ale nezaporne.
Braňo: To je veľmi zaujímavé čo si uviedol s tým orientovaným grafom (inak, volá sa to myslím silná súvislosť). Keď mi zvýši čas, zamyslím sa nad tým trochu viac.
Áno, tá Braňova vlastnosť je silná súvislosť.
Ono by to malo fungovať aj s kladnými koeficientami, nie len nezápornými. V jednom smere je to jasné -- ak sa dá celý priestor vygenerovať kladnými, dá sa aj nezápornými kombináciami. V opačnom smere si zase stačí uvedomiť, že v silnosúvislom grafe existuje ku každej orientovanej hrane aj "cesta späť" (t.j. postupnosť hrán z jej koncového vrcholu do začiatočného). Inak povedané, každá hrana je súčasťou nejakého uzavretého ťahu. Súčet vektorov zodpovedajúcich uzavretému ťahu je nulový vektor (keďže končí tam, kde začal). No a ak takéto "nulové" kombinácie spočítame pre všetky hrany, dostaneme linéarnu kombináciu vyjadrúcu nulový vektor, v ktorej má každá hrana kladný koeficient -- a teda ak ju prirátame k nejakému nezápornému vyjadreniu nejakého vektora, dostaneme kladné vyjadrenie onoho vektora.
Zverejnenie komentára