Prethodna tema :: Sljedeća tema |
Autor/ica |
Poruka |
krcko Forumaš nagrađen za životno djelo
Pridružen/a: 07. 10. 2002. (15:57:59) Postovi: (18B3)16
|
|
[Vrh] |
|
malte Gost
|
|
[Vrh] |
|
krcko Forumaš nagrađen za životno djelo
Pridružen/a: 07. 10. 2002. (15:57:59) Postovi: (18B3)16
|
Postano: 20:28 sri, 6. 11. 2002 Naslov: |
|
|
[quote="malte"]Reprezentirajmo gradove vrhovima grafa ciji su edgevi avionske linije za koje vrijedi uvjet zadatka. Prvo, lako je vidjeti da postoji barem 1 takav graf.[/quote]
OK, stima. Recimo potpun graf K_4 (cetiri grada, svaka dva spojena avionskom linijom).
[quote="malte"]Oznacimo sad s n broj vrhova proizvoljnog takvog grafa; tada bi trebalo vrijediti [code:1]broj_edgeva=3n/2.[/code:1][/quote]
Tako je, zato sto je graf 3-regularan (iz svakog grada vode tri avionske linije).
[quote="malte"]Zatim, treba za proizvoljno odabrana 2 vrha (a takvih je (n povrh 2)) prebrojati edgeve na putu medju njima (ima ih ili 1 ili 2). Uocimo potom da se niti jedan edge ne mo¸e prebrojati vi¨e od 5 puta (malo crtanja slicice), pa bi sljedeca relacija trebala biti zadovoljena:
[code:1](n povrh 2) < 3*5*n/2 < (n povrh 2) * 2[/code:1]
iz cega slijedi
[code:1]9 < n < 16[/code:1] pa bi trazeni n trebao biti 15.[/quote]
Ovdje mi nije bas jasno sto se broji. Put izmedju dva grada nije jedinstven. Na primjer, u drzavi K_4 iz grada A moze se letjeti direktno u B, ali moze se letjeti i preko C ili preko D (sa samo jednim presjedanjem). U vecim drzavama moglo bi se letjeti i na puno vise nacina, uz vise presjedanja. Uvjet zadatka kaze da duljina MINIMALNOG puta izmedju svaka dva vrha ne premasuje 2. To ne znaci da nema i duljih puteva.
U svakom slucaju, za proizvoljan takav graf ne mora vrijediti n>9. Protuprimjer je K_4. Gornja ograda n<16 vrijedi, ali moze se dobiti i bolja gornja ograda na jednostavniji nacin. Evo hint:
:!: Recimo da se nalazimo u jednom od gradova. Prebrojite u koliko drugih gradova mozemo doci uz najvise jedno presjedanje.
Nadam se da ce ovo pomoci :wink:
malte (napisa): | Reprezentirajmo gradove vrhovima grafa ciji su edgevi avionske linije za koje vrijedi uvjet zadatka. Prvo, lako je vidjeti da postoji barem 1 takav graf. |
OK, stima. Recimo potpun graf K_4 (cetiri grada, svaka dva spojena avionskom linijom).
malte (napisa): | Oznacimo sad s n broj vrhova proizvoljnog takvog grafa; tada bi trebalo vrijediti |
Tako je, zato sto je graf 3-regularan (iz svakog grada vode tri avionske linije).
malte (napisa): | Zatim, treba za proizvoljno odabrana 2 vrha (a takvih je (n povrh 2)) prebrojati edgeve na putu medju njima (ima ih ili 1 ili 2). Uocimo potom da se niti jedan edge ne mo¸e prebrojati vi¨e od 5 puta (malo crtanja slicice), pa bi sljedeca relacija trebala biti zadovoljena:
Kod: | (n povrh 2) < 3*5*n/2 < (n povrh 2) * 2 |
iz cega slijedi
pa bi trazeni n trebao biti 15. |
Ovdje mi nije bas jasno sto se broji. Put izmedju dva grada nije jedinstven. Na primjer, u drzavi K_4 iz grada A moze se letjeti direktno u B, ali moze se letjeti i preko C ili preko D (sa samo jednim presjedanjem). U vecim drzavama moglo bi se letjeti i na puno vise nacina, uz vise presjedanja. Uvjet zadatka kaze da duljina MINIMALNOG puta izmedju svaka dva vrha ne premasuje 2. To ne znaci da nema i duljih puteva.
U svakom slucaju, za proizvoljan takav graf ne mora vrijediti n>9. Protuprimjer je K_4. Gornja ograda n<16 vrijedi, ali moze se dobiti i bolja gornja ograda na jednostavniji nacin. Evo hint:
Recimo da se nalazimo u jednom od gradova. Prebrojite u koliko drugih gradova mozemo doci uz najvise jedno presjedanje.
Nadam se da ce ovo pomoci
_________________ Vedran Krcadinac
Ljudi su razliciti, a nula je paran broj.
|
|
[Vrh] |
|
C'Tebo Moderator
Pridružen/a: 03. 11. 2002. (18:40:48) Postovi: (26A)16
Lokacija: Zagreb
|
|
[Vrh] |
|
Gost
|
Postano: 22:40 sri, 6. 11. 2002 Naslov: |
|
|
[quote="krcko"][quote="malte"]Reprezentirajmo gradove vrhovima grafa ciji su edgevi avionske linije za koje vrijedi uvjet zadatka. Prvo, lako je vidjeti da postoji barem 1 takav graf.[/quote]
OK, stima. Recimo potpun graf K_4 (cetiri grada, svaka dva spojena avionskom linijom).[/quote]
Da, na taj sam i mislio.
[quote="malte"]Oznacimo sad s n broj vrhova proizvoljnog takvog grafa; tada bi trebalo vrijediti [code:1]broj_edgeva=3n/2.[/code:1][/quote]
[quote="krcko"]Tako je, zato sto je graf 3-regularan (iz svakog grada vode tri avionske linije).[/quote]
Good. Bar nesto smisleno rekoh. :roll:
[quote="krcko"]Ovdje mi nije bas jasno sto se broji.[/quote]
Nije vise ni meni. :shock: Sve sam ovo napisao u napadaju potpunog tupila, sto mi je postalo jasno tek nakon postanja. :(
[quote="krcko"]Put izmedju dva grada nije jedinstven. Na primjer, u drzavi K_4 iz grada A moze se letjeti direktno u B, ali moze se letjeti i preko C ili preko D (sa samo jednim presjedanjem). U vecim drzavama moglo bi se letjeti i na puno vise nacina, uz vise presjedanja. Uvjet zadatka kaze da duljina MINIMALNOG puta izmedju svaka dva vrha ne premasuje 2. To ne znaci da nema i duljih puteva. [/quote]
Da, to je jasno. Dobio sam onu gornju ocjenu gledajuci slucaj kad su svi putevi bez presjedanja. Donja je ocjena cista, katastrofalna glupost.
[quote="krcko"]U svakom slucaju, za proizvoljan takav graf ne mora vrijediti n>9. Protuprimjer je K_4.[/quote]
Svakako. But damage can not be undone :cry:
[quote="krcko"]Gornja ograda n<16 vrijedi, ali moze se dobiti i bolja gornja ograda na jednostavniji nacin. Evo hint:
:!: Recimo da se nalazimo u jednom od gradova. Prebrojite u koliko drugih gradova mozemo doci uz najvise jedno presjedanje.
Nadam se da ce ovo pomoci :wink:[/quote]
Hvala, potrudit cu se, ali nakon dugog dobrog sna. Mozda u medjuvremenu stovani vsego bude dao kakvu perlusinu 8)
krcko (napisa): | malte (napisa): | Reprezentirajmo gradove vrhovima grafa ciji su edgevi avionske linije za koje vrijedi uvjet zadatka. Prvo, lako je vidjeti da postoji barem 1 takav graf. |
OK, stima. Recimo potpun graf K_4 (cetiri grada, svaka dva spojena avionskom linijom). |
Da, na taj sam i mislio.
malte (napisa): | Oznacimo sad s n broj vrhova proizvoljnog takvog grafa; tada bi trebalo vrijediti |
krcko (napisa): | Tako je, zato sto je graf 3-regularan (iz svakog grada vode tri avionske linije). |
Good. Bar nesto smisleno rekoh.
krcko (napisa): | Ovdje mi nije bas jasno sto se broji. |
Nije vise ni meni. Sve sam ovo napisao u napadaju potpunog tupila, sto mi je postalo jasno tek nakon postanja.
krcko (napisa): | Put izmedju dva grada nije jedinstven. Na primjer, u drzavi K_4 iz grada A moze se letjeti direktno u B, ali moze se letjeti i preko C ili preko D (sa samo jednim presjedanjem). U vecim drzavama moglo bi se letjeti i na puno vise nacina, uz vise presjedanja. Uvjet zadatka kaze da duljina MINIMALNOG puta izmedju svaka dva vrha ne premasuje 2. To ne znaci da nema i duljih puteva. |
Da, to je jasno. Dobio sam onu gornju ocjenu gledajuci slucaj kad su svi putevi bez presjedanja. Donja je ocjena cista, katastrofalna glupost.
krcko (napisa): | U svakom slucaju, za proizvoljan takav graf ne mora vrijediti n>9. Protuprimjer je K_4. |
Svakako. But damage can not be undone
krcko (napisa): | Gornja ograda n<16 vrijedi, ali moze se dobiti i bolja gornja ograda na jednostavniji nacin. Evo hint:
Recimo da se nalazimo u jednom od gradova. Prebrojite u koliko drugih gradova mozemo doci uz najvise jedno presjedanje.
Nadam se da ce ovo pomoci |
Hvala, potrudit cu se, ali nakon dugog dobrog sna. Mozda u medjuvremenu stovani vsego bude dao kakvu perlusinu
|
|
[Vrh] |
|
krcko Forumaš nagrađen za životno djelo
Pridružen/a: 07. 10. 2002. (15:57:59) Postovi: (18B3)16
|
Postano: 23:55 sri, 6. 11. 2002 Naslov: |
|
|
[quote="malte (?)"]Nije vise ni meni. :shock: Sve sam ovo napisao u napadaju potpunog tupila, sto mi je postalo jasno tek nakon postanja. :( [/quote]
No dobro, ne moras se stalno posipati pepelom. Ja sam ti zahvalan sto si zapoceo diskusiju. Prije tebe zadatak tjedan dana nitko nije htio ni stapom pipnut.
[quote="malte"][quote="krcko"]U svakom slucaju, za proizvoljan takav graf ne mora vrijediti n>9. Protuprimjer je K_4.[/quote]
Svakako. But damage can not be undone :cry: [/quote]
Pa mozes pitati vsegu da obrise post.. on je ovdje zakon :D
[quote="malte"]Hvala, potrudit cu se, ali nakon dugog dobrog sna. Mozda u medjuvremenu stovani vsego bude dao kakvu perlusinu 8)[/quote]
"Perlusina" = velika skripta u perl-u? :lol:
Hint je vec iskoristio C'Tebo. Ono bozicno drvce je stvarno dokaz da ne moze biti vise od 10 gradova. Sad jos treba dokazati da ih moze biti 10. Treba pospajati listove C'Tebinog stabla tako da budu ispunjeni uvjeti zadatka.
Ali pls odgovor ne u ASCII artu ovaj puta.. :?: Vsego, jel se mogu ubacivat slike u postove?
malte (?) (napisa): | Nije vise ni meni. Sve sam ovo napisao u napadaju potpunog tupila, sto mi je postalo jasno tek nakon postanja. |
No dobro, ne moras se stalno posipati pepelom. Ja sam ti zahvalan sto si zapoceo diskusiju. Prije tebe zadatak tjedan dana nitko nije htio ni stapom pipnut.
malte (napisa): | krcko (napisa): | U svakom slucaju, za proizvoljan takav graf ne mora vrijediti n>9. Protuprimjer je K_4. |
Svakako. But damage can not be undone |
Pa mozes pitati vsegu da obrise post.. on je ovdje zakon
malte (napisa): | Hvala, potrudit cu se, ali nakon dugog dobrog sna. Mozda u medjuvremenu stovani vsego bude dao kakvu perlusinu |
"Perlusina" = velika skripta u perl-u?
Hint je vec iskoristio C'Tebo. Ono bozicno drvce je stvarno dokaz da ne moze biti vise od 10 gradova. Sad jos treba dokazati da ih moze biti 10. Treba pospajati listove C'Tebinog stabla tako da budu ispunjeni uvjeti zadatka.
Ali pls odgovor ne u ASCII artu ovaj puta.. Vsego, jel se mogu ubacivat slike u postove?
_________________ Vedran Krcadinac
Ljudi su razliciti, a nula je paran broj.
|
|
[Vrh] |
|
vsego Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09) Postovi: (355F)16
Spol:
Lokacija: /sbin/init
|
Postano: 2:06 čet, 7. 11. 2002 Naslov: |
|
|
[quote="krcko"][quote="malte"][quote="krcko"]U svakom slucaju, za proizvoljan takav graf ne mora vrijediti n>9. Protuprimjer je K_4.[/quote]
Svakako. But damage can not be undone :cry: [/quote]
Pa mozes pitati vsegu da obrise post.. on je ovdje zakon :D [/quote]
Zar nemaju svi useri pravo brisanja/editiranja vlastitih postova? (ne znam, nisam probao) Ipak, neka post bude gore. Nema nikakve "sramote" jer smo svi anonimni (mada su neki samo "anonimni" :)), a replyi bi gubili na smislu da se nesto ide mijenjati.
[quote="krcko"][quote="malte"]Hvala, potrudit cu se, ali nakon dugog dobrog sna. Mozda u medjuvremenu stovani vsego bude dao kakvu perlusinu 8)[/quote]
"Perlusina" = velika skripta u perl-u? :lol:
[/quote]
Kad se vec trazi... :D
[code:1]!/usr/bin/env perl
print "10\n";
[/code:1]
[quote="krcko"]Ali pls odgovor ne u ASCII artu ovaj puta.. :?: Vsego, jel se mogu ubacivat slike u postove?[/quote]
Ne bas direktno. No, i studenti i asistenti imaju accounte na studentu. Tamo se slika uploada u public_html, pa se onda polinka preko "img"-a (predzadnji gumbic tu di se pisu poruke).
[img]http://student.math.hr/~vsego/phun/image003.gif[/img]
Ako neki student nema account, moze ga otvoriti u Racunskom centru (pise na vratima koji su termini).
krcko (napisa): | malte (napisa): | krcko (napisa): | U svakom slucaju, za proizvoljan takav graf ne mora vrijediti n>9. Protuprimjer je K_4. |
Svakako. But damage can not be undone |
Pa mozes pitati vsegu da obrise post.. on je ovdje zakon |
Zar nemaju svi useri pravo brisanja/editiranja vlastitih postova? (ne znam, nisam probao) Ipak, neka post bude gore. Nema nikakve "sramote" jer smo svi anonimni (mada su neki samo "anonimni" ), a replyi bi gubili na smislu da se nesto ide mijenjati.
krcko (napisa): | malte (napisa): | Hvala, potrudit cu se, ali nakon dugog dobrog sna. Mozda u medjuvremenu stovani vsego bude dao kakvu perlusinu |
"Perlusina" = velika skripta u perl-u?
|
Kad se vec trazi...
Kod: | !/usr/bin/env perl
print "10\n";
|
krcko (napisa): | Ali pls odgovor ne u ASCII artu ovaj puta.. Vsego, jel se mogu ubacivat slike u postove? |
Ne bas direktno. No, i studenti i asistenti imaju accounte na studentu. Tamo se slika uploada u public_html, pa se onda polinka preko "img"-a (predzadnji gumbic tu di se pisu poruke).
Ako neki student nema account, moze ga otvoriti u Racunskom centru (pise na vratima koji su termini).
_________________ U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju.
|
|
[Vrh] |
|
krcko Forumaš nagrađen za životno djelo
Pridružen/a: 07. 10. 2002. (15:57:59) Postovi: (18B3)16
|
|
[Vrh] |
|
C'Tebo Moderator
Pridružen/a: 03. 11. 2002. (18:40:48) Postovi: (26A)16
Lokacija: Zagreb
|
Postano: 1:40 sub, 9. 11. 2002 Naslov: |
|
|
Sjetio sam se kako bi mogli povezat (dok sam išo na šah)
Na onom mom "božićnom drvcu" :) su s o označeni gradovi, precrtajte tu sliku i umjesto onog skroz lijevog o-a metnite K, umjesto ona tri koja idu iz njega označimo s g1, g2, g3, a one zadnje označimo s 1,2,3,4,5,6 (u nedostatku ideja)
Dakle iz K izlaze g1,g2,g3, iz g1 izlaze 1,2; iz g2 izlaze 3,4 i iz g3 izlaze 5,6.
Sad povežemo
1 s 3 i 5.
2 s 4 i 6
3 s 5
4 sa 6
Sad iz K možemo doć bilo di s maks 1 presjedanjem (očito)
Iz g1 možemo doć u g2 i g3 s maksimalno jednim presjedanjem (preko K)
Ako oćemo iz g1 doć u 3(ili 5) idemo putem g1->1->3(ili 5), ako oćemo u 4, idemo g1->2->4(ili 6).
I tako dalje i tako bliže, uglavnom to je to :)
Sjetio sam se kako bi mogli povezat (dok sam išo na šah)
Na onom mom "božićnom drvcu" su s o označeni gradovi, precrtajte tu sliku i umjesto onog skroz lijevog o-a metnite K, umjesto ona tri koja idu iz njega označimo s g1, g2, g3, a one zadnje označimo s 1,2,3,4,5,6 (u nedostatku ideja)
Dakle iz K izlaze g1,g2,g3, iz g1 izlaze 1,2; iz g2 izlaze 3,4 i iz g3 izlaze 5,6.
Sad povežemo
1 s 3 i 5.
2 s 4 i 6
3 s 5
4 sa 6
Sad iz K možemo doć bilo di s maks 1 presjedanjem (očito)
Iz g1 možemo doć u g2 i g3 s maksimalno jednim presjedanjem (preko K)
Ako oćemo iz g1 doć u 3(ili 5) idemo putem g1->1->3(ili 5), ako oćemo u 4, idemo g1->2->4(ili 6).
I tako dalje i tako bliže, uglavnom to je to
|
|
[Vrh] |
|
krcko Forumaš nagrađen za životno djelo
Pridružen/a: 07. 10. 2002. (15:57:59) Postovi: (18B3)16
|
|
[Vrh] |
|
|