Skojarzenie w grafie dwudzielnym.
: 4 lip 2011, o 15:58
ponoć zadanie jest tak łatwe, że żaden z moich wykładowców nie jest w stanie go rozwiązać, a żaden z moich znajomych już nie pamięta jak to się robiło.
Pokazac, że dowolny graf dwudzielny z l krawedziami posiada skojarzenie rozmiaru co
najmniej \(\displaystyle{ \frac{l}{\Delta(G)}}\), gdzie \(\displaystyle{ \Delta(G)}\) oznacza maxymalny stopien wierzchołka w G.
ja sam już tyle różnych i dziwnych prób rozwiązania tego zadania widziałem, że szczerze przyznaje nie wiem jak je rozwiązać poprawnie i zadowalająco dla prowadzącego zajęcia.-- 4 lip 2011, o 16:12 --tak więc proszę o pomoc w rozwiązaniu tego zadania.
Pokazac, że dowolny graf dwudzielny z l krawedziami posiada skojarzenie rozmiaru co
najmniej \(\displaystyle{ \frac{l}{\Delta(G)}}\), gdzie \(\displaystyle{ \Delta(G)}\) oznacza maxymalny stopien wierzchołka w G.
ja sam już tyle różnych i dziwnych prób rozwiązania tego zadania widziałem, że szczerze przyznaje nie wiem jak je rozwiązać poprawnie i zadowalająco dla prowadzącego zajęcia.-- 4 lip 2011, o 16:12 --tak więc proszę o pomoc w rozwiązaniu tego zadania.