Zum Inhalt springen

Dreifarbenproblem

aus Wikipedia, der freien Enzyklopädie

Das Dreifarbenproblem ist ein Entscheidungsproblem aus der Graphentheorie. Gefragt ist, ob die Knoten eines einfachen Graphen so mit drei Farben einfärbbar sind, dass zueinander benachbarte Knoten unterschiedliche Farben haben. Das Problem ist NP-vollständig.<ref>{{#if:|{{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}| |}}}}{{#if:Dorothea Wagner|Dorothea Wagner: }}{{#if:|{{#if:Theoretische Grundlagen der Informatik|[{{#invoke:Vorlage:Internetquelle|archivURL|1={{#invoke:URLutil|getNormalized|1={{{archiv-url}}}}}}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=Theoretische Grundlagen der Informatik}}]{{#if:PDF; 874 kB| (PDF; 874 kB)}}{{#if:Vorlaufiges Skript zur Vorlesung| Vorlaufiges Skript zur Vorlesung{{#invoke:Vorlage:Internetquelle|Endpunkt|titel=Vorlaufiges Skript zur Vorlesung}}}}}}|{{#if:https://i11www.iti.kit.edu/_media/teaching/winter2011/tgi/tgi_skript_ws11.pdf%7C{{#if:{{#invoke:TemplUtl%7Cfaculty%7C}}%7C{{#invoke:Vorlage:Internetquelle%7CTitelFormat%7Ctitel={{#invoke:WLink%7CgetEscapedTitle%7C1=Theoretische Grundlagen der Informatik}}}}|[{{#invoke:URLutil|getNormalized|1=https://i11www.iti.kit.edu/_media/teaching/winter2011/tgi/tgi_skript_ws11.pdf}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{#invoke:WLink|getEscapedTitle|1=Theoretische Grundlagen der Informatik}}}}]}}{{#if:PDF; 874 kB| (PDF; 874 kB{{#if:Vorlaufiges Skript zur Vorlesung65{{#if: 2012-02-18 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}} 

          | )
          | {{#if:{{#ifeq:de|de||{{#if:|1}}}}| ; 
              | )}}}}}}{{#if:Vorlaufiges Skript zur Vorlesung| Vorlaufiges Skript zur Vorlesung{{#invoke:Vorlage:Internetquelle|Endpunkt|titel=Vorlaufiges Skript zur Vorlesung}}}}}}}}{{#if:https://i11www.iti.kit.edu/_media/teaching/winter2011/tgi/tgi_skript_ws11.pdf%7C{{#if:{{#invoke:URLutil%7CisResourceURL%7C1=https://i11www.iti.kit.edu/_media/teaching/winter2011/tgi/tgi_skript_ws11.pdf}}%7C%7C}}}}{{#if:Theoretische Grundlagen der Informatik|{{#if:{{#invoke:WLink|isValidLinktext|1=Theoretische Grundlagen der Informatik|lines=0}}||}}}}{{#if: | In: {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{{werk}}}}}}}{{#if: | {{{hrsg}}}{{#if: 65|,|{{#if: 2012-02-18 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: | {{#if:{{#invoke:DateTime|format||noerror=1}}
            |{{#invoke:DateTime|format||T._Monat JJJJ}}
            |{{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, datum=|class=Zitationswartung}} }}{{#if: 65|,|{{#if: 2012-02-18 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: 65| S. 65{{#if: |,|{{#if: 2012-02-18 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: {{#invoke:TemplUtl|faculty|}}| {{#if:65|{{#if:|archiviert|ehemals}}|{{#if:|Archiviert|Ehemals}}}} {{#if:|vom|im}} Vorlage:Referrer{{#if:{{#invoke:TemplUtl|faculty|}}| (nicht mehr online verfügbar)}}{{#if: | am {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}|{{{archiv-datum}}}{{#if:105763||(?)}}}}}}{{#if: 2012-02-18|;}}}}{{#if: 2012-02-18| {{#if:65{{#invoke:TemplUtl|faculty|}}|abgerufen|Abgerufen}} {{#switch: {{#invoke:Str|len| {{#invoke:DateTime|format| 2012-02-18 |ISO|noerror=1}} }}
       |4=im Jahr
       |7=im
       |10=am
       |#default={{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, abruf=2012-02-18|class=Zitationswartung}} }} {{#invoke:DateTime|format|2012-02-18|T._Monat JJJJ}}
    | {{#invoke:TemplUtl|failure|1=Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}} }}{{#if:{{#ifeq:de|de||{{#if:|1}}}}|{{#if:Vorlaufiges Skript zur Vorlesung65{{#if: 2012-02-18 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}
       |  (
       | {{#if:PDF; 874 kB | |  (}}
       }}{{#ifeq:{{#if:de|de|de}}|de||
          {{#invoke:Multilingual|format|{{{sprache}}}|slang=!|split=[%s,]+|shift=m|separator=, }}}}{{#if: |{{#ifeq:{{#if:de|de|de}}|de||, }}{{{kommentar}}}}})}}{{#if: 65{{#if: 2012-02-18 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}} }}|{{#if: |: {{
 #if: 
 | „{{
     #ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | Vorlage:Str trim
     | {{#invoke:Vorlage:lang|flat}}
     }}“
 | {{#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | „Vorlage:Str trim“
     | {{#invoke:Text|quote
         |1={{#if: 
              | {{#invoke:Vorlage:lang|flat}}
              | {{#invoke:Vorlage:lang|flat}} }}
         |2={{#if: {{#invoke:TemplUtl|faculty|}}|de-CH|de}}
         |3=1}} }}

}}{{#if: 

   |  (<templatestyles src="Person/styles.css" />{{#if:  | :  }}{{#if:  | , deutsch: „“ }})
   | {{#if: 
       |  ({{#if:  | , deutsch: „“ }})
       | {{#if:  |  (deutsch: „“) }}
 }}

}}{{#if: {{{zitat}}} 

   | {{#if: 
       | {{#if: {{{zitat}}}
           | Vorlage:": Text= und 1= gleichzeitig, bzw. Pipe zu viel }} }}
   | Vorlage:": Text= fehlt }}{{#if:  | {{#if: {{#invoke:Text|unstrip|{{{ref}}}}}
             | Vorlage:": Ungültiger Wert: ref=
             | {{{ref}}} }}

}}|.{{#if:{{#invoke:TemplUtl|faculty|}}|{{#if:||{{#ifeq: | JaKeinHinweis |{{#switch: 

   |0|=Vorlage:Toter Link/Core{{#if: https://i11www.iti.kit.edu/_media/teaching/winter2011/tgi/tgi_skript_ws11.pdf
       | {{#if:  | [1] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: https://i11www.iti.kit.edu/_media/teaching/winter2011/tgi/tgi_skript_ws11.pdf
      | {{#if:{{#invoke:URLutil|isWebURL|https://i11www.iti.kit.edu/_media/teaching/winter2011/tgi/tgi_skript_ws11.pdf}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://i11www.iti.kit.edu/_media/teaching/winter2011/tgi/tgi_skript_ws11.pdf Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: https://i11www.iti.kit.edu/_media/teaching/winter2011/tgi/tgi_skript_ws11.pdf
       | {{#if:{{#invoke:URLutil|isWebURL|https://i11www.iti.kit.edu/_media/teaching/winter2011/tgi/tgi_skript_ws11.pdf}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[https://i11www.iti.kit.edu/_media/teaching/winter2011/tgi/tgi_skript_ws11.pdf }}|{{#switch: 
   |0|=Vorlage:Toter Link/Core{{#if: https://i11www.iti.kit.edu/_media/teaching/winter2011/tgi/tgi_skript_ws11.pdf
       | {{#if:  | [2] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: https://i11www.iti.kit.edu/_media/teaching/winter2011/tgi/tgi_skript_ws11.pdf
      | {{#if:{{#invoke:URLutil|isWebURL|https://i11www.iti.kit.edu/_media/teaching/winter2011/tgi/tgi_skript_ws11.pdf}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://i11www.iti.kit.edu/_media/teaching/winter2011/tgi/tgi_skript_ws11.pdf Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: https://i11www.iti.kit.edu/_media/teaching/winter2011/tgi/tgi_skript_ws11.pdf
       | {{#if:{{#invoke:URLutil|isWebURL|https://i11www.iti.kit.edu/_media/teaching/winter2011/tgi/tgi_skript_ws11.pdf}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[https://i11www.iti.kit.edu/_media/teaching/winter2011/tgi/tgi_skript_ws11.pdf }} }}}}}}}}}}{{#if:|
        {{#invoke:Vorlage:Internetquelle|archivBot|stamp={{{archiv-bot}}}|text={{#if:|Vorlage:Webarchiv/archiv-bot}}

}}}}{{#invoke:TemplatePar|check |all= url= titel= |opt= autor= hrsg= format= sprache= titelerg= werk= seiten= datum= abruf= zugriff= abruf-verborgen= archiv-url= archiv-datum= archiv-bot= kommentar= zitat= AT= CH= offline= |cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Internetquelle}} |template= Vorlage:Internetquelle |format=0 |preview=1 }}</ref>

Eine Verallgemeinerung ist das Färbungsproblem. Bekannt ist auch eine als Landkartenfärbungsproblem bekannte Variante.

Einzelnachweise

<references/>

Abgerufen von „https://wiki-de.moshellshocker.dns64.de/index.php?title=Dreifarbenproblem&oldid=105763“