Řekněme, že máme graf $ G $. Vybereme z něj jednu hranu (jakoukoli hranu). Bude vždy existovat takový překlenovací strom, který obsahuje ten samý okraj?
Myslím, že odpověď je ano, protože bez ohledu na to, co děláme, můžeme vždy vytvořit takový překlenovací strom, aby byl zahrnut i ten samý okraj, který jsme vybrali. Samozřejmě, formálnější důkaz bylo by potřeba?
Komentáře
- Napsali jste ' ani neformální důkaz: v podstatě, ' řekl jste " Myslím, že odpověď je ano, protože odpověď je ano. "
Odpověď
Všimněte si, že počáteční graf $ G $ je třeba připojit, nebo nemá vůbec žádné kostry. (Stejný argument aplikovaný na každou komponentu by však ukázal, že jakýkoli graf má kostru obsahující jakoukoli vybranou hranu.)
Nechte $ G = (V, E) $ je připojený graf, nechť $ T $ může být libovolný překlenující podstrom a nechat $ e $ libovolný okraj $ E $. Tvrdíme, že existuje překlenovací strom, který obsahuje $ e $. Pokud $ e \ v T $, máme hotovo. Jinak $ T + e $ obsahuje cyklus. Tento cyklus nutně obsahuje alespoň jeden okraj $ e „\ neq e $ (ve skutečnosti obsahuje alespoň dva). $ T + ee“ $ je překlenovací strom, který obsahuje $ e $.
Měli byste si dokázat, že $ T + ee „$ je opravdu klenutý strom.
Odpověď
Přidání hrany ke stromu způsobí jedinečný cyklus. Z tohoto cyklu můžete odstranit kteroukoli hranu (odlišnou od té, kterou jste přidali), abyste strom dostali zpět. Tento nový strom obsahuje přidanou hranu.
Komentáře
- To je ' přesně to, co jsem řekl!
- Ano, ale Řekl jsem to méně slovy. 🙂
- Protože mých sedm vět opravdu je třeba shrnout do tří. Máme pět tisíc nezodpovězených otázek na webu – bylo by mnohem lepší odpovědět na některé z nich, než zveřejňovat duplicitní odpovědi na otázky, které je ' nepotřebujete.
- Pak si prosím přečtěte stávající odpověď s před zveřejněním jednoho z vašich vlastních.
- Nic opravdu není vyžadováno – jak bychom to mohli vymáhat? Obecně se ale očekává, že odpovědi by měly přispět něčím novým, a jak můžete vědět, že to děláte, pokud ' to neuděláte, pokud nevíte co ' s již bylo řečeno? Mít více odpovědí, které všechny říkají totéž, prostě přeplňuje stránku, i když to zjevně není div jen s dvěma. Zveřejnění krátké odpovědi v souhrnném stylu může být určitě cenné, pokud jsou stávající odpovědi dlouhé; Jen si ' nemyslím, že v tomto konkrétním případě něco přidá.