Pulsar - wyjątkowy portal naukowy. Pulsar - wyjątkowy portal naukowy. Shutterstock
Strona główna

Ile tras? Rozwiązanie zagadki ze s. 9

Zadanie jest bardzo proste po zauważeniu, że do sześciu miast (A, B, E, F, G, H)
prowadzą tylko dwie drogi. Zatem miasto A musi znaleźć się na trasie okrężnej między miastami I a L, B między J a M, E między I a N, F między J a O, G między C a M i wreszcie H między D a N. Po oznaczeniu tych fragmentów trasy na schemacie dróg okaże się, że są one połączone lub mogą być połączone ze sobą i z pozostałymi miastami (D, K, P) tak, aby powstała trasa zamknięta – tylko w jeden sposób. A zatem komiwojażer ma przed sobą tylko jedną konkretną trasę (A-I-E-N-H-D-O-F-J-B-M-G-C-K-P-L-A), choć może ją pokonać w dwóch kierunkach.

Świat Nauki 09.2024 (300397) z dnia 01.09.2024; s. 74
Reklama