Next: Tästä dokumentista ...
Up: harj8
Previous: harj8
- Olkoon vähintään 3-solmuinen yhtenäinen tasoverkko,
jonka kaikki syklit ovat vähintään neljän pituisia
(so. verkko ei sisällä -muotoista indusoitua aliverkkoa
eli on kolmioton).
Osoita, että :n kaarien määrää rajoittaa tällöin epäyhtälö
. (Kuten luennolla esitettiin,
ilman kolmiottomuusoletusta saadaan heikompi
epäyhtälö
.)
- Osoita edellisen tuloksen nojalla, että verkko
ei ole planaarinen, ja että edellisissä harjoituksissa
tarkastellut hyperkuutioverkot ovat planaarisia,
jos ja vain jos .
- Mikä on harjoituksissa 6 tarkastellun ns. Petersenin
verkon väriluku?
- Montako väriä enintään tarvitaan avaruuden konveksin monitahokkaan
(esim. kuution, pyramidin, ikosaedrin tms.) sivutahkojen värittämiseen
niin, ettei millekään kahdelle vierekkäiselle (= yhteisen särmän
erottamalle) tahkolle tule samaa väriä?
- Eräs yliopisto järjestää samalla lukukaudella kurssit TTP, JDM,
ALTE, APK, DL ja MIT. Kursseilla TTP ja APK on yhteisiä opiskelijoita,
samoin kuin kursseilla APK/JDM, JDM/DL, DL/ALTE ja ALTE/MIT.
Montako koepäivää tarvitaan kurssien kokeisiin, jotta kellekään
opiskelijalle ei tule päällekkäisiä kokeita?
- Pieni hiiri haluaa syödä kuutionmuotoisen juuston. Ollen järjestelmällinen eläin, hiiri jakaa mielessään juuston 333
alikuutioon ja päättää edetä niin, että aloittaa syömisen yhdestä nurkasta,
syö kokonaisen alikuution kerralla, etenee siitä johonkin naapurikuutioon,
ja syö viimeisenä juuston ytimessä olevan keskikuution.
Onnistuuko hiiren suunnitelma?
- Verkko G on -säännöllinen, jos sen jokaisen solmun asteluku on
tasan . Osoita, että jokaisessa -säännöllisessä kaksijakoisessa
verkossa voidaan muodostaa täydellinen pariutus.
- Kaikkien 15 EU-maan pääministerit saapuvat Jyväskylään huippukokoukseen
tapaamaan 15:ta Jyvässeudun merkittävää kunnallista vaikuttajaa. Kukin
pääministeri saa nimetä kolme vaikuttajaa, joiden kanssa hän
haluaisi neuvotella. Osoita, että mikäli kenellekään
jyvässeutulaiselle ei tule enempää kuin kolme neuvottelupyyntöä
(tällöin itse asiassa jokaiselle tulee tasan kolme),
kaikki toivotut tapaamiset voidaan järjestää kolmessa peräkkäisessä
vaiheessa, joissa kussakin käydään 15 pareittaista neuvottelua
EU:n ja Jyvässeudun edustajien kesken.
- Olkoon
kokoelma jonkin äärellisen
perusjoukon osajoukkoja. Perheen edustajisto
on -alkioinen joukko , joka sisältää täsmälleen
yhden alkion kustakin joukosta , .
(Huomaa siis, että vaikka joukot eivät välttämättä ole erillisiä,
niin sama alkio ei voi edustaa useampaa joukkoa.)
Osoita, että perheestä
voidaan valita edustajisto, jos ja vain jos kaikilla
on minkä tahansa :n -joukon yhdisteessä
vähintään alkiota, so.
kaikilla
, missä , kun .
(Vihje: Pariutus.)
Next: Tästä dokumentista ...
Up: harj8
Previous: harj8
Pekka Orponen
2000-11-09