Baloni u teoriji grafova

Kako mi je matematika zapisana u genima, naravno da sam upućena da se dizajn balona može prikazati kao (orijentirani) graf: mjesta na kojima je balon zarotiran u "čvor" predstavljaju točke/vrhove u grafu, a dio balona između dva čvora je usmjerena linija (tzv. spojnica ili brid). Brid koji počinje i završava u istom vrhu zove se petlja. Prilikom izrade skulptura od balona poželjno je smanjiti broj balona, da bi se smanjio trošak materijala, kao i broj "čvorova" na svakom balonu, jer vezanje čvorova oduzima vrijeme (koje je također trošak), pa to predstavlja matematički problem.

 

prikaz osnovnih elemenata balona u teoriji grafova

 

Dakle, modeliranje balona može se opisati matematički kroz teoriju grafova, te izraditi elaborat o najmanjem broju čvorova/vrhova potrebnih za dizajn određene skulpture koja se sastoji od tzv. "šetnji" (alternirajućeg niza vrhova i bridova od kojih se sastoji svaki pojedini balon), koje mogu biti ponavljajuće ili ne, povezane ili nepovezane (npr. prilikom dodavanja novog balona u nekom drugom vrhu). 

 

Neke osnove teorije grafova: ako iz vrha izlazi neparan broj bridova, to je "neparan vrh", a vrh iz koje izlazi paran broj bridova zove se "paran vrh". Euler je dokazao da možete "prošetati" grafom koji ima točno dva neparna vrha na način da kroz svaki vrh prolazite točno jednom (tzv. Eulerov put) ako krenete iz jednog od neparnih vrhova i završite u drugom neparnom vrhu. Ako graf ima sve vrhove parne, možete prijeći svaki brid točno jednom, ali ćete završiti u istom vrhu iz kojeg ste krenuli (graf ima Eulerov put i Eulerov krug).

 

Da li je moguće napraviti figuru od samo jednog balona bez dodavanja drugog balona na neko mjesto - to je ekvivalent pitanju da li ovaj graf ima Eulerovu šetnju, tj. mogu li se svi bridovi u grafu proći točno jednom? Izvadite olovku i papir i pokušajte! Pogledajte možete li pratiti svaki rub točno jednom bez podizanja olovke. Rješavanje ovakvog problema ekvivalentan je "problemu sedam mostova Königsberga" koji je Euler riješio 1735. godine, postavljajući osnov tada buduće nove grane matematike - teorije grafova!