Matroids Matheplanet Forum Index
Moderiert von matroid
Kombinatorik & Graphentheorie » Graphentheorie » Färbungsinvariante
Autor
Universität/Hochschule Färbungsinvariante
Rosebrock
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 13.03.2009
Mitteilungen: 6
Wohnort: Karlsruhe, Deutschland
  Themenstart: 2009-03-13

Liebe Leute,    ich habe mir eine Färbungsinvariante für Graphen überlegt und wüsste gerne, ob es das schon irgendwo gibt. Ich vermute schon, es ist eine nahe liegende Konstruktion, aber ich weiß nicht, wo gucken. Also: Sei G =(V,K) ein Graph mit Eckenmenge V und nicht leerer Kantenmenge K. Sei A eine Teilmenge der Eckenmenge V. Wir stellen uns die Ecken von A gefärbt vor und die anderen Ecken V - A als ungefärbt. Sei dA die Teilmenge der Kanten, die jeweils einen gefärbten und einen ungefärbten Randpunkt haben. Wir definieren für endliche Graphen: h(G,A)= |dA| / |K| Diese Zahl liegt immer zwischen 0 und 1, weil dA eine Teilmenge von K ist. Wegen h(G,V)=0 bekommt man immer die 0 hin, wir wollen aber fragen, wann ist h(G,A) maximal? Wir definieren also:     t(G)= max h(G,A) über alle Teilmengen A von V. Ist G ein unendlicher Graph, ersetze Maximum durch Supremum und mache eine limes-Konstruktion über beschränkte Teilgraphen. t ist eine Grapheninvariante. Es gilt: Satz: Für den Graph G gilt t(G)=1 genau dann, wenn G bipartit ist. Beweis: Wir beginnen mit einem bipartiten Graphen. Bipartit heißt, dass sich die Eckenmenge V in zwei Teilmengen V_1 und V_2 zerlegen lässt, so dass jede Kante eine Ecke aus V_1 mit einer Ecke aus V_2 verbindet. Färbe V_1. Umgekehrt definiere die gefärbten Ecken als die Menge V_1 und erhalte so eine Zerlegung der Eckenmenge und damit einen bipartiten Graphen. q.e.d. Die t-Invariante misst also, wie weit ein Graph davon weg ist, bipartit zu sein. Je größer t desto 'bipartiter' ist der Graph. Wir benötigen im Weiteren das folgende Lemma, welches sich sehr leicht elementar beweisen lässt: Lemma: Sind a,b,c,d natürliche Zahlen, so gilt: Aus a/b > 1/2 und c/d >= 1/2 folgt (a+c)/(b+d)>=1/2 Satz: Für beliebige endliche Graphen G gilt t(G)>1/2. Beweis: Wir brauchen den Satz nur für zusammenhängende Graphen beweisen, denn wenn er für alle zusammenhängenden wahr ist, dann ist er nach obigem Lemma für alle wahr. Wir machen Induktion über die Anzahl der Ecken. Der kleinste zusammenhänge Graph mit nicht-leerer Kantenmenge besteht aus einer Kante und seinen beiden Randecken. Färbe genau eine der beiden Ecken und erhalte so t = 1. Angenommen, alle zusammenhängenden Graphen G mit höchstens n Ecken erfüllen t(G)>1/2. Sei G=(V,K) jetzt ein zusammenhängender Graph mit genau n+1 Ecken. Entferne eine Ecke v, so dass der Restgraph zusammenhängend bleibt, mit allen angrenzenden Kanten e_1,....,e_k und erhalte so den Graph G'. Färbe G' nach Induktion, so dass t(G')>1/2. Es gibt also eine Menge A' von Ecken von G', die gefärbt sind, so dass (1)   |dA'| / (|K|-k)>1/2 Das induziert eine Färbung für G bis auf die Ecke v. Sei v_i die Bezeichnung der zweiten Ecke der Kante e_i für alle i. Betrachte die Farben der Ecken v_1,....,v_k. Färbe genau dann die Ecke v, wenn mehr als die Hälfte der Ecken v_1,....,v_k ungefärbt ist. Das gibt uns insgesamt eine Färbung A von G. dA unterscheidet sich von dA' um mindestens k/2, d.h. (2)    |dA| - |dA'| >= k/2 Aus den Ungeichungen (1) und (2) folgt mit obigem Lemma: |dA| / |K| > 1/2 und also h(G,A)>1/2. Die Behauptung folgt aus t(G)>= h(G,A). q.e.d. Fragen: Meine Hauptfrage ist: Gibt es das schon? Wo kann ich was darüber nachlesen? Der Beweis vom obigen Satz gibt uns ein Verfahren, mit dem man eine Menge A von zu färbenden Ecken findet, für die h(G,A) recht groß ist. Gilt immer t(G)=h(G,A) für die mit dem Verfahren gefundene Menge A? Gibt es eine bessere Abschätzung für planare Graphen? Oder solche, mit relativ wenigen Kanten im Verhältnis zur Anzahl Ecken bei zusammenhängenden Graphen? Gibt es für jede rationale Zahl 1/2


   Profil
valentin
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.03.2005
Mitteilungen: 1478
Wohnort: Berlin
  Beitrag No.1, eingetragen 2009-03-13

Hallo, das Problem t(G) zu berechnen ist äquivalent zum MAX CUT Problem in Graphen, denn es gilt MAXCUT(G)=t(G)*|K|. Dieses ist leider NP-Schwer. Zu deinen weiteren Fragen findest du eventuell was in der Literatur zu besagtem Problem. -- Valentin


   Profil
valentin
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.03.2005
Mitteilungen: 1478
Wohnort: Berlin
  Beitrag No.2, eingetragen 2009-03-13

Noch mal einen Nachtrag: Das Verfahren zum heuristischen Finden von A, welches du beschreibst, sieht mir nach dem Greedy Verfahren aus. Es ist bekannt, dass ein Greedy-Cut immer mindestens die Hälfte aller Kanten enthält, somit MAXCUT(G) >= |K|/2 bzw t(G) >= 1/2. Dies entspricht der Aussage deines Lemmas. -- Valentin


   Profil
Rosebrock
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 13.03.2009
Mitteilungen: 6
Wohnort: Karlsruhe, Deutschland
  Beitrag No.3, vom Themenstarter, eingetragen 2009-03-13

Hallo Valentin,    vielen Dank, das war genau, was ich suchte. Grüße Stephan


   Profil
Rosebrock
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 13.03.2009
Mitteilungen: 6
Wohnort: Karlsruhe, Deutschland
  Beitrag No.4, vom Themenstarter, eingetragen 2009-03-13

Hallo Leute,    ich habe doch noch eine Frage dazu: Die MAX CUT Geschichte scheint darauf zu zielen, so einen maximal cut zu finden, also mehr die algorithmische Seite. Es scheint aber weniger damit zu tun zu haben, dass das ja eigentlich eine Grapheninvariante ist (jedenfalls t(G)). Das finde ich das spannende daran. Also: Zu welchen Werten q zwischen 0 und 1 gibt es einen Graphen G mit t(G)=q und ähnliche Fragen. Gibt es dazu was? Grüße Stephan


   Profil
valentin
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.03.2005
Mitteilungen: 1478
Wohnort: Berlin
  Beitrag No.5, eingetragen 2009-03-13

Hallo, was bedeutet für dich der Begriff Grapheninvariante? Sicherlich ist t() eine eindeutig definierte Funktion von der Menge der endlichen Graphen in die rationalen Zahlen. Aber wenn man von Invarianten redet, meint man doch meist eine Invariante bezüglich irgendeiner Operation oder Klassifikation. Zu deiner Frage: Ich denke man wird zu allen rationalen .5 <= q <= 1 einen Graphen konstruieren können. Ich muss darüber aber noch mal nachdenken. -- Valentin [ Nachricht wurde editiert von valentin am 13.03.2009 17:54:15 ]


   Profil
Rosebrock
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 13.03.2009
Mitteilungen: 6
Wohnort: Karlsruhe, Deutschland
  Beitrag No.6, vom Themenstarter, eingetragen 2009-03-13

Hallo Valentin,    ja, ich meine schon Invariante bezüglich Graphenisomorphismus. Man kann mit t() möglicherweise manchmal nachweisen, dass zwei Graphen nicht isomorph sind. Dazu wäre es natürlich nett, man hätte zwei verschiedene zusammenhängende Graphen mit unterschiedlichem t, aber selber Ecken- und Kantenzahl. Vermutlich kriegt man sowas hin. Grüße Stephan


   Profil
valentin
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.03.2005
Mitteilungen: 1478
Wohnort: Berlin
  Beitrag No.7, eingetragen 2009-03-13

Klar bekommst du so etwas hin, doch was bringt dies? Die Berechnung von t ist sowohl praktisch betrachtet als auch unter gängigen komplexitätstheoretischen Annahmen schwieriger als das Isomorphismusproblem direkt zu entscheiden. Und ein gleiches t bedeutet ja noch lange nicht, dass beide Graphen isomorph sind. -- Valentin


   Profil
Rosebrock
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 13.03.2009
Mitteilungen: 6
Wohnort: Karlsruhe, Deutschland
  Beitrag No.8, vom Themenstarter, eingetragen 2009-03-13

Naja, selbst wenn die Berechnung erstmal nicht leicht ist, ist jede Invariante immer erstmal interessant. Vielleicht kann man ja irgendwelche allgemeinen Sätze dazu zeigen, die einem dann was bringen. Das ist ja erstmal offen. Mit dem was ich im Moment weiß, bringt sie natürlich noch nichts. Übrigens: Die Berechnung von t für vollständige Graphen ist nicht schwer: Anzahl Ecken n: n ungerade: t=(n+1)/2n n gerade: t=n/(2n-2) Stephan


   Profil
Rosebrock hat die Antworten auf ihre/seine Frage gesehen.
Rosebrock wird per Mail über neue Antworten informiert.

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-2021 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]