Broj delimicnih podgrafova

PostPoslato: Petak, 19. April 2019, 20:46
od diopo
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? :think1:

Re: Broj delimicnih podgrafova

PostPoslato: Petak, 26. April 2019, 10:16
od Daniel
U redu je. Ja bih to radio tako što bih izabrao čvorove koje zadržavamo (da li ćeš izabrati čvorove koje brišeš ili koje zadržavaš, isti đavo, jer je [inlmath]{8\choose3}={8\choose5}[/inlmath]), a zatim bih od ukupno [inlmath]5\choose2[/inlmath] grana koliko ih ima u novom grafu, birao njih [inlmath]6[/inlmath], što mogu učiniti na [inlmath]{5\choose2}\choose6[/inlmath] načina. Dakle,
[dispmath]{8\choose5}\cdot{{5\choose2}\choose6}[/dispmath] što je jednako tvom rezultatu.