Zur Haupt­na­vi­ga­ti­on sprin­gen [Alt]+[0] Zum Sei­ten­in­halt sprin­gen [Alt]+[1]

Mul­ti­gra­phen – Übun­gen – Lö­sung

  1. Mul­ti­gra­phen, Eu­ler­sche Kan­ten­zü­ge

    Abbildung Multigraphen 1 Lösung zur Übung

    a) bis d) sind Mul­ti­gra­phen, da sie Mehr­fach­kan­ten be­sit­zen, meist Dop­pel­kan­ten.

    e) ist ein ein­fa­cher Graph. Alle Gra­phen außer d) be­sit­zen nur Kno­ten ge­ra­der Ord­nung und sind daher eu­lersch, es exis­tie­ren also bei a)-c) und e) ge­schlos­se­ne Eu­ler­sche Kan­ten­zü­ge.

    Bei d) gibt es of­fe­ne Eu­ler­sche Kan­ten­zü­ge mit den mar­kier­ten Start- bzw. End­kno­ten.

  2. Eu­ler­sche Kan­ten­zü­ge

    Nach dem Bau der 8. (bzw. 9.) Brü­cke waren Stadt­spa­zier­gän­ge mög­lich, bei denen man jede der 8 (bzw. 9) Brü­cken genau ein­mal über­quer­te. Nach dem Bau der 8. Brü­cke konn­te man auf der Insel be­gin­nen und en­de­te im Osten (oder um­ge­kehrt). Nach dem Bau der 9. Brü­cke konn­te man auch auf der Insel be­gin­nen, en­de­te aber im Süden (oder um­ge­kehrt). Ein ech­ter Rund­gang mit Rück­kehr zum Aus­gangs­punkt war nicht mög­lich (Die Gra­phen ent­hal­ten genau zwei un­ge­ra­de Kno­ten, es exis­tie­ren „nur“ of­fe­ne Eu­ler­sche Kan­ten­zü­ge).

  3. Woh­nungs­rund­gang

    Abbildung Multigraphen 2 Lösung zur Übung

    Mit einem Gra­phen lässt sich das Pro­blem über­sicht­lich dar­stel­len. Man fasst die Räume als Kno­ten und die Türen als Kan­ten auf. Der Graph hat genau zwei un­ge­ra­de Kno­ten (Raum C und E), d.h. es gibt of­fe­ne Eu­ler­sche Kan­ten­zü­ge. Der „Woh­nungs­rund­gang“ kann nur in C be­gin­nen und endet dann in E oder um­ge­kehrt. Ein mög­li­cher Rund­gang wäre z.B. CBACEA­FE­DE.

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

    Abbildung Multigraphen 3 Lösung zur Übung

    Es ist mög­lich. Fasst man die durch­ge­zo­ge­nen Li­ni­en als Kan­ten und die Schnitt­punk­te als Kno­ten eines Gra­phen auf, er­kennt man, dass alle Kno­ten die Ord­nung 2 oder 4 be­sit­zen, der Graph also eu­lersch ist. Wenn die ge­stri­chel­ten Li­ni­en als Kan­ten hin­zu­kom­men, ent­ste­hen die bei­den mar­kier­ten un­ge­ra­den Kno­ten, die dann Start- und End­kno­ten sein müs­sen. Der Brief­trä­ger muss dann ei­ni­ge Stra­ßen­zü­ge dop­pelt ab­lau­fen, um wie­der zur Post zu­rück­keh­ren zu kön­nen.

  5. Schnee­pflug

    Abbildung Multigraphen 4 Lösung zur Übung

    a) Ja, es ist mög­lich. Alle Kno­ten im Netz haben ge­ra­de Ord­nung. Daher exis­tiert min­des­tens ein Eu­ler­scher Kan­ten­zug, den der Fah­rer als Fahrt­rou­te nut­zen kann, z.B. BCI­HE­DAF­GAB.

    b) Falls die Stra­ße von E nach H aber ge­sperrt ist, so re­du­ziert sich die Ord­nung bei­der Kno­ten um 1 und ist damit un­ge­ra­de. Dann exis­tiert kein Eu­ler­scher Kan­ten­zug, der in B star­tet.

 

 

Mul­ti­gra­phen – Übun­gen – Lö­sung: Her­un­ter­la­den [odt][280 KB]

Mul­ti­gra­phen – Übun­gen – Lö­sung: Her­un­ter­la­den [pdf][239 KB]

 

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