Dowód, podzbiór krawędzi zawiera rozcięcie i cykl

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
TrzyRazyCztery
Użytkownik
Użytkownik
Posty: 101
Rejestracja: 24 maja 2014, o 17:53
Płeć: Mężczyzna
Lokalizacja: Wro
Podziękował: 27 razy
Pomógł: 1 raz

Dowód, podzbiór krawędzi zawiera rozcięcie i cykl

Post autor: TrzyRazyCztery »

Witam mam za zadanie:
C jest podzbiorem krawędzi Grafu \(\displaystyle{ G}\). Wykaz ze jeżeli \(\displaystyle{ C}\) ma wspólną krawędz z każdym lasem spinającym grafu \(\displaystyle{ G}\) to \(\displaystyle{ C}\) zawiera pewne rozcięcie. I to samo dla cyklu.

Wydaje mi się że pierwszą cześć można udowodnić w ten sposób, że skoro las spinający ma tą własność że usunięcie jakiejkolwiek krawędzi spowoduje powstanie dodatkowej składowej to jesli usunę z każdego lasu jedną krawędz (tą którą zawiera \(\displaystyle{ C}\)) to w moim grafie nie bedzie żadnego z lasów spinających \(\displaystyle{ G}\) a to oznacza że powstanie kolejna składowa. Wiec w szczególnosci zbior \(\displaystyle{ A}\) zawierajacy wszystkie krawędzie z \(\displaystyle{ C}\) które są wspólne z drzewami bedzie zbiorem rozspajającym. A skoro rozcięcie jest najmniejszym podzbiorem zbioru rozspającego spełniającym warunki, nazwijmy ten zbiór krawędzi \(\displaystyle{ R}\) to znaczy że \(\displaystyle{ R\subseteq A}\) a to oznacza że \(\displaystyle{ R \subseteq C}\)

Czy jest to poprawne rozumowanie?
A co z cyklem? nie mam pomysłu. Pozdrawiam
ODPOWIEDZ