zadatci za 2.kolokvij

[jelena]

Imam par pitanja ovako:

1. pokažite da su prikazi svih alkohola CnH2n+1OH stabla?
kako se to treba pokazati?
2. Opišite algoritam koji konstruira hamiltonov ciklus koji je najviše 3/2 puta gori od optimalnog hamiltonovog ciklusa. koja je pretpostavka na težinsku fju pri tom potrebna? to je bilo prosle godine na popravnom,al mi nismo to radili na vjezbama, pa ak netko to moze napisati
hvala

_________________
jelena

[Luuka]

Ovo za h. ciklus imaš u predavanjima a i napisah već nešto o tome negdje na forumu, pogledaj...

a za 1. ovak:
Trebaš dokazat da je taj kem spoj stablo. Pa prebrojiš vrhove, ima ih n+2n+1+1=3n+2 i taj graf je povezan (ne bio bio spoj da nije).
Povezan graf s n vrhova je stablo akko ima n-1 bridova.

U ovom slučaju 3n+1 bridova.
Pa idemo brojat bridove (vj ima i pametniji način)

Svaki C je vezan bar sa dva H pa je to 2n bridova. Također, C-ovi su vezani i međusobno pa je to još n-1 brid. Prvi i zadnji C još daju dva brida jer je prvi vezan s još jednim H, a zadnji sa OH.
To zbrojimo i imamo:
2n+n-1+2=3n+1

I to je to.

btw alkoholi nemaju dvostrukih veza ni ičeg sličnog...Izgledaju CH3CH2CH2...CH2OH ili se taj OH mijenja s nekim od H u nekim slučajevima eventualno

_________________
"Bolje bi prolazio na faxu da sam na drogama nego na netu" - by a friend of mine
"Poslije spavanja doma spavanje bilo di mi je najdraža stvar" - by the same guy

[napraviculom]

kod dokazivanja da K_5 nije planaran (a i kod sl. zadataka) koristimo argument stupanj podrucja >= 3
iz cega to slijedi?

_________________
"I'm the operator with my pocket calculator"

[j.b.i.n.s.h.]

kod jednostavnog grafa ne možeš imati petlju ili dvostruki brid, a to su jedini načini da dobiješ područje stupnja 1 ili 2
područje s najmanjim mogućim stupnjem je trokutasto

_________________
...joined because i needed some help...

[napraviculom]

hvala. a kod petersenovog >=5 jer ... ?

_________________
"I'm the operator with my pocket calculator"

[mala]

.. jer najkraći ciklus ima duljinu 5 (što se vidi iz sličice )

[tajchi666]

Jel mi može netko ukratko napisati rješ. 4.zad s prošlogodišnjeg kolokvija (jedan od ona dva s blokovima)... zahvaljujem..

[Luuka]

[Luuka]

Jel zna netko kak bi išlo ono gore? Sutra rano je kolokvij...

Može čak i j.b.i.n.s.h. ...

_________________
"Bolje bi prolazio na faxu da sam na drogama nego na netu" - by a friend of mine
"Poslije spavanja doma spavanje bilo di mi je najdraža stvar" - by the same guy

[Fisher]

ja sam to skužija da ti je svejedno jel piše 12 u bloku ili 21, gledaš kao jedan objekt pa kardinalni broj od tog skupa brojiš kao (5+1)! = 6!.. najlogičnije mi je tako

_________________
.. sve bi seke ljubile mornare, ali mame, mame brane to ..

[Luuka]

Ok to za 1 objekt, al ako nam paše i 12 i 21 onda imamo 6! * 2! načina jer se ovi u bloku mogu permutirat...zato pitam.

_________________
"Bolje bi prolazio na faxu da sam na drogama nego na netu" - by a friend of mine
"Poslije spavanja doma spavanje bilo di mi je najdraža stvar" - by the same guy

[Fisher]

ma krivo sam se izrazija, ne ide mi baš ovo pisanje po forumu..

mislija sam reć 12 gledamo isključivo kao jedan objekt, tj ne množimo s 2! znači blok 12 je sam blok 12 i nikako ne može biti 21, tako mislim

_________________
.. sve bi seke ljubile mornare, ali mame, mame brane to ..

[Luuka]

Ok onda, tak sam i ja mislio... tnx... evo ti da budeš u pozitivi

_________________
"Bolje bi prolazio na faxu da sam na drogama nego na netu" - by a friend of mine
"Poslije spavanja doma spavanje bilo di mi je najdraža stvar" - by the same guy

[napraviculom]

jesul ti zadaci s blokovima FUI? kako naci presjek A_23 s A_34. moze netko malo pojasnit?

EDIT: bi to onda bilo 7! -3*6! + 3*5! - 4!

_________________
"I'm the operator with my pocket calculator"

[buzov5]

stavis da su (23) i (34) jedan element, pa takvih
permutacija ima 5! a racunas FUI, onu verziju s
komplementima, valjda, neznam. nisam ziher.
vise nis ne vjerujem.

_________________
tko je ikada naučio od poraza?

[napraviculom]

da, da, tak sam i ja shvatio

kofein se razgradio
ja se snom nagradio

_________________
"I'm the operator with my pocket calculator"

[Luuka]

[goc]

A1&A3 nije 4! nego 5! jer nemas ti blok 1234 nego razlicite blokove 12 i 34 koje gledas svaki ko jedan element... nie to slucaj kad imas A1&A2&A3 pa da imas blok 1234 koji gledas ko jedan element.
blah... ovo nespavanje ce me ubit jednog dana

[arya]

pa, slažem se da nije dobro ne spavati... recimo, meni je to skoro na svakom kolokviju do sada oduzelo vremena za cijeli zadatak naime, spora sam ak mi se spava... pa niš ne stignem
dakle, ljudi... spavajte

_________________
kalendar

[ß]