skripta (objasnjenje gradiva)

[krcko]

Lepi, odgovor dobijes sutra u 12 sati

Bit ce sve u redu ako kuzis algoritme

_________________
Vedran Krcadinac

Ljudi su razliciti, a nula je paran broj.

[Lepi91]

ma kuzim ja kaj rade algoritmi,al pitam cisto zbog toga ako cu ih morat strebat napamet da napisem algoritam...ako ja vidim njega napisanog ispred sebe normalno da mi je jasno sta rade...al ajde nekak mi se nakraju cini da radim zbrku oko nicega...

_________________
tko rano rani,malo spava

[pupi]

Imam pitanje u vezi koda za konstruiranje razapinjućeg stabla, na stranici 67 u skripti http://web.math.pmf.unizg.hr/nastava/komb/predavanja/predavanja.pdf

Tj. trebala bi mi potvrda jesam li ja to dobro shvatila

Od nekog povezanog grafa "uzmemo" samo njegove vrhove (svaki vrh ce onda biti jedna komponenta) i dalje nalazimo bridove po prvoj uputi iz algoritma dok svi vrhovi ne budu povezani ?

[krcko]

Da, to je algoritam na str. 67. Dualni algoritam bi radio ovako: dokle god ima ciklusa, pocupaj jedan brid iz ciklusa.

_________________
Vedran Krcadinac

Ljudi su razliciti, a nula je paran broj.

[pupi]

Vuu, hvala

[PermutiranoPrase]

Nisu mi jasni skupovi [tex]A_I[/tex] u tm.2.6.2. Koliko shvatih, I je podskup skupa {1,...,n}, npr. neka mi je I={1,2,5}. Što je onda [tex]A_I[/tex]? U kakvoj vezi su oni s familijom [tex]A_1,...,A_n[/tex]?
I zašto je zadnja suma u dokazu jednaka 0?

_________________
With great power comes great electricity bill.
n!!!!
Theorem 2: Alexander the Great did not exist and he had an infinite number of limbs.

[shakespeare]

Meni nije jasno u zad. 8.14. iz vježbi- dokaži da jednostavan, povezan, planaran graf s n vrhova ima najviše 3n-6 bridova- kako znamo da vrijedi d(f) >= 3 ?

Zad. 7.2 - zašto alfa1 i alfa2 kod broja (i općenito) mogu biti i 61, a ne do 60 uključivo?

Zad. 7.7 - kako dobijemo zadnji član sume i zar nije greška u skripti kod trećeg pribonika - zar ne treba biti 3+2 povrh 3 umjesto 2?

Hvala unaprijed bilo kome.

[Loo]

[tex]A_I=\displaystyle\cap _{i\in I} A_i[/tex], a [tex]I\subseteq \{1,2,...,n\}[/tex], pri čemu za [tex]I=\emptyset, A_I=X[/tex]
suma je 0 po binomnom teoremu, a sumu smo raspisali po kardinalitetu od I.

morali smo dodati [tex]\binom{j}{i}[/tex] jer toliko ima podskupova od J s kardinalitetom |I|=i

8.14 svako područje mora biti omeđeno s barem tri brida jer inače graf ne bi bio jednostavan (postojali bi dvostruki bridovi)

7.2 mislim da treba pisati stroga nejednakost. ali [tex]|A|=61^2[/tex]
jer [tex]\alpha _1, \alpha _2 \in \{0,1,...,60\}[/tex]

7.7 svejedno je jer je [tex]\binom {3+2}{2} = \binom {3+2}{3}[/tex]

a zadnji sumand je broj puteva koji prolaze kroz oba segmenta. znači,
do točke [tex](2,2)[/tex], pa primjeti onda da na samo 1 način možemo doći do točke [tex](4,3)[/tex] tako da prođemo oba segmenta, i onda ovo zadnje od [tex](4,3)[/tex] do [tex](7,5)[/tex]

[shakespeare]

Hvala puno, Loo!

[PermutiranoPrase]

Da, ja sam idiot, još jučer uvečer sam vidjela da red iznad teorema piše što su [tex]A_I[/tex]. Hvala.

_________________
With great power comes great electricity bill.
n!!!!
Theorem 2: Alexander the Great did not exist and he had an infinite number of limbs.

[shakespeare]

Evo još jedno pitanjce, iako je odgovor vjerojatno očit kao i prije- zašto su rješenjima zadataka kada se pita je li graf Eulerov ( a jest ako dupušta Eulerovu turu) kaže da nije jer su više od dva vrha neparnog stupnja, kada za Eulerovu turu svi vrhovi moraju biti parni?

[an5]

da li moze netko rijesiti zadatak 3.9. iz skripte, odnosno dokazati teorem da je povezani graf bipartitan ako i samo ako sadrzi cikluse neparne duljine ...unaprijed se zahvaljujem

[sasha.f]

[student_92]

Može li netko reći kako obrazložiti algoritam koji nalazi [tex]2092[/tex]-tu permutaciju u leksikografskom poretku skupa [tex]\{1,2,...9\}[/tex]?

To stoji u poglavlju o generiranju komb. objekata na samom kraju cjeline.