Search
 
 
  Engleski
 
 
 
Open in this window (click to change)
Forum@DeGiorgi: Početna
Forum za podršku nastavi na PMF-MO
Login Registracija FAQ Smajlići Članstvo Pretražnik Forum@DeGiorgi: Početna

Zadacic iz diskretne
Idite na 1, 2  Sljedeće
Moja sarma
 
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Ostalo - ozbiljno -> Čistilište
Prethodna tema :: Sljedeća tema  
Autor/ica Poruka
hermione
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 23. 09. 2003. (10:50:57)
Postovi: (152)16
Spol: kućni ljubimac
Sarma: -

PostPostano: 20:22 pet, 19. 8. 2005    Naslov: Zadacic iz diskretne Citirajte i odgovorite

Buduci da nema foruma iz Diskretne,pisem zadacic ovdje pa ako mi neko pomogne mrak!
Treba dokazati da za jednostavan graf struka 7 vrijedi da je
V(G)>=d^3-d^2+d+1(pri cemu je d u biti delta,tj minimalni stupanj grafa).
Hvala
Buduci da nema foruma iz Diskretne,pisem zadacic ovdje pa ako mi neko pomogne mrak!
Treba dokazati da za jednostavan graf struka 7 vrijedi da je
V(G)>=d^3-d^2+d+1(pri cemu je d u biti delta,tj minimalni stupanj grafa).
Hvala


[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail Posjetite Web stranice
vjekovac
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 23. 01. 2003. (18:26:55)
Postovi: (2DB)16
Spol: kućni ljubimac
Sarma = la pohva - posuda
182 = 198 - 16

PostPostano: 13:38 sub, 20. 8. 2005    Naslov: Re: Zadacic iz diskretne Citirajte i odgovorite

Stvarno zgodan zadačić, ugodno sam iznenađen! Jel to s nekog roka?

Fiksirajmo neki vrh, nazovimo ga w, i promotrimo sve putove duljine 4 čiji jedan kraj je vrh w. Dakle, putove oblika (ovdje ------ znači brid):

w--------neki_vrh--------neki_vrh--------neki_vrh

Graf ima struk 7, tj. najmanji ciklus u grafu ima duljinu 7. Iz toga slijedi da su svaka dva gornja puta disjunktna, zapravo jedino im je vrh w zajednički. Naime, kad bi neka dva takva puta imala još koji zajednički vrh (osim w), onda bi oni zatvorili ciklus duljine <=6.

Prebrojimo koliko vrhova leži na svim tim putovima. (Onda je jasno ukupni broj vrhova v(G) barem toliko.)

Najprije brojimo sam vrh w. On ima barem d susjeda. Svakih od tih d vrhova ima jos barem po d-1 novih susjeda. Svaki od ovih posljednjih d(d-1) vrhova isto ima jos barem d-1 novih susjeda.
Dakle,

v(G)>=
1+d+d(d-1)+d(d-1)(d-1)=
d^3-d^2+d+1

:changes:

[quote="hermione"]Buduci da nema foruma iz Diskretne,[/quote]
Meni se Kombinatorika čini najbliža.
[quote="hermione"]pisem zadacic ovdje pa ako mi neko pomogne mrak![/quote]
Totalni mrak! 8) :wink:
Stvarno zgodan zadačić, ugodno sam iznenađen! Jel to s nekog roka?

Fiksirajmo neki vrh, nazovimo ga w, i promotrimo sve putove duljine 4 čiji jedan kraj je vrh w. Dakle, putove oblika (ovdje ------ znači brid):

w--------neki_vrh--------neki_vrh--------neki_vrh

Graf ima struk 7, tj. najmanji ciklus u grafu ima duljinu 7. Iz toga slijedi da su svaka dva gornja puta disjunktna, zapravo jedino im je vrh w zajednički. Naime, kad bi neka dva takva puta imala još koji zajednički vrh (osim w), onda bi oni zatvorili ciklus duljine ⇐6.

Prebrojimo koliko vrhova leži na svim tim putovima. (Onda je jasno ukupni broj vrhova v(G) barem toliko.)

Najprije brojimo sam vrh w. On ima barem d susjeda. Svakih od tih d vrhova ima jos barem po d-1 novih susjeda. Svaki od ovih posljednjih d(d-1) vrhova isto ima jos barem d-1 novih susjeda.
Dakle,

v(G)>=
1+d+d(d-1)+d(d-1)(d-1)=
d^3-d^2+d+1

#CHanges

hermione (napisa):
Buduci da nema foruma iz Diskretne,

Meni se Kombinatorika čini najbliža.
hermione (napisa):
pisem zadacic ovdje pa ako mi neko pomogne mrak!

Totalni mrak! Cool Wink


[Vrh]
Korisnički profil Pošaljite privatnu poruku Posjetite Web stranice
hermione
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 23. 09. 2003. (10:50:57)
Postovi: (152)16
Spol: kućni ljubimac
Sarma: -

PostPostano: 15:47 sub, 20. 8. 2005    Naslov: Citirajte i odgovorite

Je,to je zadatak sa roka iz Diskretne odM Krnica.Ja ga nikako nisam mogla sama rijesiti.Puno ti hvala.Sada cu si ga prostudirati.
Je,to je zadatak sa roka iz Diskretne odM Krnica.Ja ga nikako nisam mogla sama rijesiti.Puno ti hvala.Sada cu si ga prostudirati.


[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail Posjetite Web stranice
hermione
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 23. 09. 2003. (10:50:57)
Postovi: (152)16
Spol: kućni ljubimac
Sarma: -

PostPostano: 17:02 sub, 20. 8. 2005    Naslov: Citirajte i odgovorite

Da li je ovo O.K.?


1.Odredite broj razlicith ciklusa duljine k u potpunom grafu K_n?
Rj.U biti trazim ciklicku k-permutaciju.pa je rez (n(n-1)(n-2)........(n-k+1))/k


2.Dokazite da k-regularan graf struka 5 ima barem k^2-k+1 vrhova.
Napomena-u jednom drugom roku drugog asistenta kaze da onda ima barem k^2+1 vrhova.

Rj.V(G)>=k^2+1>=k^2-k+1 pa je V(G)>=k^2-k+1


3.Neka je G povezan graf u kojem svaki vrh ima paran stupanj.Dokazite da vrijedi nejednakost

C(G-v)<=d(v)/2

Rj.Svaki vrh je parnog stupnja pa ima ciklicki rastav.Takoder za c(G) znamo da vrijedi c(G)+e(G)>=V(G).I tu stajem.Help.
Da li je ovo O.K.?


1.Odredite broj razlicith ciklusa duljine k u potpunom grafu K_n?
Rj.U biti trazim ciklicku k-permutaciju.pa je rez (n(n-1)(n-2)........(n-k+1))/k


2.Dokazite da k-regularan graf struka 5 ima barem k^2-k+1 vrhova.
Napomena-u jednom drugom roku drugog asistenta kaze da onda ima barem k^2+1 vrhova.

Rj.V(G)>=k^2+1>=k^2-k+1 pa je V(G)>=k^2-k+1


3.Neka je G povezan graf u kojem svaki vrh ima paran stupanj.Dokazite da vrijedi nejednakost

C(G-v)<=d(v)/2

Rj.Svaki vrh je parnog stupnja pa ima ciklicki rastav.Takoder za c(G) znamo da vrijedi c(G)+e(G)>=V(G).I tu stajem.Help.


[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail Posjetite Web stranice
vjekovac
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 23. 01. 2003. (18:26:55)
Postovi: (2DB)16
Spol: kućni ljubimac
Sarma = la pohva - posuda
182 = 198 - 16

PostPostano: 18:32 sub, 20. 8. 2005    Naslov: Citirajte i odgovorite

[quote="hermione"]1.Odredite broj razlicith ciklusa duljine k u potpunom grafu K_n?
Rj.U biti trazim ciklicku k-permutaciju.pa je rez (n(n-1)(n-2)........(n-k+1))/k[/quote]
Još to treba podijeliti s 2 jer nam nije važna orijentacija.
(I podrazumijeva se k>=3, inače je trivijalno.)

[quote="hermione"]2.Dokazite da k-regularan graf struka 5 ima barem k^2-k+1 vrhova.
Napomena-u jednom drugom roku drugog asistenta kaze da onda ima barem k^2+1 vrhova.[/quote]
Pa ovo je sasvim isto kao i gornji zadatak, samo gledamo putove iz vrha w duljine 3. Oni su svi disjunktni i ukupno imaju vrhova
1+k+k(k-1)=k^2+1.
Tvrdnja sa k^2-k+1 onda pogotovo vrijedi zbog
k^2+1>=k^2-k+1.
Ne znam zašto je to netko stavio. Vjerojatno se zabunio, ali tvrdnja vrijedi.

[quote="hermione"]3.Neka je G povezan graf u kojem svaki vrh ima paran stupanj.Dokazite da vrijedi nejednakost
C(G-v)<=d(v)/2[/quote]
A što znači oznaka c(G)? Davno sam slušao Diskretnu pa se ne sjecam koje oznake su se koristile. Možda broj komponenata povezanosti grafa? Čini mi se po smislu da je tako.

Neka je k=c(G-v) broj komponenata povezanosti grafa G-v.
Iz vrha v izlazi d(v) bridova i svaki od njih ulazi u neku od gornjih komponenata. (Ovo "izlazi" i "ulazi" nama smisla jer je graf neusmjeren, ali ovako mi se čini slikovitije. :) )
U svaku komponentu ulazi paran broj bridova iz v jer bi u protivnom zbroj svih stupnjeva vrhova u toj komponenti bio neparan. (To se moze vidjeti i iz rastava na cikluse, kad ga već spominješ.)
U svaku komponentu ulazi barem jedan brid (pa zbog parnosti [b]barem dva brida[/b]) iz v, jer bi u protivnom polazni graf bio nepovezan.
Dakle, d(v) je barem 2k, tj. k<=d(v)/2.
:scrambleup:
hermione (napisa):
1.Odredite broj razlicith ciklusa duljine k u potpunom grafu K_n?
Rj.U biti trazim ciklicku k-permutaciju.pa je rez (n(n-1)(n-2)........(n-k+1))/k

Još to treba podijeliti s 2 jer nam nije važna orijentacija.
(I podrazumijeva se k>=3, inače je trivijalno.)

hermione (napisa):
2.Dokazite da k-regularan graf struka 5 ima barem k^2-k+1 vrhova.
Napomena-u jednom drugom roku drugog asistenta kaze da onda ima barem k^2+1 vrhova.

Pa ovo je sasvim isto kao i gornji zadatak, samo gledamo putove iz vrha w duljine 3. Oni su svi disjunktni i ukupno imaju vrhova
1+k+k(k-1)=k^2+1.
Tvrdnja sa k^2-k+1 onda pogotovo vrijedi zbog
k^2+1>=k^2-k+1.
Ne znam zašto je to netko stavio. Vjerojatno se zabunio, ali tvrdnja vrijedi.

hermione (napisa):
3.Neka je G povezan graf u kojem svaki vrh ima paran stupanj.Dokazite da vrijedi nejednakost
C(G-v)⇐d(v)/2

A što znači oznaka c(G)? Davno sam slušao Diskretnu pa se ne sjecam koje oznake su se koristile. Možda broj komponenata povezanosti grafa? Čini mi se po smislu da je tako.

Neka je k=c(G-v) broj komponenata povezanosti grafa G-v.
Iz vrha v izlazi d(v) bridova i svaki od njih ulazi u neku od gornjih komponenata. (Ovo "izlazi" i "ulazi" nama smisla jer je graf neusmjeren, ali ovako mi se čini slikovitije. Smile )
U svaku komponentu ulazi paran broj bridova iz v jer bi u protivnom zbroj svih stupnjeva vrhova u toj komponenti bio neparan. (To se moze vidjeti i iz rastava na cikluse, kad ga već spominješ.)
U svaku komponentu ulazi barem jedan brid (pa zbog parnosti barem dva brida) iz v, jer bi u protivnom polazni graf bio nepovezan.
Dakle, d(v) je barem 2k, tj. k⇐d(v)/2.
#Scramble


[Vrh]
Korisnički profil Pošaljite privatnu poruku Posjetite Web stranice
hermione
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 23. 09. 2003. (10:50:57)
Postovi: (152)16
Spol: kućni ljubimac
Sarma: -

PostPostano: 8:03 ned, 21. 8. 2005    Naslov: Citirajte i odgovorite

Evo jos par zadataka:
Siladic:
1.Neka je G povezan graf s V>2d.Dokazite da tada G ima put duljine barem2d.(d-min stupanj grafa).

2.Dokazite da je diam(G^C)<=3, ako je G nepovezan graf ili je diam(g)>=3.(diam(G)je dijametar grafa,a G^C je komplement grafa G).(diam je duljina pita max duljine)

3.S p_k(n) oznacimo broj ciklusa duljine k u grafu s n vrhova.Odredite p_k(n) tako da proizvoljan graf s n vrhova i p_k(n)ciklusa duljine k bude povezan.

Krnic:
4.Pretpostavimo da je G k-povezan.Formirajmo novi graf H tako da grafu G dodamo novi vrh i njega spojimo s bilo kojih k vrhovau G.Odredite povezanost od H.(graf je k-povezan ako se svaka dva vrha mogu povezati sa barem k unutarnje disjunktnih puteva,tj puteva koji nemaju zajednickih unutarnjih tocaka).

5.Neka je G graf bez petlji ,a L(G) linijski graf od G.Dokazite:
a)Ako je graf Eulerov,onda je L(G) Eulerov i Hamiltonov.
b)Ako je G Hamiltonov,onda je i L(G)Hamiltonov.

Uputa-L(G)-vrhovi od L(G) su bridovi od G,a dva vrha u L(G) su spojena ako i samo ako su odgovarajuci bridovi u G incidentni.
Graf je Eulerov ako dopusta Eulerovu turu(zatvorena staza koja prolazi svakim bridom jedanputa.Graf je Eulerov akko su mu svi vrhovi parnog stupnja.
Graf je Hamiltonov ako ima Hamiltonov ciklus-razapinjuci ciklus grafa.

Hanzer:
6.Neka je d_1<d_2<......<=d_n niz stupnjeva grafa G i pretpostavimo da je d_k>=k za svaki k<=n-d_n-1.Dokazite da je graf G povezan.
Evo jos par zadataka:
Siladic:
1.Neka je G povezan graf s V>2d.Dokazite da tada G ima put duljine barem2d.(d-min stupanj grafa).

2.Dokazite da je diam(G^C)<=3, ako je G nepovezan graf ili je diam(g)>=3.(diam(G)je dijametar grafa,a G^C je komplement grafa G).(diam je duljina pita max duljine)

3.S p_k(n) oznacimo broj ciklusa duljine k u grafu s n vrhova.Odredite p_k(n) tako da proizvoljan graf s n vrhova i p_k(n)ciklusa duljine k bude povezan.

Krnic:
4.Pretpostavimo da je G k-povezan.Formirajmo novi graf H tako da grafu G dodamo novi vrh i njega spojimo s bilo kojih k vrhovau G.Odredite povezanost od H.(graf je k-povezan ako se svaka dva vrha mogu povezati sa barem k unutarnje disjunktnih puteva,tj puteva koji nemaju zajednickih unutarnjih tocaka).

5.Neka je G graf bez petlji ,a L(G) linijski graf od G.Dokazite:
a)Ako je graf Eulerov,onda je L(G) Eulerov i Hamiltonov.
b)Ako je G Hamiltonov,onda je i L(G)Hamiltonov.

Uputa-L(G)-vrhovi od L(G) su bridovi od G,a dva vrha u L(G) su spojena ako i samo ako su odgovarajuci bridovi u G incidentni.
Graf je Eulerov ako dopusta Eulerovu turu(zatvorena staza koja prolazi svakim bridom jedanputa.Graf je Eulerov akko su mu svi vrhovi parnog stupnja.
Graf je Hamiltonov ako ima Hamiltonov ciklus-razapinjuci ciklus grafa.

Hanzer:
6.Neka je d_1<d_2<......<=d_n niz stupnjeva grafa G i pretpostavimo da je d_k>=k za svaki k<=n-d_n-1.Dokazite da je graf G povezan.


[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail Posjetite Web stranice
vjekovac
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 23. 01. 2003. (18:26:55)
Postovi: (2DB)16
Spol: kućni ljubimac
Sarma = la pohva - posuda
182 = 198 - 16

PostPostano: 11:12 ned, 21. 8. 2005    Naslov: Citirajte i odgovorite

Eh pa sad, nemojmo baš pretjerivati! :?
Preporučio bih konzultiranje s vježbama ili nekom zbirkom zadataka.
Rado ću pomoći oko ponekog zadatka, ali sad ih je ipak malo previše. :roll:
Trebam se ipak malo zamisliti oko svakog zadatka, ne bacam to ja baš iz rukava...
Eh pa sad, nemojmo baš pretjerivati! Confused
Preporučio bih konzultiranje s vježbama ili nekom zbirkom zadataka.
Rado ću pomoći oko ponekog zadatka, ali sad ih je ipak malo previše. Rolling Eyes
Trebam se ipak malo zamisliti oko svakog zadatka, ne bacam to ja baš iz rukava...


[Vrh]
Korisnički profil Pošaljite privatnu poruku Posjetite Web stranice
hermione
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 23. 09. 2003. (10:50:57)
Postovi: (152)16
Spol: kućni ljubimac
Sarma: -

PostPostano: 11:30 ned, 21. 8. 2005    Naslov: Citirajte i odgovorite

Nazalost zbirke iz ovog kolegija nema.Jedino se po vjezbama moze raditi a na njima se rade vecinom zadaci sa rokova.
Nazalost zbirke iz ovog kolegija nema.Jedino se po vjezbama moze raditi a na njima se rade vecinom zadaci sa rokova.


[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail Posjetite Web stranice
vjekovac
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 23. 01. 2003. (18:26:55)
Postovi: (2DB)16
Spol: kućni ljubimac
Sarma = la pohva - posuda
182 = 198 - 16

PostPostano: 12:05 ned, 21. 8. 2005    Naslov: Citirajte i odgovorite

Mah dobro, ali onda barem pažljivo prepiši zadatke.

2. Ovo uopće ne mora vrijediti. Npr. gledamo graf G čiji vrhovi su 1,2,...,2m-1,2m, a bridom su spojeni samo vrhovi 2k-1 i 2k za k=1,...,m.
diam(G)=2, diam(G^c)>=m (zamisli ljestve).
Nije mi baš jasna niti konstrukcija rečenice.

3. Ovo je isto neprecizno zadano. Trivijalno, ali ako uzmem npr. p_k(n)=n^k, onda takvog grafa uopće nema, pa su svi takvi grafovi povezani.
Kako zapravo glasi zadatak? Traži li se možda najveći/najmanji takav p_k(n)?

1. Pretpostavimo da najdulji put P u grafu ima duljinu k<2d (tj. diam(G)=k). Vrhove tog puta označimo v_1, v_2,..., v_k.
Svi susjedi od v_1 i v_k se nalaze na putu P, jer bismo inače dodavanjem vrha dobili put duljine k+1.
Nadalje tvrdimo da postoji i, 1<=i<=k-1 takav da je v_1 spojen s v_(i+1) te v_k spojen s v_i. To se vidi po Dirichletovom principu: gledamo indekse svih susjeda od v_k te indekse umanjene za 1 svih susjeda od v_1. To je barem 2d brojeva iz skupa {1,...,k-1}, k-1<=2d-2 pa neka dva moraju biti jednaka.
Sve u svemu, imamo ciklus C duljine k:
put od v_1 do v_i, v_k, put od v_k do v_(i+1), v_1.
Graf G ima više od 2d>k vrhova pa postoji vrh koji ne pripada C. Zbog povezanosti to znači da neki vrh ciklusa C ima susjeda koji ne pripada C. Počevši od tog vrha možemo napraviti put duljine k+1.
Mah dobro, ali onda barem pažljivo prepiši zadatke.

2. Ovo uopće ne mora vrijediti. Npr. gledamo graf G čiji vrhovi su 1,2,...,2m-1,2m, a bridom su spojeni samo vrhovi 2k-1 i 2k za k=1,...,m.
diam(G)=2, diam(G^c)>=m (zamisli ljestve).
Nije mi baš jasna niti konstrukcija rečenice.

3. Ovo je isto neprecizno zadano. Trivijalno, ali ako uzmem npr. p_k(n)=n^k, onda takvog grafa uopće nema, pa su svi takvi grafovi povezani.
Kako zapravo glasi zadatak? Traži li se možda najveći/najmanji takav p_k(n)?

1. Pretpostavimo da najdulji put P u grafu ima duljinu k<2d (tj. diam(G)=k). Vrhove tog puta označimo v_1, v_2,..., v_k.
Svi susjedi od v_1 i v_k se nalaze na putu P, jer bismo inače dodavanjem vrha dobili put duljine k+1.
Nadalje tvrdimo da postoji i, 1<=i<=k-1 takav da je v_1 spojen s v_(i+1) te v_k spojen s v_i. To se vidi po Dirichletovom principu: gledamo indekse svih susjeda od v_k te indekse umanjene za 1 svih susjeda od v_1. To je barem 2d brojeva iz skupa {1,...,k-1}, k-1<=2d-2 pa neka dva moraju biti jednaka.
Sve u svemu, imamo ciklus C duljine k:
put od v_1 do v_i, v_k, put od v_k do v_(i+1), v_1.
Graf G ima više od 2d>k vrhova pa postoji vrh koji ne pripada C. Zbog povezanosti to znači da neki vrh ciklusa C ima susjeda koji ne pripada C. Počevši od tog vrha možemo napraviti put duljine k+1.


[Vrh]
Korisnički profil Pošaljite privatnu poruku Posjetite Web stranice
hermione
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 23. 09. 2003. (10:50:57)
Postovi: (152)16
Spol: kućni ljubimac
Sarma: -

PostPostano: 12:22 ned, 21. 8. 2005    Naslov: Citirajte i odgovorite

Konstrukcija recenice 2.zadatka niti meni nije jasna,ali sam ga prepisala kako pise na roku.Isto vrijedi i za 3.zadatak.Prepisah zadatke direktno sa rokova kako pise.Sorry sta te gnjavim,ali nitko od racunalaca to nece polagati jos dugo,a nas profaca ima jako malo koji to slusaju.
Konstrukcija recenice 2.zadatka niti meni nije jasna,ali sam ga prepisala kako pise na roku.Isto vrijedi i za 3.zadatak.Prepisah zadatke direktno sa rokova kako pise.Sorry sta te gnjavim,ali nitko od racunalaca to nece polagati jos dugo,a nas profaca ima jako malo koji to slusaju.


[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail Posjetite Web stranice
hermione
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 23. 09. 2003. (10:50:57)
Postovi: (152)16
Spol: kućni ljubimac
Sarma: -

PostPostano: 13:02 ned, 21. 8. 2005    Naslov: Citirajte i odgovorite

Malo proucih kostrukciju recenice 2.zad +par primjera i mislim da je to ovako- Ako je G nepovezan graf ili je diam(G)>=3,tada je diam(G^C)<=3.

Nacrtah si ljestvice,to je nepovezan graf.Njegov komplement je graf gdje ce svaki vrh biti spojen sa vrhom s kojim nije bio spojen u G.Diametar komplementa ce bti 2.Pa stima tvrdnja.
Onda sam si uzela graf diametra3.Nacrtala sam si njegov komlement i dobila da je njeov diam=3.
Tako da mislim da je konstrukcija recenice koju sam napisala da mislim da bi isla O.K.Ispravis me ako sam u krivu.:-)
No,znam da su to sve izdvojeni slucajevi i da se tvrdnja mora dokazati za sve grafove.
Malo proucih kostrukciju recenice 2.zad +par primjera i mislim da je to ovako- Ako je G nepovezan graf ili je diam(G)>=3,tada je diam(G^C)<=3.

Nacrtah si ljestvice,to je nepovezan graf.Njegov komplement je graf gdje ce svaki vrh biti spojen sa vrhom s kojim nije bio spojen u G.Diametar komplementa ce bti 2.Pa stima tvrdnja.
Onda sam si uzela graf diametra3.Nacrtala sam si njegov komlement i dobila da je njeov diam=3.
Tako da mislim da je konstrukcija recenice koju sam napisala da mislim da bi isla O.K.Ispravis me ako sam u krivu.Smile
No,znam da su to sve izdvojeni slucajevi i da se tvrdnja mora dokazati za sve grafove.


[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail Posjetite Web stranice
vjekovac
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 23. 01. 2003. (18:26:55)
Postovi: (2DB)16
Spol: kućni ljubimac
Sarma = la pohva - posuda
182 = 198 - 16

PostPostano: 13:19 ned, 21. 8. 2005    Naslov: Citirajte i odgovorite

[quote="hermione"]Malo proucih kostrukciju recenice 2.zad +par primjera i mislim da je to ovako- Ako je G nepovezan graf ili je diam(G)>=3,tada je diam(G^C)<=3.[/quote]
Pa tako sam i shvatio, ali ono je bio protuprimjer. G nisu ljestve nego ovo:
[code:1]o o o o
| | | |
o o o o[/code:1]
Komplement G^c sadrži put
[code:1]o---o---o---o[/code:1]
pa mu je dijametar barem 4.

Može i malo drukčiji primjer: G=
[code:1]o---o---o---o o
| | | |
o o o o o[/code:1]
Sada je diam(G)=5, G je nepovezan, ali G^c sadrži put duljine 5.

Zapravo, takvih primjera ima koliko hoćeš. U svakom slučaju, nešto tu ne valja.
hermione (napisa):
Malo proucih kostrukciju recenice 2.zad +par primjera i mislim da je to ovako- Ako je G nepovezan graf ili je diam(G)>=3,tada je diam(G^C)⇐3.

Pa tako sam i shvatio, ali ono je bio protuprimjer. G nisu ljestve nego ovo:
Kod:
o   o   o   o
|   |   |   |
o   o   o   o

Komplement G^c sadrži put
Kod:
o---o---o---o

pa mu je dijametar barem 4.

Može i malo drukčiji primjer: G=
Kod:
o---o---o---o   o
|   |   |   |
o   o   o   o   o

Sada je diam(G)=5, G je nepovezan, ali G^c sadrži put duljine 5.

Zapravo, takvih primjera ima koliko hoćeš. U svakom slučaju, nešto tu ne valja.


[Vrh]
Korisnički profil Pošaljite privatnu poruku Posjetite Web stranice
hermione
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 23. 09. 2003. (10:50:57)
Postovi: (152)16
Spol: kućni ljubimac
Sarma: -

PostPostano: 13:33 ned, 21. 8. 2005    Naslov: Citirajte i odgovorite

Shvatih ljestve kao karike,tj onako kako si nacrtao.Neka postoje bridovi 12,34,56 .To su bridovi grafa G.znaci u G^C postojat ce bridovi 13,14,15,16,23,24,25,26,35,36,45,46.(bridove koji se ponavljaju nisam pisala jer orjentacija nije bitna.Kada se to nacrta vidi se da je diam2.I stima tvrdnja.Ne znam,mozda je meni mozak pregorio od Diskretne vec.
Shvatih ljestve kao karike,tj onako kako si nacrtao.Neka postoje bridovi 12,34,56 .To su bridovi grafa G.znaci u G^C postojat ce bridovi 13,14,15,16,23,24,25,26,35,36,45,46.(bridove koji se ponavljaju nisam pisala jer orjentacija nije bitna.Kada se to nacrta vidi se da je diam2.I stima tvrdnja.Ne znam,mozda je meni mozak pregorio od Diskretne vec.


[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail Posjetite Web stranice
vjekovac
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 23. 01. 2003. (18:26:55)
Postovi: (2DB)16
Spol: kućni ljubimac
Sarma = la pohva - posuda
182 = 198 - 16

PostPostano: 14:58 ned, 21. 8. 2005    Naslov: Citirajte i odgovorite

Pa nije diam(G^c)=2. Postoji put duljine 3:
1---3---5
pa čak i put duljine 6:
1---3---5---4---2---6
Dakle diam(G^c)=6.
Pa nije diam(G^c)=2. Postoji put duljine 3:
1---3---5
pa čak i put duljine 6:
1---3---5---4---2---6
Dakle diam(G^c)=6.


[Vrh]
Korisnički profil Pošaljite privatnu poruku Posjetite Web stranice
hermione
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 23. 09. 2003. (10:50:57)
Postovi: (152)16
Spol: kućni ljubimac
Sarma: -

PostPostano: 15:16 ned, 21. 8. 2005    Naslov: Citirajte i odgovorite

Diametar je max udaljenost medu bridovima.A udaljenost je duljina najkraceg puta.
Tako da je 1----3----5 put duljine 2 jer ima dva brida.A sta se tice 1---3---5---4---2---6 ,postoji direktan brid koji povezuje vrh 1 i 6,tj 1------6.Ubit ces me ,jelda?:-)
Diametar je max udaljenost medu bridovima.A udaljenost je duljina najkraceg puta.
Tako da je 1----3----5 put duljine 2 jer ima dva brida.A sta se tice 1---3---5---4---2---6 ,postoji direktan brid koji povezuje vrh 1 i 6,tj 1------6.Ubit ces me ,jelda?Smile


[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail Posjetite Web stranice
vsego
Site Admin
Site Admin


Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (3560)16
Spol: zombi
Sarma = la pohva - posuda
854 = 1068 - 214
Lokacija: /sbin/init

PostPostano: 15:35 ned, 21. 8. 2005    Naslov: Citirajte i odgovorite

[quote="hermione"]Diametar je max udaljenost medu bridovima.A udaljenost je duljina najkraceg puta.[/quote]

:ccc:

[quote="D. Veljan, [i]Kombinatorna i diskretna matematika[/i], Algoritam, 2001, str. 250"][b]Dijametar[/b] grafa [i]G[/i], diam [i]G[/i] je maksimalna udaljenost medju njegovim bridovima, tj. [color=red]to je duljina puta maksimalne duljine u [i]G[/i][/color].[/quote]

8)

[quote="hermione"]Tako da je 1----3----5 put duljine 2 jer ima dva brida.A sta se tice 1---3---5---4---2---6 ,postoji direktan brid koji povezuje vrh 1 i 6,tj 1------6.Ubit ces me ,jelda?:-)[/quote]

Ali put 1-3-5-4-2-6 i dalje ostaje najveci. :)
hermione (napisa):
Diametar je max udaljenost medu bridovima.A udaljenost je duljina najkraceg puta.


Ccc.... Sram te bilo...

D. Veljan, Kombinatorna i diskretna matematika, Algoritam, 2001, str. 250 (napisa):
Dijametar grafa G, diam G je maksimalna udaljenost medju njegovim bridovima, tj. to je duljina puta maksimalne duljine u G.


Cool

hermione (napisa):
Tako da je 1----3----5 put duljine 2 jer ima dva brida.A sta se tice 1—3---5—4---2—6 ,postoji direktan brid koji povezuje vrh 1 i 6,tj 1------6.Ubit ces me ,jelda?Smile


Ali put 1-3-5-4-2-6 i dalje ostaje najveci. Smile



_________________
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.
Drzim prodike
[Vrh]
Korisnički profil Pošaljite privatnu poruku
vjekovac
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 23. 01. 2003. (18:26:55)
Postovi: (2DB)16
Spol: kućni ljubimac
Sarma = la pohva - posuda
182 = 198 - 16

PostPostano: 17:04 ned, 21. 8. 2005    Naslov: Citirajte i odgovorite

Ah, pa sad tek shvaćam što je dijametar!
Isprva si mi dala krivu definiciju :mrgreen:
[quote="hermione"]diam je duljina pita max duljine[/quote]
Dakle trebalo bi biti ovako:
[quote="hermione"]Diametar je max udaljenost među [b]vrhovima[/b]. A udaljenost dvaju vrhova je duljina najkraćeg puta između njih.[/quote]
Ali onda je ovo što piše u knjizi (doista tako piše, i ja sam pogledao) sasvim krivo. Trebalo bi pisati:
[quote="knjiga"]Dijametar grafa G, diam G je maksimalna udaljenost medju njegovim [b]vrhovima[/b], tj. to je [b]maksimum duljina najkraćih putova[/b] između svaka dva vrha grafa.[/quote]
I usput sam u knjizi primijetio još jednu stvar:
Duljina puta je broj njegovih bridova, a ne vrhova. Dakle, npr.
o-----o-----o-----o
ima duljinu 3, a ne 4. Logično, ali ja sam mislio da je drukčije (nekako sam krivo zapamtio) pa sam tako i pisao. To je važno u ovom zadatku zbog dijametra.

Hja dobro, tko bi se sjećao svih definicija. :oops: Ionako to sve nije standardizirano, bla, bla. :mrgreen: Matematika je samo "hipotetičko znanje". Definicije, konvencije i oznake same za sebe nemaju nikakvu vrijednost. Khm, da.

Dobro, evo onda konačno rješenja zadatka:
[quote="hermione"]Ako je G nepovezan graf ili je diam(G)>=3,tada je diam(G^c)<=3.[/quote]
Pretpostavimo diam(G)>=3. To znači da postoje dva vrha, u i v, čija udaljenost je >=3. To znači da u i v nisu spojeni bridom niti imaju zajedničkih susjeda (jer bi inače bili spojeni putom duljine 1 ili 2). Drugim riječima, svaki preostali vrh w nije spojen s u ili nije spojen s v.
U grafu G^c je situacija ovakva (obrnuta): u i v su spojeni bridom, svaki preostali vrh w je spojen s u ili je spojen s v. Sada je jasno da se svaka dva vrha u G^c mogu spojiti putom duljine <=3 preko vrhova u i v.
Npr.
w----u----v----w'
ili
w----u----w'
Prema tome, diam(G^c)<=3.

Pretpostavimo sada da je G nepovezan. To znači da se skup vrhova može particionirati na dva skupa A i B tako da vrhovi iz različitih skupova nisu povezani. (Komponenata povezanosti može biti >=2, ali uvijek ih možemo podijeliti u 2 skupa.)
U G^c je situacija obrnuta:
Svaki vrh iz A je spojen sa svakim vrhom iz B. Sada je jasno i da svaka dva vrha iz A (analogno za B) možemo spojiti putom duljine 2 preko nekog vrha iz B.
Prema tome, diam(G^c)<=2. (čak i bolje od <=3)

U oba slučaja smo dokazali diam(G^c)<=3.
:squarewink: =Q.E.D.
Ah, pa sad tek shvaćam što je dijametar!
Isprva si mi dala krivu definiciju Mr. Green
hermione (napisa):
diam je duljina pita max duljine

Dakle trebalo bi biti ovako:
hermione (napisa):
Diametar je max udaljenost među vrhovima. A udaljenost dvaju vrhova je duljina najkraćeg puta između njih.

Ali onda je ovo što piše u knjizi (doista tako piše, i ja sam pogledao) sasvim krivo. Trebalo bi pisati:
knjiga (napisa):
Dijametar grafa G, diam G je maksimalna udaljenost medju njegovim vrhovima, tj. to je maksimum duljina najkraćih putova između svaka dva vrha grafa.

I usput sam u knjizi primijetio još jednu stvar:
Duljina puta je broj njegovih bridova, a ne vrhova. Dakle, npr.
o-----o-----o-----o
ima duljinu 3, a ne 4. Logično, ali ja sam mislio da je drukčije (nekako sam krivo zapamtio) pa sam tako i pisao. To je važno u ovom zadatku zbog dijametra.

Hja dobro, tko bi se sjećao svih definicija. Embarassed Ionako to sve nije standardizirano, bla, bla. Mr. Green Matematika je samo "hipotetičko znanje". Definicije, konvencije i oznake same za sebe nemaju nikakvu vrijednost. Khm, da.

Dobro, evo onda konačno rješenja zadatka:
hermione (napisa):
Ako je G nepovezan graf ili je diam(G)>=3,tada je diam(G^c)⇐3.

Pretpostavimo diam(G)>=3. To znači da postoje dva vrha, u i v, čija udaljenost je >=3. To znači da u i v nisu spojeni bridom niti imaju zajedničkih susjeda (jer bi inače bili spojeni putom duljine 1 ili 2). Drugim riječima, svaki preostali vrh w nije spojen s u ili nije spojen s v.
U grafu G^c je situacija ovakva (obrnuta): u i v su spojeni bridom, svaki preostali vrh w je spojen s u ili je spojen s v. Sada je jasno da se svaka dva vrha u G^c mogu spojiti putom duljine ⇐3 preko vrhova u i v.
Npr.
w----u----v----w'
ili
w----u----w'
Prema tome, diam(G^c)⇐3.

Pretpostavimo sada da je G nepovezan. To znači da se skup vrhova može particionirati na dva skupa A i B tako da vrhovi iz različitih skupova nisu povezani. (Komponenata povezanosti može biti >=2, ali uvijek ih možemo podijeliti u 2 skupa.)
U G^c je situacija obrnuta:
Svaki vrh iz A je spojen sa svakim vrhom iz B. Sada je jasno i da svaka dva vrha iz A (analogno za B) možemo spojiti putom duljine 2 preko nekog vrha iz B.
Prema tome, diam(G^c)⇐2. (čak i bolje od ⇐3)

U oba slučaja smo dokazali diam(G^c)⇐3.
#Wink2 =Q.E.D.


[Vrh]
Korisnički profil Pošaljite privatnu poruku Posjetite Web stranice
hermione
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 23. 09. 2003. (10:50:57)
Postovi: (152)16
Spol: kućni ljubimac
Sarma: -

PostPostano: 17:18 ned, 21. 8. 2005    Naslov: Citirajte i odgovorite

Hvala ti.Ovaj dijamter me skroz ubio u pojam.Ja sam ga shvatila kako si i sam rekao da bi definicija trebala glasiti.A i inace je ta knjiga puna gresaka.Barem ovaj Diskretni dio. :oops:
Hvala ti.Ovaj dijamter me skroz ubio u pojam.Ja sam ga shvatila kako si i sam rekao da bi definicija trebala glasiti.A i inace je ta knjiga puna gresaka.Barem ovaj Diskretni dio. Embarassed


[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail Posjetite Web stranice
vjekovac
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 23. 01. 2003. (18:26:55)
Postovi: (2DB)16
Spol: kućni ljubimac
Sarma = la pohva - posuda
182 = 198 - 16

PostPostano: 17:40 ned, 21. 8. 2005    Naslov: Citirajte i odgovorite

Vjerujem da autoru nije do ispravljanja grešaka za eventualna buduća izdanja. Sad ima drugih briga...
:OT: ali nisam mislio biti zloban. :gg:
Zapravo šteta jer knjiga je inače jako dobra. Navodno je trebala uslijediti i zbirka s riješenim zadacima.
Vjerujem da autoru nije do ispravljanja grešaka za eventualna buduća izdanja. Sad ima drugih briga...
Off-topic ali nisam mislio biti zloban. Mr Green being very Greeen indeed
Zapravo šteta jer knjiga je inače jako dobra. Navodno je trebala uslijediti i zbirka s riješenim zadacima.


[Vrh]
Korisnički profil Pošaljite privatnu poruku Posjetite Web stranice
Anđelčić
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 11. 05. 2005. (16:57:50)
Postovi: (201)16
Sarma = la pohva - posuda
= 22 - 16

PostPostano: 11:14 pon, 22. 8. 2005    Naslov: Citirajte i odgovorite

[quote="vjekovac"]Vjerujem da autoru nije do ispravljanja grešaka za eventualna buduća izdanja. Sad ima drugih briga...
[/quote]
Jooooj, kak je ovo zlobno bilo... :roll:
vjekovac (napisa):
Vjerujem da autoru nije do ispravljanja grešaka za eventualna buduća izdanja. Sad ima drugih briga...

Jooooj, kak je ovo zlobno bilo... Rolling Eyes


[Vrh]
Korisnički profil Pošaljite privatnu poruku
Prethodni postovi:   
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Ostalo - ozbiljno -> Čistilište Vremenska zona: GMT + 01:00.
Idite na 1, 2  Sljedeće
Stranica 1 / 2.

 
Forum(o)Bir:  
Ne možete otvarati nove teme.
Ne možete odgovarati na postove.
Ne možete uređivati Vaše postove.
Ne možete izbrisati Vaše postove.
Ne možete glasovati u anketama.
You can attach files in this forum
You can download files in this forum


Powered by phpBB © 2001, 2002 phpBB Group
Theme created by Vjacheslav Trushkin
HR (Cro) by Ančica Sečan