Uz malo podsecanje iz
teorije grafova, vise terminoloski, mislim da imam neke odgovore:
1. Prvo pitanje je lako - imas 46 cvorova, iz svakog cvora ide po 8 grana, svaka grana spaja po 2 cvora. Znaci: 46*8/2 = 184 (C).
2. Ako graf sa n cvorova ima ukupno 26 grana, pri cemu je stepen svakog cvora (oznacimo ga sa S[j], gde je j redni broj cvora) najmanje 4 (a moze biti i veci), to znaci da vazi sledeca jednakost:
(S[1] + S[2] + ... + S[n]) / 2 = 26
S[j] >= 4 za svako j
Odatle sledi da je suma svih stepena S[1] + ... + S[n] = 52. Sto je stepen svakog pojedinacnog cvora (S[j]) manji treba ti vise sabiraka da bi dostigao 52, iz cega sledi da svaka vrednost S[j] mora da bude postavljena na svoj apsolutni minimum, sto je 4 (u skladu s drugom nejednakoscu). Samim tim 4*n = 52, iz cega sledi da je max(n) = 13 (B)
3. Graf ima 31 granu i 4+3+1 = 8 cvorova (taj jedan je taj famozni 'v'). Polovina zbira stepeni svih cvorova je jednak broju grana (31), sto znaci da je zbir stepeni svih cvorova 62:
S[1] + S[2] + ... + S[8] = 62
Prva 4 cvora imaju stepen 8, a druga 3 imaju stepen 7, sto znaci da je:
S[1] = S[2] = S[3] = S[4] = 8.
S[5] = S[6] = S[7] = 7.
Prema tome: 4*8 + 3*7 + x = 62, iz cega sledi da je x = 9 (C)
4. Ako dobro razumem, stablo je poseban slucaj grafa gde svaki cvor moze da ima samo jednog roditelja. Cvorovi stepena 1 su "deca", a cvorovi visih stepeni su roditelji. 15 cvorova nemaju potomstvo, 1 je plodni Pantelija sa 6 potomaka koji zajedno s njima cini skup od 7 cvorova koji se nalaze u korenu stabla. Posto stablo ima 21 cvor, ostaje 14 cvorova. Posto 15 cvorova nemaju decu, to znaci da jedan Pantin potomak nema decu, a ostalih 5 imaju i to je tih 14. Ako oznacimo sa C[j] ukupan broj grana koje spajaju tih 5 cvorova sa njihovih 14 potomaka, tada je:
C[1] + C[2] + C[3] + C[4] + C[5] = 14
Pri cemu C[j] moze da bude 2, 4 ili 5, jer svaki od cvorova vec ima jednu granu ka Panteliji. Ako izvrtimo sve kombinacije brojeva 2, 4 i 5 pete klase s ponavljanjem dobijamo:
2+2+2+2+2 = 10
2+2+2+2+4 = 12
2+2+2+2+5 = 13
2+2+2+4+4 = 14
2+2+2+4+5 = 15
2+2+2+5+5 = 16
2+2+4+4+4 = 16
itd.
Jedina kombinacija sa zbirom 14 je 2+2+2+4+4. Ako racunamo da svaki od tih 5 cvorova ima jedan uplink ka Panteliji, njihovi stepeni su: 3, 3, 3, 5, 5. Znaci, stablo ima: 15 cvorova stepena 1, 3 cvora stepena 3, 2 cvora stepena 5 i 1 cvor stepena 6 (Pantelija). Zakljucak: ukupan broj cvorova stepena 3 je 3 (B).
5. Ako stablo ima 3 cvora stepena 2, to automatski znaci da ima barem 3 cvora stepena 1 i barem jedan cvor stepena 5. Ako pretpostavimo da se u korenu stabla nalazi taj cvor stepena 5, tada on ima 2 potomka bez dece i 3 potomka sa po jednim detetom. Time smo ukupno potrosili 9 cvorova (1+5+3, pri cemu 1 ima stepen 5 (root), 3 imaju stepen 2 i 5 ima stepen 1). Tih 9 cvorova cine podskup stabla T koje cemo oznaciti sa S. Podskup S ima 5 cvorova stepena 1. Ostaje jos 4 cvora koja treba nekako povezati u graf, koji cine drugi podskup stabla T koji cemo oznaciti sa R. Posto svaki od ta 4 cvora iz skupa R moze imati samo stepene 1 ili 5 jedini nacin dse oni ukljuce u stablo je da nemaju potomstvo (odnosno da svaki cvor iz skupa R ima stepen 1), a da im roditelj bude jedan od ovih 5 cvorova iz skupa S sa stepenom 1. Time se broj cvorova iz skupa S koji imaju stepen 1 smanjuje sa 5 na 4, a broj cvorova iz skupa S sa stepeno 5 se povecava sa 1 na 2. Znaci, podskup S stabla T ima: 2 cvora stepena 5, 3 cvora stepena 2 i 4 cvora stepena 1. Sabrano sa cvorovima iz skupa R od kojih svaki ima stepen 1 dolazimo do zakljucka da stablo T ima: 2 cvora stepena 5, 3 cvora stepena 2 i 8 cvorova stepena 1. Dakle, resenje je: 8 cvorova stepena 1 i 2 cvora stepena 5 (C).
[Ovu poruku je menjao B3R1 dana 15.09.2021. u 14:29 GMT+1]
Par pitanja iz grafova?
Registrovani: 0 ( 0 )