Să spunem că avem un grafic $ G $. Alegem o margine din ea (orice margine). Va exista întotdeauna un copac atât de întins încât conține chiar această margine?
Cred că răspunsul este da, deoarece indiferent de ceea ce facem, putem crea întotdeauna un astfel de copac care să includă chiar marginea pe care am ales-o. Desigur, o dovadă mai formală ar fi necesar?
Comentarii
- ' nu ați scris nici măcar o dovadă informală: în esență, tu ' ai spus " Cred că răspunsul este da, deoarece răspunsul este da. "
Răspuns
Rețineți că graficul inițial $ G $ trebuie conectat sau nu are deloc arbori care se întind. (Deși același argument aplicat fiecărei componente ar arăta că orice grafic are o pădure care cuprinde orice margine aleasă.)
Să fie $ G = (V, E) $ să fie un grafic conectat, să fie $ T $ fie orice subarborel care se întinde și lăsați $ e $ să fie orice edgein $ E $. Susținem că există un copac care include $ e $. Dacă $ e \ în T $, am terminat. În caz contrar, $ T + e $ conține un ciclu. Acest ciclu conține în mod necesar cel puțin o margine $ e „\ neq e $ (de fapt, conține cel puțin două). $ T + ee” $ este un copac care conține $ e $.
Ar trebui să vă demonstrați că $ T + ee „$ este într-adevăr un copac care se întinde.
Răspunde
Adăugarea unei margini la un arbore determină un ciclu unic. Puteți elimina orice margine din acest ciclu (diferită de cea pe care ați adăugat-o) pentru a obține înapoi un arbore. Acest arbore nou conține marginea care a fost adăugată.
Comentarii
- Exact ' ceea ce am spus!
- Da, dar Am spus-o cu mai puține cuvinte. 🙂
- Pentru că cele șapte propoziții ale mele într-adevăr trebuie rezumate în trei. Avem cinci mii de întrebări fără răspuns pe site – ar fi mult mai bine să răspundem la unele dintre acestea decât să postăm răspunsuri duplicat la întrebări care nu au ' nevoie de ele.
- Apoi vă rugăm să citiți răspunsul existent s înainte de a posta una a ta.
- Nimic nu este cu adevărat necesar – cum am putea să-l aplicăm, oricum? Dar, în general, este de așteptat ca răspunsurile să contribuie cu ceva nou și cum poți să știi că ' faci asta dacă nu știi ' ce ' s-a spus deja? Având mai multe răspunsuri care spun toți același lucru, aglomerați pagina, deși evident că ' nu este mare lucru cu doar doi. Postarea unui răspuns scurt, în stil rezumat, poate fi cu siguranță valoroasă atunci când răspunsurile existente sunt lungi; Nu cred că ' nu cred că adaugă ceva în acest caz particular.