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
52
Vastaukset
- Anonyymi
Tämä löytyy ainakin sivulta math.stackexchange.com pienellä etsimisellä.
Ketjusta on poistettu 1 sääntöjenvastaista viestiä.
Luetuimmat keskustelut
- 1654428
- 263203
Kehutaan vaihteeksi Perussuomalaisia
Perussuomalaiset ovat olleet melkoisen lokakampanjoinnin kohteena, vaikka ovat saaneet paljon hyvää aikaiseksi. Nyt on1382721- 252328
SDP ylivoimainen ykkönen
En ole koskaan viitsinyt käydä äänestämässä, mutta nyt SDP:n etumatka on niin kutkuttava, että pakkohan se on vaivautua.602204Tiesitkö? Johannes Brotheruksen ex-isäpuoli on kuin onkin Mikko Kuustonen - Tästä on kyse!
Tiesitkö? Ja hehän on kuin kaksi marjaa... Johannes Brotherus on KUUMAA-yhtyeen jäsen ja tänä syksynä mukana Vain elämää191918Mitä tapahtuu?
Mitä säpäkän risteyksessä on tapahtunut kun poliiseja, ambulansseja ja kopteri paikalla?311724Roiskeläpät takaisin niin alkaa lasit kestämään
"Tuulilaseja hajottava talvi-ilmiö on ehkä ratkennut" Tämän päivän autoissa kun on esimerkiksi vanhempaa autokalustoa s391705Polttomoottoriauto on köyhän merkki
Kun ei ole varaa ostaa sähköautoa, niin joutuu köyhän autoa käyttämään.641320Murtautuminen uimahalliin
17.10. yöllä Kiuruveden uimahalliin murtauduttiin yläkerran oven ikkunasta. Onko kellään havaintoja tapauksesta?341181