Forum@DeGiorgi :: Pogledajte temu - Zadacic iz diskretne

through

[^/[Print]\]
Idite na 1, 2 Sljedeće :| |:
Forum@DeGiorgi -> Čistilište

#1: Zadacic iz diskretne Autor/ica: hermione,

Postano: 20:22 pet, 19. 8. 2005
—
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

#2: Re: Zadacic iz diskretne Autor/ica: vjekovac,

Postano: 13:38 sub, 20. 8. 2005
—
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

#3: Autor/ica: hermione,

Postano: 15:47 sub, 20. 8. 2005
—
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.

#4: Autor/ica: hermione,

Postano: 17:02 sub, 20. 8. 2005
—
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.

#5: Autor/ica: vjekovac,

Postano: 18:32 sub, 20. 8. 2005
—

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

#6: Autor/ica: hermione,

Postano: 8:03 ned, 21. 8. 2005
—
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.

#7: Autor/ica: vjekovac,

Postano: 11:12 ned, 21. 8. 2005
—
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...

#8: Autor/ica: hermione,

Postano: 11:30 ned, 21. 8. 2005
—
Nazalost zbirke iz ovog kolegija nema.Jedino se po vjezbama moze raditi a na njima se rade vecinom zadaci sa rokova.

#9: Autor/ica: vjekovac,

Postano: 12:05 ned, 21. 8. 2005
—
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.

#10: Autor/ica: hermione,

Postano: 12:22 ned, 21. 8. 2005
—
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.

#11: Autor/ica: hermione,

Postano: 13:02 ned, 21. 8. 2005
—
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.

#12: Autor/ica: vjekovac,

Postano: 13:19 ned, 21. 8. 2005
—

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.

#13: Autor/ica: hermione,

Postano: 13:33 ned, 21. 8. 2005
—
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.

#14: Autor/ica: vjekovac,

Postano: 14:58 ned, 21. 8. 2005
—
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.

#15: Autor/ica: hermione,

Postano: 15:16 ned, 21. 8. 2005
—
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

#16: Autor/ica: vsego, Lokacija: /sbin/init

Postano: 15:35 ned, 21. 8. 2005
—

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? Smile

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

#17: Autor/ica: vjekovac,

Postano: 17:04 ned, 21. 8. 2005
—
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.

#18: Autor/ica: hermione,

Postano: 17:18 ned, 21. 8. 2005
—
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

#19: Autor/ica: vjekovac,

Postano: 17:40 ned, 21. 8. 2005
—
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.

#20: Autor/ica: Anđelčić,

Postano: 11:14 pon, 22. 8. 2005
—

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

Forum@DeGiorgi -> Čistilište

output generated using printer-friendly topic mod. Vremenska zona: GMT + 01:00.

Idite na 1, 2 Sljedeće :| |: Stranica 1 / 2.