Osaisiko joku täällä antaa ratkaisut alla oleviin tehtäviin:
1. Kun määritellään verkko G asettamalla
Pg=P[4](={A:A c {1,2,3,4}) ja Vg={AB(päällä viiva):A,B kuuluu P[4] ja I(A\B)U(B\A)I=1,
niin kuinka monta viivaa on G:ssä?
2. Mikä on Petersenin verkon riippumattomuusluku?
http://users.jyu.fi/~jorma/graphs/vk12.htm
1. Kun määritellään verkko G asettamalla
Pg=P[4](={A:A c {1,2,3,4}) ja Vg={AB(päällä viiva):A,B kuuluu P[4] ja I(A\B)U(B\A)I=1,
niin kuinka monta viivaa on G:ssä?
2. Mikä on Petersenin verkon riippumattomuusluku?
http://users.jyu.fi/~jorma/graphs/vk12.htm
Vastaukset 11
Vanhimmat
Osaisin molemmat. Toivottavasti tämä tieto hyödytti.
Nyt voitkin yrittää ratkaista tehtävät itse.
... voin antaa:
1. Mitä intuitiivista asiaa G edustaa?
Helpottaa ehkä, jos piirrät pienemmät tapaukset {1,2} ja {1,2,3} ensin. Kokeile piirtää ne 'tasoittain'. Miten monta viivaa on eri tasojen välillä? Onko kuvissa symmetriaa?
2. Vastaus on helposti hahmotettavissa, jos mietit pisteitä pienemmissä osissa.
Voit saada lisävinkkejä, jos ensin laitat esille oman yrityksesi.
Tehtävät olivat tentissäni, enkä niitä silloinkaan osannut.
Ensimmäisessä en ymmärrä merkintöjä ja toisessa sain väärän vastauksen 5, kun taidan senkin ymmärtää väärin.
... tässä ovat vastaukset. Muuten, jos käväiset pääkaupungissa, tässä olisi sellaista materiaalia, jossa olisin aivan erityisen hyvä antamaan yksityistunteja. ;)
1) P(G) tietysti tarkoittaa G:n pisteiden joukkoa.
V(G) tarkoittaa G:n viivojen joukkoa.
(Englanniksi nämä ovat yleensä V(G) (vertices) ja E(G) (edges) .)
Kirjoitamme [n] = {1,2,3,...,n}
Merkintä P[n] tarkoittaa sitä joukkoa, joka sisältää kaikki joukon [n] osajoukot.
Lauseessa |(A\B)U(B\A)| = 1, käytetään joukkojen erotusta sekä unionia tavalla, joka antaa A:n ja B:n 'symmetrisen erotuksen'. Voit Venn-diagrammilla (tai pienellä mielikuvituksella) todeta, että vasemmanpuoleinen joukko (A\B)U(B\A) sisältää ne alkiot, jotka kuuluvat täsmälleen yhteen joukoista A ja B.
Usein kirjoitustapa on A 'Delta' B = (A\B)U(B\A), missä Delta on kolmion näköinen kirjain.
Jos |(A\B)U(B\A)| = 1, silloin A ja B ovat tietenkin samanlaisia, paitsi että yhdessä on yksi alkio enemmän kuin toisessa. (Piirrä jälleen Venn-diagrammi, jos ei aukea.)
Voit piirtämällä todentaa seuraavan: 'n-ulotteinen kuutio' voidaan piirtää graafina, jossa jokaista joukon [n] osajoukkoa vastaa yksi piste. Kuution sivuiksi tulee sellaiset viivat, joita vastaavien osajoukkojen koot eroavat tasan yhdellä. (Tälläinen verkko vastaa logiikan käsitettä 'Hasse-diagrammi'.)
Sinulla on nyt pari vaihtoehtoa: Voit joko yrittää yleisemmin todistaa n-ulotteisen kuutioiden sivujen määrän. Ks. vaikka 'hyperkuutio'-osuutta Wikipediasta.
Helpompi tapa tapaukselle n=4 on yksinkertaisesti miettiä G:tä tasoittain: Kuvitellaan (tai piirretään) pohjimmaiseksi piste joka edustaa tyhjää joukkoa, sitten sen yläpuolelle kaikki 1-alkioiset osajoukot ja näiden yläpuolelle 2-alkioiset... jne.
Huomaa, että k-alkioisten osajoukkojen taso on kooltaan 4Ck = 4C(4-k), jolloin 2-alkioisten taso on suurin, ja kuva on symmetrinen sen tason suhteen.
Viivoja on vain peräkkäisten tasojen välillä:
0. ja 1. tasojen välillä on tietysti 4 viivaa, sillä tyhjään joukkoon voi lisätä yhden alkion neljällä tavalla.
1. ja 2. tasojen välillä on tietysti 12 viivaa, sillä 1. tasolla on 4 eri joukkoa, joihin voi kuhunkin lisätä yhden alkion kolmella eri tavalla.
2. ja 3. tasojen välillä on 12 viivaa symmetrisesti. (Mieti asiaa vaikkapa komplementtijoukkojen suhteen.)
3. ja 4. tasojen välillä on myös 4 viivaa symmetrisesti.
Siispä 4-ulotteisessa kuutiossa on 32 sivua.
2) Riippumaton joukko on sellainen pisteiden joukko, että joka ei sisällä lainkaan viivoja.
Riippumattomuusluku on suurimman riippumattoman joukon koko.
Mietit varmaankin asiaa ottamalla pisteitä pareittain - luku on enintään viisi, sillä kustakin 'sakara'-parista voidaan valita korkeintaan yksi piste riippumattomaan joukkoon.
Valitettavasti ei kuitenkaan ole mahdollista valita yhtä pistettä jokaisesta parista siten, että näiden viiden pisteen välillä ei olisi viivoja.
Petersenin verkkoa voi ajatella toisin: Siinä on kaksi C_5:sta, (elikä 5-sykliä), yksi sisäpuolella ja yksi ulkopuolella. On helppoa oivaltaa, että riippumaton joukko voi sisältää korkeintaan kaksi pistettä kustakin C_5:stä. (Huomaa, että jos valitset yli kaksi pistettä 5-syklistä, ainakin kaksi niistä on peräkkäin.)
Riippumattomuusluku on siten korkeintaan 4. Nyt riittää, että onnistut valitsemaan kaksi pistettä kustakin syklistä, niin että niiden välillä ei ole viivoja. Tämä on todella helppoa.
Siispä riippumattomuusluku on 4.
Kun sanoin
'osajoukkojen koot eroavat tasan yhdellä',
tarkoitin tietysti että
'joukot sisältävät samat alkiot, paitsi että toisessa on yksi alkio enemmän'
Kiitos, nyt meni jakeluun. Tehtävät ovat helppoja, kun näkee ratkaisut;) Tentti meni jo, joten yksityistunneille ei ole tarvetta.
Jos sinulla riittää intoa, niin vielä oli tehtävä, jossa piti osoittaa, että 5. pisteen täydellisessä verkossa K5 ei ole kahta keskenään erillistä neliötä.
... ymmärrä mitä tarkoitat 'erillisellä neliöllä'. Voitko selittää tehtävää tarkemmin?
Ymmärtäisin, että 4-rengasta...
... mutta mun päässä kaksi erillistä 4-rengasta vie yhteensä 8 pistettä. En oikein ymmärrä kysymystä niiden mahtumisesta K_5:een. Luultavasti väärinkäsitys jomman kumman osalta.
... on ns. 'edge-disjoint' C_4, elikä viivoiltaan erillisten neliöiden olemassaolo, riittää kun huomaat, että mitkä tahansa kaksi neliötä menevät päällekkäin ainakin kolmessa pisteessä. Mutta jos valitset kolme pistettä neliöstä, ne muodostavat polun siinä neliössä. Joten päällekkäisyyttä syntyy ainakin kahden viivan verran.
Kiitoksia avusta. Tässä vielä kokonainen ratkaisu.
Väite: K5:ssä ei ole kahta erillistä neliötä.
Todistus. Oletetaan vastoin väitettä, että W ja W' ovat erillisiä neliöitä.
Olkoot A ja A' vastaavat pistejoukot. Koska 5 => |AUA'| = |A| |A'|−|A\A'| = 2·4−|A\A'|, niin |A\A'|=> 8−5 = 3. Olkoot a, b ja c leikkauksen A\A' kolme pistettä. Rengas W sisältää kaksi näiden välisistä viivoista. Samoin W'\{ab, ac, bc} = 2. Koska W'\{ab, ac, bc} ja W'\{ab, ac, bc} ovat molemmat joukon {ab, ac, bc} kaksialkioisia osajoukkoja, ne eivät voi olla erillisiä, mikä on ristiriita.