Matematyka dyskretna, zadanie nr 896
ostatnie wiadomo艣ci | regulamin | latex
| Autor | Zadanie / Rozwi膮zanie |
megustaaa post贸w: 2 |  2013-01-19 19:21:45Ile r贸偶nych podgraf贸w posiada graf b臋d膮cy cyklem o 4 wierzcho艂kach? |
tumor post贸w: 8070 | 2013-01-19 20:21:37 Sam jest swoim podgrafem. Na 4 sposoby mo偶emy usun膮膰 jedn膮 kraw臋d藕, wierzcho艂k贸w wtedy ruszy膰 nie mo偶emy. Na 2 sposoby mo偶emy usun膮膰 par臋 przeciwleg艂ych kraw臋dzi, wierzcho艂k贸w wtedy ruszy膰 nie mo偶emy Na 4 sposoby mo偶emy usun膮膰 dwie s膮siednie kraw臋dzie, przy tym albo eliminujemy wierzcho艂ek, kt贸ry by艂 mi臋dzy nimi, albo nie (czyli 8 mo偶liwo艣ci). Na 4 sposoby mo偶emy usun膮膰 3 kraw臋dzie. Zostan膮 2 wierzcho艂ki niepodpi臋te kraw臋dziami. Mo偶emy usun膮膰 ka偶dy lub nie, co da 4 warianty (razem 16) No i na 1 spos贸b usuwamy wszystkie kraw臋dzie, zostaj膮 4 wierzcho艂ki, czyli $2^4-1=15$ wariant贸w (bo liczba wierzcho艂k贸w nie jest 0). 1+4+2+8+16+15=46 Nie pami臋tam twierdze艅, kt贸re by pozwoli艂y liczy膰 to w og贸lnym przypadku :P |
| strony: 1 | |
Prawo do pisania przys艂uguje tylko zalogowanym u偶ytkownikom. Zaloguj si臋 lub zarejestruj