proslogod. kolokvij (zadatak)

[malena]

pozz svima!
zapela sam na ova dva zadatka, pa ako imate vremena i volje:

4. Pokazite da u svakom jednostavnom planarnom grafu postoji vrh ciji stupanj je manji od 6.
moze ideja kako rijesiti?

5. Izvedite rekurziju za broj permutacija n-cl. skupa sa svojstvom da su svi pripadni ciklusi duljine 1 i 2.
jedino sto znam o ovom zadatku je sto je ciklus duljine 2
help!

_________________

[Milojko]

za ovaj peti pogledaj u skripti involucije, malo tam baci oko.

a vaj prvi, khm.... neam pojma
probaj nešto s brojem bridova, vrhova, tako nešto.

_________________
Sedam je prost broj

Bolonja je smeće i to pod hitno treba mijenjat

[Mrs. Bean]

ovaj 4. sam ja ovako:

pretp suprotno, tj da su svi vrhovi stupnja >=6 i da graf ima n vrhova.
suma d(v)(stupnjeva vrhova) je >=6n, a kako je suma vrhova jednaka 2*|E|(broj bridova) tada je 2*|E|>=6n, tj |E|>=3n što je u kondtradikciji s činjenicom(dokazano na vjezbama) da jednostavan planaran graf s n vrhova moze unati najvise 3n-6 bridova.

evo nisam sigurna pa neka netko potvrdi ako je dobro ili ispravi ako nije.

[(s)Venn]

Dijelim isto mišljenje s gospodičnom Bean, i meni je tako ispalo.


Neka me netko ispravi ako griješim, ali čini mi se da na vježbama nismo radili zadatke tipa 5. iz prošlogodišnjeg kolokvija. Je li se možda netko raspitao hoće li biti zadataka s rekurzijama na ovome kolokviju?

_________________
..pišem pjesme, sviram bluz, radost i tugu na stihove lomim..

[maloka]

ne znam jel ja krivo gledam nešto, ali 5. zad prošlogodišnjeg kolokvija (dakle 2009.) glasi : Izvedite rekurziju za broj permutacija n-skupa sa svojstvom da su svi pripadni ciklusi duljine 1 ili 2. To je definicija involucija i ima u skripti prof. Nakića na 38.str , primjer 2.3.4. izvedena ta rekurzija.

[Gino]

[ddduuu]

Odredite na koliko na·cina mo·zemo odabrati uredenu ·cetvorku nenegativnih cijelih bro-
jeva manjih od 7 takvih da je njihov zbroj 17.

jel neko zna???

[malena]