Matroids Matheplanet Forum Index
Moderiert von matroid
Kombinatorik & Graphentheorie » Graphentheorie » Kann man effizient zeigen, dass ein k-konstruierbarer Graph existiert/ nicht existiert?
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Kann man effizient zeigen, dass ein k-konstruierbarer Graph existiert/ nicht existiert?
Pter87
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.11.2018
Mitteilungen: 202
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-05-24


Ich habe hier im dem Buch Graphentheorie von Reinhard Diestel folgenden Satz von Hajós:

Für \(k \in \mathbb{N}\) und einen Graphen \(G\) gilt genau dann \(\chi(G) \geq k\), wenn \(G\) einen k-konstruierbaren Teilgraphen hat.

Falls nicht klar ist, was k-konstruierbare Graphen sein sollen, hier ist eine Erklärung:

So, jetzt ist es ja meistens so, dass man immer eine Färbung hat(im schlimmsten Fall die Triviale). Man könnte jetzt eigentlich ganz einfach durch wiederholtes anwenden des Satzes mit immer kleiner werdendem k, die chromatische Zahl berechnen. Wenn der Graph keine k-konstruierbaren Teilgraphen hat, dann probiert man es einfach mit der nächstkleineren Zahl k-1, bis man auf eine Zahl p stößt, für die der Graph einen k-konstruierbaren Graphen hat. p ist ja dann die chromatische Zahl.

Kann man sowas denn effizient realisieren ?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Ixx
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.04.2020
Mitteilungen: 169
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-05-24


Aus dem Grund, den du beschreibst, würde aus der effizienten (d.h. in Polynomialzeit) Überprüfung, ob ein Graph einen k-konstruierbaren Teilgraphen besitzt, ein Polynomialzeit-Algorithmus für das bekanntermaßen NP-vollständige Problem der Bestimmung der chromatischen Zahl folgen.

Also dürfte die Antwort wohl lauten, dass es keinen solchen effizienten Algo für dein gestelltes Problem gibt.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Pter87 hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]