Matematyka.pl

Witam, mam następujące zadanie: Mamy do dyspozycji 2 pręty o długości L oraz listę wymaganych długości prętów, które w miarę możliwości należy wyciąć: l_{1}, l_{2}, ..., l_{k} . Należy wyciąć największą możliwą liczbę prętów o długościach z podanej listy. Skonstruuj algorytm 1-bezwzględnie przybliżo...

Witam. Treść zadania przedstawia się następująco. Niech: v(G) - moc najliczniejszego skojarzenia, r(G) - moc najmniej licznego pokrycia wierzchołkowego, a(G) - moc najliczniejszego zbioru niezależnego p(G) - moc najmniej licznego pokrycia krawędziowego Pokazać, że: 1) v(G) \le r(G) 2) a(G) \le p(G) ...

Przepraszam, odwrotnie zapisałem nierówność. Już poprawione.

Witam.
Próbuję uporać się z następującym zadaniem:

Wykaż, że dla \(\displaystyle{ k}\) będącego długością najdłuższej ścieżki w grafie, zachodzi: \(\displaystyle{ x \le k+1}\), gdzie \(\displaystyle{ x}\) to liczba chromatyczna grafu.

Jakieś wskazówki?
Pozdrawiam.

Zadanie przedstawia się następująco:

Wykaż, że każdy graf o \(\displaystyle{ m}\) krawędziach zawiera podgraf dwudzielny posiadający co najmniej \(\displaystyle{ \frac{1}{2}m}\) krawędzi.

Byłbym wdzięczny za jakieś poważniejsze wskazówki.

Dzięki wielkie! Dedukcja jak najbardziej w porządku, wyhaczyłem tylko jeden błąd. W wyrażeniu: \left( \frac{n - 2}{k - 1} + a \right) \cdot k + n - \left( \frac{n - 2}{k - 1} - a\right) \cdot 1 = 2n - 2 + ak - a Powinno być n - \left( \frac{n - 2}{k - 1} + a\right) zamiast n - \left( \frac{n - 2}{k ...

Witam,
treść mojego zadania przedstawia się następująco.

Niech \(\displaystyle{ k > 1}\) będzie liczbą naturalną. Wykaż, że każde niepuste \(\displaystyle{ n}\)-wierzchołkowe drzewo posiada co najmniej \(\displaystyle{ n - \frac{n-2}{k-1}}\) wierzchołków stopnia mniejszego niż \(\displaystyle{ k.}\)

Jakieś wskazówki co do rozwiązania tego zadania?
Pozdrawiam.