Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Knotentheorie und Knotenfärbung (Knoteninvariante)
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> Knotentheorie und Knotenfärbung (Knoteninvariante)
 
Autor Nachricht
Leo
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 08.12.2004
Beiträge: 4

BeitragVerfasst am: 08 Dez 2004 - 13:14:09    Titel: Knotentheorie und Knotenfärbung (Knoteninvariante)

Guten Tag!!!
Weiss jemand etwas über die Knotentheorie und speziel über die Knotenfärbung (Knoteninvariante)? Brache dringend Hilfe!!!!! Laughing


Zuletzt bearbeitet von Leo am 08 Dez 2004 - 14:17:42, insgesamt einmal bearbeitet
Faulus
Gast






BeitragVerfasst am: 08 Dez 2004 - 13:22:59    Titel:

kleiner Tip: Wäre n1, wenn deine genaue Frage auch mit im Thread stehen würde .p

Eine Knotenfärbung eines Graphen G=(V,E) mit k Farben ist
eine Abbildung c: V -> [k] , so dass gilt:
c(u) != c(v) für alle Kanten {u,v} ε E. ( != bedeutet ungleich)

Die minimale Anzahl der benötigten Farben ist die
chromatische Zahl: x(G)

cu...
Leo
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 08.12.2004
Beiträge: 4

BeitragVerfasst am: 08 Dez 2004 - 14:20:50    Titel:

Könnten Sie das auch für "normale sterbliche" erklären? Denn ich verstehe von der Theorie net viel, muss aber ein Programm schreiben, dass die Anzahl der möglichen Färbungen ausrechnet (ausgehend aus der Koordinaten des Knotens)...
Faulus
Gast






BeitragVerfasst am: 08 Dez 2004 - 16:38:13    Titel:

wie, die anzahl der möglichen Färbungen???

bei unendlich vielen farben, gibt es auch unendlich viele möglichkeiten .p
Faulus
Gast






BeitragVerfasst am: 08 Dez 2004 - 17:01:22    Titel:

Wenn du einen Algorithmus suchst, der mit der minimalen Anzahl an Färbungen auskommt, dann sieht es schlecht aus.

Aber wenn C(G) die Anzahl an Farben fuer den Graphen G ist, dann gilt:

X(G) < C(G) < max_deg(v) + 1 , v ε V
( V ist die Menge an Knoten, E die Menge an Kanten
X(G) ist die chromatische Zahl, fuer die es glaube ich keinen Algorithmus gibt
max_deg(v) ist der Grad des Knotens, mit der höchsten Anzahl an Kanten

Ein Algorithmus fuer die Färbung: Greedy-Färbung
hier ein C.Source: http://home.in.tum.de/~velev/projects/dop/blatt06/greedy_faerbung.C.html

ansonsten mal selber googlen...

cu..
Leo
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 08.12.2004
Beiträge: 4

BeitragVerfasst am: 08 Dez 2004 - 18:26:36    Titel:

In diesem Script steht, dass es nur 14 Farben genutzt werden dürfen. Ich muss den Knoten aber nur mit 3 füllen... Soweit ich weiss hat z.B. ein Trefoil 6 Färbungen. Ich verstehe einfach nicht, wieso... Denn an einer Kreuzung dürfen alle 3 oder eine Farbe benutzt werden. Und der ganze Knoten darf nicht in einer Farbe gefärbt sein. Wocher kommen die 6 Varianten beim Trefoil kann ich überhaupt nicht verstehen.
Faulus
Gast






BeitragVerfasst am: 08 Dez 2004 - 19:05:30    Titel:

sorry, da kann ich dir nicht helfen...

1. ich weiss nicht was ein Trefoil ist ^^
2. ich denke, ein Knoten darf eh nur mit einer Farbe gefärbt sein
(wir meinen wohl was verschiedenes)

sorry, cu...
Gast







BeitragVerfasst am: 08 Dez 2004 - 21:17:53    Titel:

OK. Danke!
Leo
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 08.12.2004
Beiträge: 4

BeitragVerfasst am: 08 Dez 2004 - 21:19:03    Titel:

Anonymous hat folgendes geschrieben:
OK. Danke!


p.s.: das kommt von mir... Very Happy
Anni03
Gast






BeitragVerfasst am: 08 Dez 2004 - 21:27:14    Titel:

Wenn ich mich nicht irre, redet hier einer über Knotentheorie und der andere über Knotenfärbungen in der Graphentheorie. Ne, ne.
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> Knotentheorie und Knotenfärbung (Knoteninvariante)
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum