Inne, zadanie nr 3661
ostatnie wiadomo艣ci | regulamin | latex
| Autor | Zadanie / Rozwi膮zanie |
klauduska post贸w: 1 |  2015-10-10 21:23:28Witam, Mam do rozwi膮zania zadanie z Teorii liczb. To dopiero pocz膮tki mojej przygody z tym przedmiotem. Tre艣膰 zadania: Ile wierzcho艂k贸w i kraw臋dzi ma graf pe艂ny tr贸jdzielny Kl,m,n (l,m,n s膮 w indeksie dolnym). Moje domniemane rozwi膮zanie: Ilo艣膰 wierzcho艂k贸w r贸wna jest m+n. Czy to dobra odpowied藕? I co z liczb膮 kraw臋dzi? Nie do ko艅ca rozumiem zapis tego grafu Kl,m,n, szuka艂am jaki艣 informacji ale niestety jest opisany tylko graf pe艂ny dwudzielny. Z g贸ry bardzo dzi臋kuje za jak膮艣 pomoc :) |
tumor post贸w: 8070 | 2015-10-10 21:50:14 Przed uczeniem si臋 teorii liczb warto si臋 nauczy膰 czyta膰. Ju偶 pierwszy wynik z google, wikipedia, podaje, co to pe艂ny graf tr贸jdzielny. Graf tr贸jdzielny, jak sobie uog贸lnimy z definicji grafu dwudzielnego, to taki, w kt贸rym wierzcho艂ki mo偶na podzieli膰 na trzy zbiory roz艂膮czne, przy tym je艣li dwa wierzcho艂ki nale偶膮 do tego samego z tych trzech zbior贸w, to nie s膮 po艂膮czone kraw臋dzi膮. Graf pe艂ny tr贸jdzielny to taki, w kt贸rym po艂膮czone kraw臋dziami s膮 wszystkie wierzcho艂ki, kt贸re mog膮 by膰 po艂膮czone, by jeszcze zachowany by艂 warunek powy偶szy grafu tr贸jdzielnego. Zapis $K_{l,m,n}$ m贸wi tyle, 偶e wymienione trzy zbiory roz艂膮czne maj膮 odpowiednio l,m,n wierzcho艂k贸w. Graf ma zatem l+m+n wierzcho艂k贸w. Zliczenie kraw臋dzi jest r贸wnie偶 oczywiste. Ka偶dy wierzcho艂ek ze zbioru l-elementowego mo偶emy po艂膮czy膰 z n+m wierzcho艂kami z pozosta艂ych zbior贸w, ka偶dy wierzcho艂ek ze zbioru n-elementowego mo偶emy po艂膮czy膰 z l+m wierzcho艂kami, ka偶dy wierzcho艂ek ze zbioru m-elementowego mo偶emy po艂膮czy膰 z n+l wierzcho艂kami. Przy tym zliczaj膮c w ten spos贸b ilo艣膰 po艂膮cze艅 ka偶d膮 kraw臋d藕 liczyli艣my dwukrotnie. Je艣li umiesz mno偶y膰 i dodawa膰 liczby ca艂kowite, to prawdopodobnie znajdziesz rozwi膮zanie. |
| strony: 1 | |
Prawo do pisania przys艂uguje tylko zalogowanym u偶ytkownikom. Zaloguj si臋 lub zarejestruj