Prikazi cijelu temu
08.05.2011 21:02
08.05.2011 21:02
Predmet:Re: Zadaci iz algebre
Ovo je teorija grafova (oblast nastala 1736 godine). Graf je skup tacaka (cvorova) i skup grana (pravih) koje ih povezuju.
K3,3 oznaka grafa i zadatku. Govori o rasporedu cvorova).
* * * kucice
* * * bunari
Ovo je bipartitan graf ne spajaju se cvorovi iste grupe. Odnosno ne spajaju se kucice sa jucicama, a ni bunari sa bunarima.
Planaran graf moze se nacrtati tako da mu se grane ne sijeku tj da se spoje sve kucice sa bunarima tako da se putevi ne sijeku.
Kod ovih grafova vrijedi:
n-broj cvorova
m-broj grana
f- broj oblasti(trougao, kvadrat, nema dijagonala samo su redom povezani cvorovi)
k-broj komponenti( koliko dijelova ima graf npr: imamo 3 cvora, 2 su povezana granom a treci nije povezan (stoji sam pored usamljeni cvor), onda imamo 2 komponente , a ako je on povezan granomza bilo koji od druga dva cvora ili samo sa jednim onda je broj kontura 1.
Imamo:
n+f=m+k+1
K3,3 povezan, nema
usamljenih cvorova pa je k=1
n+f=m+1+1=m+2
3f ≤ 2m pa je
f=m+2-n
zamjenom 3f ≤ 2m dobijamo
3(m+2-n) ≤ 2m
3m+6-3n ≤ 2m
3m+2m ≤ 3n-6
m ≤ 3n-6
putevi se ne sijeku.
Iz K3,3 bipartitan vazi
4f ≤ 2m
K3,3 je osnovnoi primjer za neplanaran graf trj nemoguce je spojiti 3 kucice sa 3 bunara a da im se putevi ne sijeku. Ovo je jedna teorema koja se dokazuje na sljedeci nacin.
n=6(3kucice+3bunara)
m=9 (broj puteva kad se svaka kucica spoji sa svakim
bunarom)
pretpostavimo da je K3,3 planaran graf, tj.
m=3n-6
9 ≤ 3*6-6=18-6=12 ovo je uredu idamo dalje
N+f=m+2
f=m+2-n
f=9+2-6
f=5
graf je bipartitan pa je
4f ≤ 3m
4*5 ≤ 2*9
20 ≤ 18( nije tacno)
Pa K3,3 nije planaran.
Citiraj roza:
Zadatak 53
Kako povezati putem 3 kucice sa 3 bunara (svaku kucicu sa svakim bunarom ), a da se putevi ne ukrstaju. Ni jedna kucica ne smije biti povezana ni sa jednom od druge dvije kucice, a ni jedan bunar ne smije biti povezan ni sa jednim od druga dva bunara.
Ovo je teorija grafova (oblast nastala 1736 godine). Graf je skup tacaka (cvorova) i skup grana (pravih) koje ih povezuju.
K3,3 oznaka grafa i zadatku. Govori o rasporedu cvorova).
* * * kucice
* * * bunari
Ovo je bipartitan graf ne spajaju se cvorovi iste grupe. Odnosno ne spajaju se kucice sa jucicama, a ni bunari sa bunarima.
Planaran graf moze se nacrtati tako da mu se grane ne sijeku tj da se spoje sve kucice sa bunarima tako da se putevi ne sijeku.
Kod ovih grafova vrijedi:
n-broj cvorova
m-broj grana
f- broj oblasti(trougao, kvadrat, nema dijagonala samo su redom povezani cvorovi)
k-broj komponenti( koliko dijelova ima graf npr: imamo 3 cvora, 2 su povezana granom a treci nije povezan (stoji sam pored usamljeni cvor), onda imamo 2 komponente , a ako je on povezan granomza bilo koji od druga dva cvora ili samo sa jednim onda je broj kontura 1.
Imamo:
n+f=m+k+1
K3,3 povezan, nema
usamljenih cvorova pa je k=1
n+f=m+1+1=m+2
3f ≤ 2m pa je
f=m+2-n
zamjenom 3f ≤ 2m dobijamo
3(m+2-n) ≤ 2m
3m+6-3n ≤ 2m
3m+2m ≤ 3n-6
m ≤ 3n-6
putevi se ne sijeku.
Iz K3,3 bipartitan vazi
4f ≤ 2m
K3,3 je osnovnoi primjer za neplanaran graf trj nemoguce je spojiti 3 kucice sa 3 bunara a da im se putevi ne sijeku. Ovo je jedna teorema koja se dokazuje na sljedeci nacin.
n=6(3kucice+3bunara)
m=9 (broj puteva kad se svaka kucica spoji sa svakim
bunarom)
pretpostavimo da je K3,3 planaran graf, tj.
m=3n-6
9 ≤ 3*6-6=18-6=12 ovo je uredu idamo dalje
N+f=m+2
f=m+2-n
f=9+2-6
f=5
graf je bipartitan pa je
4f ≤ 3m
4*5 ≤ 2*9
20 ≤ 18( nije tacno)
Pa K3,3 nije planaran.
"Ne treba se stidjeti nikakvog posla, pa čak ni onog najprljavijeg; treba se stidjeti samo besposlenog života." - Tolstoj