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
Dowód, podzbiór krawędzi zawiera rozcięcie i cykl
-
- 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