Inne, zadanie nr 3661

Autor	Zadanie / Rozwiązanie
klauduska postów: 1	2015-10-10 21:23:28 Witam, 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