Mul­ti­gra­phen – Übun­gen

1. Wel­che der fol­gen­den Gra­phen sind Mul­ti­gra­phen

   Gibt es Eu­ler­sche Kan­ten­zü­ge? Mar­kie­re mög­li­che Start- und End­kno­ten.

   

2. Kö­nigs­ber­ger Brü­cken­pro­blem

   

3. Woh­nungs­rund­gang

   

   Ist es mög­lich durch die ab­ge­bil­de­te Woh­nung einen Rund­gang zu ma­chen, so dass man jede Tür nur genau ein­mal pas­siert?

   Be­grün­de deine Ant­wort.

4. Brief­trä­ger­pro­blem

   

   Ist es mög­lich, dass der Brief­trä­ger seine Tour bei der Post be­ginnt, die durch­ge­zo­ge­nen Stra­ßen genau ein­mal ab­läuft und zum Schluss wie­der zur Post zu­rück­kehrt? Was än­dert sich, wenn sein Zu­stell­ge­biet ver­grö­ßert wird und die ge­stri­chelt ge­zeich­ne­ten Stra­ßen hin­zu­kom­men?

5. Schnee­pflug

   Ein Ge­mein­de­mit­ar­bei­ter muss mor­gens ei­ni­ge Stra­ßen mit einem Schnee­pflug räu­men. Er star­tet im Bau­hof B, will alle Stra­ßen nur ein­mal ab­fah­ren und dann wie­der zum Bau­hof zu­rück­keh­ren.

   

   1. Ist das mög­lich? Wenn ja, mache einen Vor­schlag.
   2. Ist es mög­lich, wenn die Stra­ße von E nach H wegen eines Un­falls ge­sperrt ist?

Mul­ti­gra­phen – Übun­gen: Her­un­ter­la­den [odt][186 KB]

Mul­ti­gra­phen – Übun­gen: Her­un­ter­la­den [pdf][151 KB]

Wei­ter zu an­de­re Rei­hen­fol­ge