Konigsberški mostovi

Problem mostova

• Prvi korak
• 
  Stari pruski grad Konigsberg, današnji Kalinjingrad u Rusiji,smješten je na obalama rijeke Pregel.
  Dio grada nalazi se na dva rijecna otoka,su povezana s kopnom i međusobno sa sedam mostova
  
• Drugi korak
• 
  Građani su voljeli šeteti mostovima, nikako nisu mogli pronaći način kako prijeći svih sedam mostova točno jednput i da se vrate u polaznu točku.
  Za pomoć su se obratili švicarskom matematičaru Leonhardu Euleru, koji je vrlo brzo pokazao da je takva šetnja nemoguća.
  
• Treći korak
  
• 
  Eulerovo riješenje problema:promatrao je niz slova A,B,C,D koji predstavljaju kopno(otoke i obale).
  Konstruirao je model račvanja da dokaže da ne postoji takav niz koji zadovoljava tražene uvjete,tj. dokazujući da problem Konigsberških mostova nema rješenja.
  
  Pri tome je formirao tri glavna zaključka:
  • Ako je bilo koje kopno (obala ili otok) povezano s nekim drugim kopnom neparnim brojem mostova, tada kružno putovanje koje prelazi svaki most točno jedanput nije moguće.
  • Ako je broj mostova neparan za točno dva kopna, tada je putovanje koje prelazi svaki most točno jedanput moguće samo ako putovanje počinje u jednom, a završava u drugom kopnu s neparnim brojem mostova.
  • Ako nema kopna povezanog s neparnim brojem mostova putovanje može početi iz bilo kojeg kopna i završiti u tom istom kopnu.