Grafteori
(Nu när terminen är över har jag äntligen tid för bloggen. Detta inlägg författades för två månader sedan ombord på en buss från Stansted till Cambridge.)
I boardingkön på Skavsta studerade jag pålarna och banden som används för att styra folkmassan. Varje påle har ett utragbart band som kan hakas fast i någon av de andra pålarna. Min första fundering var då förstås ifall detta var tillräckligt - ibland bygger man ju tre- eller fyrvägskorsningar med banden och då kanske det krävs att korsningspålen har flera band att mata ut.
Den stora frågan är alltså: givet en (sammanhängande) karta över var pålarna ska stå och banden ska dras, hur realiserar man detta så att varje band matas ut från en av pålarna vid dess ändpunkter och varje påle matar ut som mest ett band? Exempel (i ASCII art):
O--O--O--O--O O<-O<-O<-O<-O
| | | ^
| | v |
O O--O--O--O ---> O O->O->O->O
| | | ^
| | v |
O--O--O--O--O O->O->O->O->O
Det är självklart omöjligt om det finns fler band än pålar på ritningen. Exempelvis kan inte den "digitala åttan" realiseras eftersom åttan har sju kanter (band) men bara sex noder (pålar):
O--O--O
| | |
O--O--O
Om det finns minst lika många pålar som band är det dock alltid möjligt (för en sammanhängande ritning - är ritningen inte sammanhängande får man dela upp i komponenter och behandla varje separat). Då är lösningsalgoritmen som följer:
1. Så länge det finns pålar kvar på ritningen som bara ska anslutas till en granne, mata ut bandet från den ensamma pålen och koppla fast i dess enda granne, samt glöm att den existerar (så om grannen tidigare hade två grannar blir den nu ensam).
2. Antingen blir det en ensam påle kvar, och då är du klar, eller så blir det en enda stor ring kvar att koopla ihop, och då uppnås det genom att alla pålar matar ut åt samma håll, exempelvis medurs.
Det visar sig att kravet på antal band/pålar är ekvivalent med att det finns max en ring av band (per sammanhängande komponent) på ritningen. Notera att denna beskrivning inte beror på var man ställer ut pålarna på ritningen utan endast var man vill dra band (förutsatt att man inte tillåter att band korsas). Alltså kan man inte bygga en åtta hur man än placerar ut pålarna (men om man tillåter korsningar så är det lätt genom att man bygger den som den klassiska racingbanan).
När man bygger kösystem är man ju inte ute efter att hindra folk från att nå vissa områden, utan bara styra dem till att gå en viss bana, så man vill inte ha några ringar alls och då genererar algoritmen alltid en lösning.
Om man vill ringa in saker med banden, exempelvis på ett museum, så behöver man dubblera några av pålarna (för att simulera en påle med flera band att mata ut). Då misstänker jag att en optimal lösning (minst antal extrapålar) uppnås genom att man helt enkelt stoppar in dem i ringar för att bryta upp dem, tills endast en ring återstår.
I boardingkön på Skavsta studerade jag pålarna och banden som används för att styra folkmassan. Varje påle har ett utragbart band som kan hakas fast i någon av de andra pålarna. Min första fundering var då förstås ifall detta var tillräckligt - ibland bygger man ju tre- eller fyrvägskorsningar med banden och då kanske det krävs att korsningspålen har flera band att mata ut.
Den stora frågan är alltså: givet en (sammanhängande) karta över var pålarna ska stå och banden ska dras, hur realiserar man detta så att varje band matas ut från en av pålarna vid dess ändpunkter och varje påle matar ut som mest ett band? Exempel (i ASCII art):
O--O--O--O--O O<-O<-O<-O<-O
| | | ^
| | v |
O O--O--O--O ---> O O->O->O->O
| | | ^
| | v |
O--O--O--O--O O->O->O->O->O
Det är självklart omöjligt om det finns fler band än pålar på ritningen. Exempelvis kan inte den "digitala åttan" realiseras eftersom åttan har sju kanter (band) men bara sex noder (pålar):
O--O--O
| | |
O--O--O
Om det finns minst lika många pålar som band är det dock alltid möjligt (för en sammanhängande ritning - är ritningen inte sammanhängande får man dela upp i komponenter och behandla varje separat). Då är lösningsalgoritmen som följer:
1. Så länge det finns pålar kvar på ritningen som bara ska anslutas till en granne, mata ut bandet från den ensamma pålen och koppla fast i dess enda granne, samt glöm att den existerar (så om grannen tidigare hade två grannar blir den nu ensam).
2. Antingen blir det en ensam påle kvar, och då är du klar, eller så blir det en enda stor ring kvar att koopla ihop, och då uppnås det genom att alla pålar matar ut åt samma håll, exempelvis medurs.
Det visar sig att kravet på antal band/pålar är ekvivalent med att det finns max en ring av band (per sammanhängande komponent) på ritningen. Notera att denna beskrivning inte beror på var man ställer ut pålarna på ritningen utan endast var man vill dra band (förutsatt att man inte tillåter att band korsas). Alltså kan man inte bygga en åtta hur man än placerar ut pålarna (men om man tillåter korsningar så är det lätt genom att man bygger den som den klassiska racingbanan).
När man bygger kösystem är man ju inte ute efter att hindra folk från att nå vissa områden, utan bara styra dem till att gå en viss bana, så man vill inte ha några ringar alls och då genererar algoritmen alltid en lösning.
Om man vill ringa in saker med banden, exempelvis på ett museum, så behöver man dubblera några av pålarna (för att simulera en påle med flera band att mata ut). Då misstänker jag att en optimal lösning (minst antal extrapålar) uppnås genom att man helt enkelt stoppar in dem i ringar för att bryta upp dem, tills endast en ring återstår.
Kommentarer