Powiedzmy, że mamy wykres $ G $. Wybieramy z niego jedną krawędź (dowolną krawędź). Czy zawsze będzie istniało takie drzewo opinające, że zawiera tę samą krawędź?
Myślę, że odpowiedź brzmi tak, ponieważ bez względu na to, co zrobimy, zawsze możemy utworzyć takie drzewo opinające, aby uwzględnić wybraną przez nas krawędź. Oczywiście bardziej formalny dowód będzie potrzebny?
Komentarze
- Ty ' nie napisałeś nawet nieformalnego dowodu: zasadniczo ' powiedziałeś " Myślę, że odpowiedź brzmi tak, ponieważ tak. "
Odpowiedź
Zwróć uwagę, że początkowy wykres $ G $ musi być połączone lub nie ma w ogóle drzew rozpinających (chociaż ten sam argument zastosowany do każdego składnika pokazałby, że każdy wykres ma las rozpinający zawierający dowolną wybraną krawędź).
Niech $ G = (V, E) $ będzie połączonym grafem, niech $ T $ będzie dowolnym poddrzewem obejmującym i niech $ e $ będzie dowolnym brzegiem $ E $. Twierdzimy, że istnieje drzewo opinające, które obejmuje $ e $. Jeśli $ e \ in T $, to wszystko. W przeciwnym razie $ T + e $ zawiera cykl. Ten cykl musi koniecznie zawierać co najmniej jedną krawędź $ e „\ neq e $ (w rzeczywistości zawiera co najmniej dwie). $ T + ee” $ to drzewo opinające zawierające $ e $.
Powinieneś udowodnić sobie, że $ T + ee „$ naprawdę jest drzewem opinającym.
Odpowiedź
Dodanie krawędzi do drzewa powoduje unikalny cykl. Możesz usunąć dowolną krawędź z tego cyklu (inną niż dodana), aby odzyskać drzewo. To nowe drzewo zawiera krawędź, która została dodana.
Komentarze
- To ' dokładnie to, co powiedziałem!
- Tak, ale Powiedziałem to z mniejszą liczbą słów. 🙂
- Ponieważ moje siedem zdań naprawdę trzeba podsumować w trzy. Mamy pięć tysięcy pytań bez odpowiedzi na stronie – znacznie lepiej byłoby odpowiedzieć na niektóre z nich, niż zamieścić zduplikowane odpowiedzi na pytania, które nie ' ich nie potrzebują.
- Następnie przeczytaj istniejącą odpowiedź s przed wysłaniem własnego.
- Tak naprawdę nic nie jest wymagane – jak moglibyśmy to wyegzekwować? Ale ogólnie oczekuje się, że odpowiedzi powinny wnieść coś nowego i skąd możesz wiedzieć, że ' robisz to, jeśli nie ' nie wiesz co ' zostało już powiedziane? Posiadanie wielu odpowiedzi, z których wszystkie mówią to samo, po prostu zaśmieca stronę, chociaż oczywiście ' to nic wielkiego, jeśli masz tylko dwa. Opublikowanie krótkiej, podsumowującej odpowiedzi może być zdecydowanie wartościowe, gdy istniejące odpowiedzi są długie; Po prostu nie ' nie wydaje mi się, żeby to coś dodało w tym konkretnym przypadku.