Prethodna tema :: Sljedeća tema |
Autor/ica |
Poruka |
hermione Forumaš(ica)
Pridružen/a: 23. 09. 2003. (10:50:57) Postovi: (152)16
Spol:
Sarma: -
|
|
[Vrh] |
|
vjekovac Forumaš(ica)
Pridružen/a: 23. 01. 2003. (18:26:55) Postovi: (2DB)16
Spol:
|
Postano: 13:38 sub, 20. 8. 2005 Naslov: Re: Zadacic iz diskretne |
|
|
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
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!
|
|
[Vrh] |
|
hermione Forumaš(ica)
Pridružen/a: 23. 09. 2003. (10:50:57) Postovi: (152)16
Spol:
Sarma: -
|
|
[Vrh] |
|
hermione Forumaš(ica)
Pridružen/a: 23. 09. 2003. (10:50:57) Postovi: (152)16
Spol:
Sarma: -
|
|
[Vrh] |
|
vjekovac Forumaš(ica)
Pridružen/a: 23. 01. 2003. (18:26:55) Postovi: (2DB)16
Spol:
|
Postano: 18:32 sub, 20. 8. 2005 Naslov: |
|
|
[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. )
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.
|
|
[Vrh] |
|
hermione Forumaš(ica)
Pridružen/a: 23. 09. 2003. (10:50:57) Postovi: (152)16
Spol:
Sarma: -
|
Postano: 8:03 ned, 21. 8. 2005 Naslov: |
|
|
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] |
|
vjekovac Forumaš(ica)
Pridružen/a: 23. 01. 2003. (18:26:55) Postovi: (2DB)16
Spol:
|
|
[Vrh] |
|
hermione Forumaš(ica)
Pridružen/a: 23. 09. 2003. (10:50:57) Postovi: (152)16
Spol:
Sarma: -
|
|
[Vrh] |
|
vjekovac Forumaš(ica)
Pridružen/a: 23. 01. 2003. (18:26:55) Postovi: (2DB)16
Spol:
|
Postano: 12:05 ned, 21. 8. 2005 Naslov: |
|
|
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] |
|
hermione Forumaš(ica)
Pridružen/a: 23. 09. 2003. (10:50:57) Postovi: (152)16
Spol:
Sarma: -
|
|
[Vrh] |
|
hermione Forumaš(ica)
Pridružen/a: 23. 09. 2003. (10:50:57) Postovi: (152)16
Spol:
Sarma: -
|
|
[Vrh] |
|
vjekovac Forumaš(ica)
Pridružen/a: 23. 01. 2003. (18:26:55) Postovi: (2DB)16
Spol:
|
Postano: 13:19 ned, 21. 8. 2005 Naslov: |
|
|
[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
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] |
|
hermione Forumaš(ica)
Pridružen/a: 23. 09. 2003. (10:50:57) Postovi: (152)16
Spol:
Sarma: -
|
Postano: 13:33 ned, 21. 8. 2005 Naslov: |
|
|
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] |
|
vjekovac Forumaš(ica)
Pridružen/a: 23. 01. 2003. (18:26:55) Postovi: (2DB)16
Spol:
|
|
[Vrh] |
|
hermione Forumaš(ica)
Pridružen/a: 23. 09. 2003. (10:50:57) Postovi: (152)16
Spol:
Sarma: -
|
|
[Vrh] |
|
vsego Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09) Postovi: (3560)16
Spol:
Lokacija: /sbin/init
|
Postano: 15:35 ned, 21. 8. 2005 Naslov: |
|
|
[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. |
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. |
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? |
Ali put 1-3-5-4-2-6 i dalje ostaje najveci.
_________________ 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] |
|
vjekovac Forumaš(ica)
Pridružen/a: 23. 01. 2003. (18:26:55) Postovi: (2DB)16
Spol:
|
Postano: 17:04 ned, 21. 8. 2005 Naslov: |
|
|
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
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. Ionako to sve nije standardizirano, bla, bla. 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.
=Q.E.D.
|
|
[Vrh] |
|
hermione Forumaš(ica)
Pridružen/a: 23. 09. 2003. (10:50:57) Postovi: (152)16
Spol:
Sarma: -
|
|
[Vrh] |
|
vjekovac Forumaš(ica)
Pridružen/a: 23. 01. 2003. (18:26:55) Postovi: (2DB)16
Spol:
|
|
[Vrh] |
|
Anđelčić Forumaš(ica)
Pridružen/a: 11. 05. 2005. (16:57:50) Postovi: (201)16
|
|
[Vrh] |
|
|