Foorumi on nykyään lähes kokonaan omistettu kotitehtävä-kyselyille yms. , joten ajattelin aloittaa jotakin varsinaista keskustelua minua kiinnostavasta matikasta.
Graafi (tai verkko) koostuu solmuista (eli pisteistä) sekä niitä yhdistävistä kaarista (eli viivoista). Solmujoukkoa merkitään V ja kaarijoukkoa E (englanninkielisistä snaoista vertices and edges).
Oletamme, että jokainen kaari yhdistää kaksi eri solmua, ja että kutakin solmuparia kohden on korkeintaan yksi kaari.
Jos graafin jokaiselle kaarelle annetaan ainutlaatuinen suunta, saamme 'orientoidun graafin'. Eli se on intuitiivisesti 'nuolien verkko'.
Olkoon G orientoitu graafi. Määrittelemme solmun v 'ulkoympäristöksi' niiden solmujen joukon, joihin on v:stä ulospäin suuntautuva nuoli.
Määrittelemme solmun v 'toiseksi ulkoympäristöksi' niiden solmujen joukon, jotka ovat etäisyydellä kaksi ulospäin v:stä.
Näiden joukkojen kokoja nimitämme v:n 'ulkoasteeksi' sekä 'toiseksi ulkoasteeksi'.
Seymourin Konjektuura: Olkoon G orientoitu graafi. Tällöin G sisältää solmun, jonka ulkoaste on korkeintaan niin suuri kuin toinen ulkoaste.
Tähän ratkaisemattomaan ongelmaan on joitakin osittaisia todistuksia. Ks. vaikka lähteitä tällä sivulla ja etsi niitä netistä: http://www.math.uiuc.edu/~west/openp/2ndnbhd.html
Säännöllisin väliajoin joku koulupoika on 'löytänyt ratkaisun' ja saa ison summan rahaa. :) Todellisuudessa näissä ratkaisuissa on virheitä, vaikka asiaa ei koskaan korjata julkisesti.
Miten ongelman voisi ratkaista? (Ei riitä, että sanoo 'algoritmisesti', sillä tällöin algoritmin löytäminen on se juju.)
Jonkun PhD-tutkielmassa osoitettiin (lineaarioptimoinnista tuttua duaaliongelmaa hyödyntäen), että konjektuura on yhtäpitävä tämän kanssa:
Muunnos: On olemassa tapa painottaa solmuja reaaliluvuilla siten, että Jokainen solmu täyttää aiemman ehdon.
Graafi (tai verkko) koostuu solmuista (eli pisteistä) sekä niitä yhdistävistä kaarista (eli viivoista). Solmujoukkoa merkitään V ja kaarijoukkoa E (englanninkielisistä snaoista vertices and edges).
Oletamme, että jokainen kaari yhdistää kaksi eri solmua, ja että kutakin solmuparia kohden on korkeintaan yksi kaari.
Jos graafin jokaiselle kaarelle annetaan ainutlaatuinen suunta, saamme 'orientoidun graafin'. Eli se on intuitiivisesti 'nuolien verkko'.
Olkoon G orientoitu graafi. Määrittelemme solmun v 'ulkoympäristöksi' niiden solmujen joukon, joihin on v:stä ulospäin suuntautuva nuoli.
Määrittelemme solmun v 'toiseksi ulkoympäristöksi' niiden solmujen joukon, jotka ovat etäisyydellä kaksi ulospäin v:stä.
Näiden joukkojen kokoja nimitämme v:n 'ulkoasteeksi' sekä 'toiseksi ulkoasteeksi'.
Seymourin Konjektuura: Olkoon G orientoitu graafi. Tällöin G sisältää solmun, jonka ulkoaste on korkeintaan niin suuri kuin toinen ulkoaste.
Tähän ratkaisemattomaan ongelmaan on joitakin osittaisia todistuksia. Ks. vaikka lähteitä tällä sivulla ja etsi niitä netistä: http://www.math.uiuc.edu/~west/openp/2ndnbhd.html
Säännöllisin väliajoin joku koulupoika on 'löytänyt ratkaisun' ja saa ison summan rahaa. :) Todellisuudessa näissä ratkaisuissa on virheitä, vaikka asiaa ei koskaan korjata julkisesti.
Miten ongelman voisi ratkaista? (Ei riitä, että sanoo 'algoritmisesti', sillä tällöin algoritmin löytäminen on se juju.)
Jonkun PhD-tutkielmassa osoitettiin (lineaarioptimoinnista tuttua duaaliongelmaa hyödyntäen), että konjektuura on yhtäpitävä tämän kanssa:
Muunnos: On olemassa tapa painottaa solmuja reaaliluvuilla siten, että Jokainen solmu täyttää aiemman ehdon.
Vastaukset 6
Vanhimmat
Pitäisikö tässä käyttää paljon mainostamaasi päättelyä?
Kysymyksessä esität solmun olevan piste eli nollaulotteinen matemaattinen objekti.
Kaari on graafissa viiva nollasta toiseen nollaan, jos graafi (G) on kytketty on solmun (v)-(v1) välinen viiva "1. ulkoympäristö" kun taas solmujen (v1)-(v2)välinen viiva 2.ulkoympäristö. Tämä jatkuu samalla tavoin solmujen (vn)-(v n 1) välinen viiva on n:s ulkoympäristö.
Ns. kauppamatkustajan ongelma perustuu juuri tämän kaltaiseen matematiikkaan, ja kun kertolaskussa nollan ollessa kertojana on aina tulos nolla.
Siispä kysymyksesi asettelussa ilmenee nulliteetti ja ongelmaa ei kyetä ratkaisemaan polynomisella formulalla.
Hauskaa syksyä!
... tajuta viestiäni. 'Ympäristöllä' tarkoitin solmujen joukkoa, en viivaa.
Ongelma on todellinen kysymys matemaattisessa tutkimuksessa.
todistais vaikka tälleen:
http://www.cst.cmich.edu/users/smith1kw/REU2002/SeymoursNbhdConj.pdf
tai sit kysyis tältä klopilta:
http://presskit.ditd.org/2005_Davidson_Fellows_Press_Kit/2005_DF_Brett_Harrison.pdf
vai onx nää just niitä koulupoikia jotka duunaa vääriä todistuksia ?
Sinänsä en edes kopittanut koko juttua. Siis jos meillä on solmu josta lähtee kaksi nuolta joista toisesta vielä yksi niin silloinhan ainoa solmu jolla ylipäätään on 2. ulkis on alkuperäinen solmu ja sen 2. ulkis on 1 ja 1. ulkis on 2. Jos taas hyväksytään tilanne, että kaikilla jopa reunasolmuilla (lehdillä) on ulkikset mutta ne on vaan nolla niin hommahan on triviaali koska graafissa jossa ei ole luuppeja on aina lehtiä ja lehdelle on aina 1. ulkis = 0 ja 2. ulkis = 0. No joo. Varmaan meni multa vaan kokonaan ohi.
Vakavampaa kuitenkin on että teoreemojen hyväksyntäprosessi on matikassa ilmeisesti vähän epämääräinen. Epämääräinen joukko ihmisiä jättää lukematta todistuksen kovinkaan tarkkaan ja teoreema saattaa hyvinkin saada lainvoiman ainakin vähäksi aikaa. Koskakohan ilmestyy suunnattuja graafeja koskeva kirja jossa esitetään vaikkapa Brett Harrisonin todistus. En kuitenkaan väitä, että todistuksessa olisi mitään vikaa kun en edes tunne asiaa.
Kivaa, että joku oli aidosti kiinnostunut asiasta!
Ensimmäisen linkin takana olevan 'todistuksen' olen lukenut, ja siinä on helppo virhe: nimittäin Lemma 2 ei ole totta. Siinä oletetaan, että ns. j-sun:it ovat 'lasten aurinkoja', eli auringon säteet eivät mene ristiin. Oletus on tietenkin väärä.
Toki tuossa todistetaan, että voimme rajoittaa niihin graafeihin, jotka sisältävät suunnatun syklin.
Brettin 'todistusta' en ole nähnyt, mutta kysyin Seymourilta itseltään asiaa, ja hän kertoi sen olleen virheellinen. Tämä oli se koulupoika, johon viittasin.
On totta, että jos löytyy solmu, jolla ei ole ulospäin suunnattuja nuolia, se on triviaalisti sopiva 'Seymour solmuksi'.
On helppo todistaa teoreema, jos minimi-ulkoaste on 3 tai vähemmän. Itse asiassa se on todistettu kaikille graafeille, joilla on minimi-ulkoaste 6 tai vähemmän.
Joten voimme rajoittaa mielenkiintomme niihin graafeihin, joiden minimi-ulkoaste 6 tai vähemmän, ja joissa on suunnattu sykli. Ei valitettavasti vie kovinkaan pitkälle.
On mielestäni vastuutonta, ettei virheellisiä todistuksia ole korjattu/poistettu, mutta 'shit happens'. :)
Tässä on onnistuneempi koulupoikatodistus, jossa on rajoitettu graafeihin, jotka ovat säännöllisen asteisia, ja joissa on yksi solmu, jonka eka ja toka ulkis ovat säännöllisen asteisia: http://web.mit.edu/rsi/www/pdfs/papers/2002/2002-mackey.pdf
Rajoitukset ovat toisaalta valitettavan suuria.
Piti sanoa 'voimme rajoittaa mielenkiintomme niihin graafeihin, joiden minimi-ulkoaste 6 tai enemmän'
Kirjoitin vahingossa 'vähemmän'.
Tarkoitin tietysti, '7 tai enemmän' . :)