Yhtenäisen verkon pisimmät polut leikkaavat

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.

2

73

    Vastaukset

    Anonyymi (Kirjaudu / Rekisteröidy)
    5000
    • Anonyymi

      Tämä löytyy ainakin sivulta math.stackexchange.com pienellä etsimisellä.

      • Joo, kerkesin sen linkin nähdäkin ennen kuin tekotyhmyys poisti viestin :D


    Ketjusta on poistettu 1 sääntöjenvastaista viestiä.

    Luetuimmat keskustelut

    1. Vesikin maksaa, miksei hengitysilma?

      Jatkuvasti itketään ettei ole rahaa mihinkään, mutta tilastojen mukaan rahaa on enemmän kuin koskaan, joten miksei asial
      Maailman menoa
      13
      1713
    2. Satuolennoista tarinointi ei kuulu peruskoulun tehtäviin

      Opetustunteja on muutenkin käytössä vain rajallinen määrä. Eli nämä satuhommat koulun ulkopuolelle vapaaehtoisiin harras
      Maailman menoa
      140
      1702
    3. Suomalainen perheenisä vaatii Suvivirren esittämisestä hyvityksiä

      Itse lapsena uskonnonopetuksesta vissiin traumoja saanut ihka suomalainen (!) perheenisä vaatii Espoon kaupungilta korva
      Maailman menoa
      291
      1312
    4. Lahkokasteen ja kristillisen kasteen erot

      Raamatun mukaan Kristillisessä yhdessä kasteessa Jumala pesee ja puhdistaa ihmisen sydämen ja poistaa perisynnin kirouks
      Kaste
      422
      1098
    5. Mies profiloin sinut

      Etsit täysin hallittavaa mutta samalla poikkeuksellista ihmistä. Etsit jotain mitä et koskaan tule saamaan.
      Ikävä
      210
      1076
    6. Mitä haluaisit

      Tehdä kaivattusi kanssa?
      Ikävä
      130
      972
    7. Salainen kastekoulutus

      Millainen on helluntailainen kastekoulutus ja kauanko se kestää ?
      Kaste
      285
      965
    8. Heikki Paasosen Marita-vaimo jätti tunteikkaat jäähyväiset: "Tällä kertaa me..."

      Heikki Paasonen on naimisissa Marita Paasosen (os. Alatalo) kanssa ja heillä on kaksi pientä lasta. Nyt koitti aika jätt
      Suomalaiset julkkikset
      3
      915
    9. Känsäkoura ja hotelli

      Tietoa kuka ostanut?
      Kuhmo
      10
      895
    10. Pirkanlinna yleisötapahtuma

      Oli todella hyvä tilaisuus. Ja EERO. L. Aivan mahtava tyyppi. Veti rennosti ja asiallisesti. Ja yleisöltä hyviä kysymyks
      Ähtäri
      49
      888
    Aihe