szukanie zaawansowane
 [ Posty: 1 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 27 sty 2016, o 13:02 
Użytkownik

Posty: 101
Lokalizacja: Wro
Witam mam za zadanie:
C jest podzbiorem krawędzi Grafu G. Wykaz ze jeżeli C ma wspólną krawędz z każdym lasem spinającym grafu G to 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 C) to w moim grafie nie bedzie żadnego z lasów spinających G a to oznacza że powstanie kolejna składowa. Wiec w szczególnosci zbior A zawierajacy wszystkie krawędzie z 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 R to znaczy że R\subseteq A a to oznacza że R \subseteq C

Czy jest to poprawne rozumowanie?
A co z cyklem? nie mam pomysłu. Pozdrawiam
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 1 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Własności synchronicznych szyfrów strumieniowych dowód  Sabisia193  0
 podzbior  Doktór Piter  2
 Dowód zachowania stopnia wierzchołka w izomorfizmie grafów  Renq77  6
 Liczby Catalana. Dowód.  IloveAlgebra  2
 Dowód nierówności w grafie  Fray  4
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl