Broj delimicnih podgrafova
Poslato: Petak, 19. April 2019, 19:46
Odrediti broj delimicnih podgrafova sa [inlmath]5[/inlmath] cvorova i [inlmath]6[/inlmath] grana potpunog grafa sa [inlmath]8[/inlmath] cvorova.
Potpun graf jeste regularan graf sa [inlmath]n[/inlmath] cvorova stepena [inlmath]n-1[/inlmath]. Dakle, ako imamo potpun graf od [inlmath]8[/inlmath] cvorova u njemu imamo [inlmath]{8\choose2}=28[/inlmath] grana. Treba da obrisemo [inlmath]3[/inlmath] cvora, to mozemo da uradimo na [inlmath]8\choose3[/inlmath] nacina. Posto brisemo [inlmath]3[/inlmath] cvora, brisemo i [inlmath]7+6+5=18[/inlmath] grana, pa ostaje [inlmath]10[/inlmath]. Sada od tih [inlmath]10[/inlmath] grana biramo [inlmath]6[/inlmath], a to je [inlmath]10\choose6[/inlmath], te je broj ovakvih delimicnih podgrafova jednak:
[dispmath]{8\choose3}\cdot{10\choose6}[/dispmath]
Je l je u redu ovo?
Potpun graf jeste regularan graf sa [inlmath]n[/inlmath] cvorova stepena [inlmath]n-1[/inlmath]. Dakle, ako imamo potpun graf od [inlmath]8[/inlmath] cvorova u njemu imamo [inlmath]{8\choose2}=28[/inlmath] grana. Treba da obrisemo [inlmath]3[/inlmath] cvora, to mozemo da uradimo na [inlmath]8\choose3[/inlmath] nacina. Posto brisemo [inlmath]3[/inlmath] cvora, brisemo i [inlmath]7+6+5=18[/inlmath] grana, pa ostaje [inlmath]10[/inlmath]. Sada od tih [inlmath]10[/inlmath] grana biramo [inlmath]6[/inlmath], a to je [inlmath]10\choose6[/inlmath], te je broj ovakvih delimicnih podgrafova jednak:
[dispmath]{8\choose3}\cdot{10\choose6}[/dispmath]
Je l je u redu ovo?