Olkoon G yhtenäinen verkko jonka pisimmän polun pituus on M.
Osoita seuraavaa: jos G:llä on kaksi polkua, joiden molemman pituus on M, niin nämä leikkaavat jossain solmussa.
Minä lähdin silleen pähkäilemään, että jos meillä nyt on ne kaksi polkua ja jos ne olisikin erilliset, niin niiden välillä täytyy olla kumpaakaan leikkaamaton polku (leikataan luupit pois). Joo näin se taitaa tullakin, sitten lasketaan kumpi on pitempi ekan alku löydetty yhdistävä polku tokan loppu
vai tokan alku löydetty yhdistävä ekan loppu, koska yhdistävällä on jotain pituutta, niin jompi kumpi näistä poluista on pitempi kuin M, ristiriita.
Yhtenäisen verkon pisimmät polut leikkaavat
2
63
Vastaukset
- Anonyymi
Tämä löytyy ainakin sivulta math.stackexchange.com pienellä etsimisellä.
Ketjusta on poistettu 1 sääntöjenvastaista viestiä.
Luetuimmat keskustelut
Hallitus pyrkii rajoittamaan kaupan omien halpamerkkien myyntiä
Helsingin Sanomien mukaan hallitus valmistelee lakihanketta, joka suitsii kaupan valtaa ja rajoittaa omien halpamerkkien2323384- 602925
Björn Wahlroos, maataloustuet lakkautettava
Sanoo pankkimies. Mitäs persut ja muut tukinulliem perskärpäset tähän? "Wahlroos listaa kansallisen maataloustuen. – I262507Persut päättivät hiilivoiman kieltämisestä Suomessa
Moni on jo unohanut kuka hyväksyi hiilivoimaloiden kieltämisen Suomessa: persut Sukupuolineutraalit liikennemerkitk182482Työvoimatoimisto
Nyt kysyisin miksi pitää käydä työvoimatoimistossa paikanpäällä, kun he eivät muuta tee kuin laittavat koneelle uudet ve761993Muistattekos kuinka kokoomus ja persut vinkuivat sähkön hinnasta?
Oppositiossa vuonna 2022, kun sähkön hinta uhkasi nousta 20 senttiin kilowattitunnilta? Nyt ovat hiiren hiljaa, kun pitä851879Nalle Wahlroos ei ulise kuten Teemu Selänne sähkölaskuista
Nalle "hah hah" nauroi saamistaan sähkötuista, kun taas Teemu-poika itkeä tirautti kovasta sähkön hinnasta. Nalle nauro191835Vain persut vastustivat hiilivoimaloiden alasajoa
Persut vastusti jyrkästi hiilen kieltolakia ja on myöhemmin vaatinut hiilivoimaloiden pitämistä käytössä. He perusteliva401832Mikä aate kaiken pahan takana?
Se laiskistuttaa kansat, opettaa vaatimaan etuisuuksia, syleilee maailmoja eikä omaa kansaa.911682Mietin sua liikaa
Mietin nytkin sitä, että millaista se olisi tulla kotiin, kun sinä olisit täällä vastassa. Tai niin päin, että sinä tuli691023