Saarien sillat

Seuraa 
Viestejä45973
Liittynyt3.9.2015

Tässäpä purtavaa verkkoteoreetikoille.

Mantereen (M) sisällä on järvi. Järvessä on viisi saarta A, B, C, D ja E. Mantereen ja saarien välillä on siltoja seuraavasti:

Saarten väliset sillat:
AB, AD, AE, BC, BD, CD ja DE.

Mantereen ja saarien väliset sillat:
AM, MA, BM, MB, CM, MC, DM, EM ja ME.

Siis kaikista muista saarista on mantereelle kaksi siltaa paitsi saaresta D vain yksi silta. Kaikilla silloilla saa kulkea miten päin tahansa.

KYSYMYS:

Voidaanko kulkea sellainen reitti, että jokaista siltaa pitkin kävellään tasan kerran? Jos voidaan, niin millaisella reitillä?

Olisin kiinnostunut myös siitä, miten tällainen tehtävä verkkoteorian avulla lasketaan, kun sitä en ole tullut koskaan lukeneeksi. Siis viitteet teoriaan mukaan.

Kommentit (10)

Vierailija
Kale
Siis eikö tähän nyt sitten kenenkään kynnet pysty?

Kuulehan nyt. Tämä kysymys hipoo lähelle traditionaalista kauppamatkustajan ongelmaa. Pienellä koodin pläjäyksellä tuo kysymys ratkeaisi alta aikayksikön, mutta arvaa kiinnostaako nyt erityisesti tämä esittämäsi vaikeusaste?

Muotoile kysymyksesi uudelleen niin, että siinä on vähintään tuhat saarta, kysyt lyhimmän reitin, ja vastaus tippuisi kuin manulle illallinen. En minä ainakaan viitsi ruveta koodaamaan noin triviaaliin ja yksinkertaiseen kysymykseen riviäkään.

Jos palaisit suunnittelupöytäsi ääreen, ja pohtisit vähän haastavamman tehtävän, niin ehkä siitä voisi sitten joku kiinnostuakin.

-tostai

Vierailija

Systeemibiologia liittyy siis aiheeseen siten, että jos joku silta on hitaampi tai nopeampi kuin muut, niin siellä on poikkeava solu, esim syöpä.

Solun tai elimen tietojärjestelmä muistuttaa ihan tavallista tehdasta.

Vierailija

Voidaan.
mdcmc ... da. Näkee aika hyvin heti piirroksesta, jos semmoisen viitsii rustata.
Eli käytännön ongelmana kehno. Teoreettiseen puoleen ei minun kannata sanoa mitään.

Vierailija

Vastaus ongelmaan: EI VOIDA!

Kyseessä on todellakin Eulerin polun löytäminen, kuten Puuhikki jo ensimmäisessä vastauksessa totesi. Sen sijaan tässä ei tarvita lainkaan tietotekniikkaa eikä siis koodin vääntämistä, koska asian voi ratkaista paljon helpommin puhtaan matemaattisesti. Leonhard Euler todisti, että Eulerin polku on olemassa jos ja vain jos solmujen (nyt A, B, C, D, E ja M) asteluvuista on parittomia tasan 0 tai 2. Jälkimmäisessä tapauksessa Näiden parittomien solmujen pitää olla "päätepysäkit". Nyt solmujen asteluvu ovat

A: 5
B: 5
C: 4
D: 5
E: 4
M: 9

joten koska joukossa on neljä paritonta solmujen astelukua, niin etsittyä polkua ei siis ole olemassa.

Vierailija

Aijai, sattui lukihäiriö ja silloista 1 unohtui
Reitin mahdottomaksi osoittaminen on helppoa joo, ihan ilman Euleriakin Mutta sellaisen olemassaolon todistaminen aina kun tuo em. ehto täyttyy lienee jo vähän vaikeampi homma?

Vierailija
Hauankaivaja
Aijai, sattui lukihäiriö ja silloista 1 unohtui
Reitin mahdottomaksi osoittaminen on helppoa joo, ihan ilman Euleriakin Mutta sellaisen olemassaolon todistaminen aina kun tuo em. ehto täyttyy lienee jo vähän vaikeampi homma?

Ei suinkaan. Lauseessa on sanamuoto jos ja vain jos! Tämä tarkoittaa sitä, että jos ehto ei täyty, niin polkua ei ole. Vastaavasti jos ehto täytyy, niin polku varmuudella on olemassa. Se vain pitää enää löytää.

Uusimmat

Suosituimmat