La oss si at vi har en graf $ G $. Vi velger en kant fra den (hvilken som helst kant). Vil det alltid være et slikt tre som inneholder akkurat den kanten?
Jeg tror svaret er ja, for uansett hva vi gjør, kan vi alltid lage et slikt spennende tre slik at selve kanten vi valgte er inkludert. Selvfølgelig et mer formelt bevis ville være nødvendig?
Kommentarer
- Du ' har ikke skrevet engang et uformelt bevis: egentlig, du ' har sagt " Jeg tror svaret er ja, fordi svaret er ja. "
Svar
Merk at den innledende grafen $ G $ må være koblet sammen, ellers har det ingen spenner av trær i det hele tatt. (Selv om det samme argumentet som brukes på hver komponent, vil vise at en hvilken som helst graf har en spennende skog som inneholder hvilken som helst valgt kant.)
La $ G = (V, E) $ være en tilkoblet graf, la $ T $ være et hvilket som helst spennende undertrær, og la $ e $ være en hvilken som helst kant i $ E $. Vi hevder at det er et spennende tre som inkluderer $ e $. Hvis $ e \ i T $, er vi ferdige. Ellers inneholder $ T + e $ en syklus. Den syklusen inneholder nødvendigvis minst en kant $ e «\ neq e $ (faktisk inneholder den minst to). $ T + ee» $ er et spennende tre som inneholder $ e $.
Du bør bevise for deg selv at $ T + ee «$ virkelig er et spennende tre.
Svar
Å legge til en kant i et tre forårsaker en unik syklus. Du kan fjerne en hvilken som helst kant fra denne syklusen (forskjellig fra den du la til) for å få tilbake et tre. Dette nye treet inneholder kanten som ble lagt til.
Kommentarer
- At ' er akkurat det jeg sa!
- Ja, men Jeg sa det med færre ord. 🙂
- Fordi de syv setningene mine virkelig trenger å bli oppsummert i tre. Vi har fem tusen ubesvarte spørsmål på nettstedet – det ville være mye bedre å svare på noen av dem enn å legge ut dupliserte svar på spørsmål som ikke ' ikke trenger dem.
- Les deretter det eksisterende svaret s før du legger ut en av dine egne.
- Ingenting er egentlig påkrevd – hvordan kunne vi håndheve det, uansett? Men det forventes generelt at svarene skal bidra med noe nytt, og hvordan kan du vite at du ' gjør det hvis du ikke vet ' hva ' er allerede sagt? Å ha flere svar som alle sier det samme, kludrer bare siden, selv om det åpenbart er at ' ikke er så farlig med bare to. Å legge ut et kort sammendragsstil kan definitivt være verdifullt når de eksisterende svarene er lange; Jeg tror bare ikke ' det legger til noe i dette tilfellet.