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

Kar­ten­fär­be­pro­blem (op­tio­nal)

Be­grif­fe: Nä­he­rungs­al­go­rith­mus, Gree­dy-Ver­fah­ren, Un­ver­träg­lich­keits­graph, Back­tracking, pla­na­rer Graph, Cli­que, bi­par­ti­ter Graph

Das Map Co­lo­ring Pro­blem ist ein wei­te­res NP-voll­stän­di­ges Pro­blem, das vom Bil­dungs­plan als Al­ter­na­ti­ve zur do­mi­nie­ren­den Menge vor­ge­schla­gen wird. Es kann als wei­te­re An­wen­dung für einen Gree­dy-Al­go­rith­mus ver­wen­det wer­den. Der Graph be­schreibt hier Un­ver­träg­lich­kei­ten zwi­schen den Kno­ten und der Al­go­rith­mus teilt die ge­sam­te Kno­ten­men­ge in Teil­men­gen auf, bei denen es in­ner­halb der Teil­men­ge keine un­ver­träg­li­chen Kno­ten gibt. Da sich viele an­de­re Pro­blem­stel­lun­gen (z.B. Schie­nen­pla­nung in der Kurs­stu­fe) auf die­ses Pro­blem zu­rück­füh­ren las­sen, lohnt es sich, das Map Co­lo­ring Pro­blem im Un­ter­richt zu be­han­deln.

Das Ar­beits­blatt führt das Kar­ten­fär­be­pro­blem an­hand der Bun­des­län­der von Deutsch­land ein. Nach­dem die Schü­ler selbst eine Fär­bung ge­fun­den haben (nicht not­wen­di­ger­wei­se die op­ti­ma­le) wird das Pro­blem wie ge­wohnt in ein Gra­phen­pro­blem über­führt. An die­ser Stel­le kann schon die Be­trach­tung der An­zahl der Mög­lich­kei­ten, die Not­wen­dig­keit eines Nä­he­rungs­al­go­rith­mus mo­ti­vie­ren (wei­ter­füh­ren­de Fra­gen 3+4).

Bei die­sem Al­go­rith­mus ist nicht so of­fen­sicht­lich, was die "beste" Er­wei­te­rung der Teil­lö­sung (teil­wei­se ge­färb­ter Graph) sein soll. Daher bie­tet es sich an, den Schü­le­rin­nen und Schü­lern hier die Be­schrei­bung des Al­go­rith­mus zu geben oder eines der un­zäh­li­gen Vi­de­os zum Kar­ten­fär­be­pro­blem zu zei­gen und den Al­go­rith­mus dann hän­disch nach­voll­zie­hen zu las­sen.

Ge­ge­be­nen­falls kann der Al­go­rith­mus auch im­ple­men­tiert wer­den, da er recht ein­fach ist.

Er­gän­zung 1: Der Vier-Far­ben-Satz (Four Color Theo­rem)

Der Bil­dungs­plan schreibt nicht vor, den Vier-Far­ben-Satz zu be­han­deln. Die Schü­le­rin­nen und Schü­ler müs­sen also nicht er­klä­ren oder be­wei­sen kön­nen, warum sich jeder pla­na­re Graph mit vier Far­ben ein­fär­ben lässt.

Das Video "The Four Color Map Theo­rem - Num­ber­phi­le" (https://​www.​youtube.​com/​watch?​v=Ngb​K43j​B4rQ ) kann aber als Aus­blick und Denk­an­stoß ver­wen­det wer­den.

Er­gän­zung 2: Ko­lo­ni­al­pro­blem

Diese Er­wei­te­rung ver­tieft die Er­kennt­nis, dass es sich bei nor­ma­len Kar­ten um pla­na­re Gra­phen han­delt. Diese Ein­schrän­kung fällt beim Ko­lo­ni­al­pro­blem weg und ver­deut­licht, dass sich die Kno­ten eines Gra­phen im All­ge­mei­nen nicht in vier Teil­men­gen ohne Un­ver­träg­lich­kei­ten auf­tei­len las­sen.

Un­ter­richts­ver­lauf: Her­un­ter­la­den [odt][298 KB]

 

Wei­ter zu Mi­ni­mal span­nen­de Bäume