Lad os sige, at vi har en graf $ G $. Vi vælger den ene kant fra den (enhver kant). Vil der altid være et sådant spændende træ, at indeholder den meget kant?
Jeg synes svaret er ja, for uanset hvad vi gør, kan vi altid skabe et sådant spændende træ, så selve kanten, vi valgte, er inkluderet. Naturligvis et mere formelt bevis ville være nødvendigt?
Kommentarer
- Du ' har ikke skrevet endnu et uformelt bevis: i det væsentlige du ' har sagt " Jeg synes svaret er ja, fordi svaret er ja. "
Svar
Bemærk, at den oprindelige graf $ G $ skal tilsluttes, ellers har den slet ingen spændende træer. (Selvom det samme argument anvendt på hver komponent ville vise, at enhver graf har en spændende skov, der indeholder en hvilken som helst valgt kant.)
Lad $ G = (V, E) $ være en tilsluttet graf, lad $ T $ være et hvilket som helst spændende undertræ, og lad $ e $ være enhver kant i $ E $. Vi hævder, at der er et spændende træ, der inkluderer $ e $. Hvis $ e \ i T $, er vi færdige. Ellers indeholder $ T + e $ en cyklus. Denne cyklus indeholder nødvendigvis mindst en kant $ e “\ neq e $ (faktisk indeholder den mindst to). $ T + ee” $ er et spændende træ, der indeholder $ e $.
Du skal bevise for dig selv, at $ T + ee “$ virkelig er et spændende træ.
Svar
Tilføjelse af en kant til et træ forårsager en unik cyklus. Du kan fjerne enhver kant fra denne cyklus (forskellig fra den, du tilføjede) for at få et træ tilbage. Dette nye træ indeholder den kant, der blev tilføjet.
Kommentarer
- At ' er præcis hvad jeg sagde!
- Ja, men Jeg sagde det med færre ord. 🙂
- Fordi mine syv sætninger virkelig skal sammenfattes i tre. Vi har fem tusind ubesvarede spørgsmål på webstedet – det ville være meget bedre at besvare nogle af dem end at sende duplikerede svar på spørgsmål, der ikke ' ikke har brug for dem.
- Så læs venligst det eksisterende svar s inden du sender en af dine egne.
- Intet er virkelig påkrævet – hvordan kunne vi alligevel håndhæve det? Men det forventes generelt, at svarene skal bidrage med noget nyt, og hvordan kan du vide, at du ' gør det, hvis du ikke ' ikke ved hvad ' er der allerede sagt? At have flere svar, der alle siger det samme, kludrer bare på siden, selvom det klart er, at ' ikke er en big deal med kun to. Udstationering af et kort svar i resuméstil kan helt sikkert være værdifuldt, når de eksisterende svar er lange Jeg tror bare ikke ' det tilføjer noget i denne særlige sag.