Skojarzenie w grafie dwudzielnym.

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
darcklord
Użytkownik
Użytkownik
Posty: 19
Rejestracja: 4 lip 2011, o 15:37
Płeć: Mężczyzna
Lokalizacja: Green Mountain
Podziękował: 5 razy

Skojarzenie w grafie dwudzielnym.

Post autor: darcklord » 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.

ODPOWIEDZ