Zadacic iz diskretne

[hermione]

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

[vjekovac]

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]

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.

[hermione]

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.

[vjekovac]

[hermione]

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.

[vjekovac]

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.
Trebam se ipak malo zamisliti oko svakog zadatka, ne bacam to ja baš iz rukava...

[hermione]

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

[vjekovac]

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.

[hermione]

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.

[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.

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.

[vjekovac]

[hermione]

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.

[vjekovac]

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.

[hermione]

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?

[vsego]

[vjekovac]

Ah, pa sad tek shvaćam što je dijametar!
Isprva si mi dala krivu definiciju

[hermione]

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.

[vjekovac]

Vjerujem da autoru nije do ispravljanja grešaka za eventualna buduća izdanja. Sad ima drugih briga...
ali nisam mislio biti zloban.
Zapravo šteta jer knjiga je inače jako dobra. Navodno je trebala uslijediti i zbirka s riješenim zadacima.

[Anđelčić]