weitere Rubriken
PhilosophieTräumeOrteEsoterikLiteraturHelpdeskAstronomieGruppenSpieleGamingFilmeMusikClashVerbesserungenAllmysteryWillkommenEnglishGelöscht
Diskussions-Übersichten
BesuchtTeilgenommenAlleNeueGeschlossenLesenswertSchlüsselwörter
Schiebe oft benutzte Tabs in die Navigationsleiste (zurücksetzen).

Turan Graph

19 Beiträge, Schlüsselwörter: Mathematik, Knoten, Kanten, Turan, Graphentheorie
Seite 1 von 1

Turan Graph

17.06.2017 um 13:09
Hallo,

bei dem Link https://oeis.org/A033437 geht es um Turan Graphen.
Wikipedia: Satz_von_Tur

Da ich diese Zahlen gerne verstehen möchte, frage ich einfach mal in die Runde:

Ist es möglich, dass mir ein User diese Zahlen aus OEIS visuell klar machen kann?

Ich verbleibe dankend!


melden
Anzeige

Turan Graph

18.06.2017 um 01:54
Erst einmal kurz zu den Grundbegriffen, sofern Du Dir diese nicht schon selbst angeeignet hast:

Mit "Knoten" werden die Punkte in solchen Strukturen bezeichnet, mit "Kanten" die Linien, die die Knoten/Punkte verbinden. Formal ausgedrückt sind die Knoten Elemente der Menge V ('vertices') und die Kanten Elemente der Menge E ('edges'), die zusammen den Graphen bilden (also ein Tupel (V,E)).

So, der Satz von Turán besagt nun, dass ein Graph unter der Bedingung, dass alle n Knoten nicht durch Kanten Dreiecke bilden können, eine maximale Anzahl an Kanten enthält (sprich dadurch nach oben beschränkt wird), nämlich [n^4/4], wobei die eckige Klammer bedeutet, dass nach unten abgerundet wird. Man verzeih mir diese unsaubere Schreibweise, aber der mir bekannte Formeleditor kennt keine Abrundungsfunktion.

Betrachte dazu die Grafik auf der entsprechenden Wikipedia-Seite:

SatzVonTuran ViererGraphen.PNG

Alle drei Graphen besitzen n = 4 Knoten, allerdings 5 bzw. 6 Kanten. Setzen wir den Wert nun in die obige Formel ein, erhalten wir

e5f8

D.h. ein Graph mit 4 Knoten dürfte höchstens 4 Kanten haben, damit es möglich ist, eine solche Struktur ohne Dreieck zu zeichnen.
Beim ersten Graphen ist schnell zu sehen, dass kein Dreieck existiert, wenn man die Kante in der Mitte entfernt. Beim zweiten existiert aber bspw. immer noch ein Dreieck, nachdem man eine der Kanten in der Mitte entfernt hat. Dies widerspricht jedoch der Aussage des Satzes nicht, da diese lediglich eine obere Schranke ('höchstens') angibt, andernfalls würde man "genau dann, wenn ..." als Formulierung verwenden. Mit anderen Worten: Es war möglich, einen dreiecklosen Graphen zu konstruieren, der (höchstens) 4 Kanten besitzt, wie man am ersten sehen konnte.

Abschließend zu deinem Link: https://oeis.org/A033437
Diese Zahlenfolge enthält in aufsteigender Ordnung die besagten, aus der obigen Formel generierten Werte, die die obere Schranke (d.h. maximale Anzahl an Kanten) bildet.
Dazu kurz als Beispiel:
Die ersten zwei Werte sind 0, was logisch ist, da n=0 -> [0^2/4] = 0 sowie n=1 -> [1^2/4] = 0 ergibt. Selbiges gilt für n = 2 -> 1; dies ist alles ebenfalls der Wikiseite zu entnehmen. Abweichungen gibt es dann allerdings schon ab n=3. Ich kann mir vorstellen, dass dies daran liegt, dass der Graph auf oeis.org 5-partitiv ist, dies dagegen in dem Wikipediabeispiel nicht näher definiert ist. Da ich persönlich nur einige Grundlagen der Graphentheorie kenne, müsste ich mich da selbst einarbeiten, wofür mir leider die Zeit fehlt. Ich hoffe aber, dass ich Dir trotzdem helfen konnte, da das Konzept an sich klar ist.
Um das ganze visuell darzustellen, empfiehlt sich wohl, ein Programm zu schreiben. In Verbindung mit dem Studium des mathematischen Beweises sollte sich ein klareres Verständnis ergeben.

Warum interessiert dich das eigentlich?


melden

Turan Graph

18.06.2017 um 04:42
@Mr.Dextar

Ganz lieben Dank für deine Zeit und Mühe!
Ja...soweit war ich auch schon. Richtig begreifen tue ich es aber nicht.

Jenes habe ich mir auch angeschaut, verstehe hier aber nicht ganz recht, was die Zahlen in den Klammern bedeuten sollen.
Habe versucht so auf die Zahlen aus OEIS zu kommen.
Turan

Warum interessiert mich das? Ich ziehe das Pferd gerne von hinten auf, oder wie es Gauß sagen würde:
"Das Ergebnis habe ich schon, jetzt brauche ich nur noch den Weg, der zu ihm führt." (Gauß)

Ich weiss, wie man die Zahlen aus OEIS extrem schnell generiert, weiss aber nicht so recht, was sie bedeuten und noch weniger, ob dies evtl. klar ist, ob man sie so schnell generieren kann!

Ich verbleibe dankend.


melden

Turan Graph

18.06.2017 um 10:14
Radix schrieb:Ich weiss, wie man die Zahlen aus OEIS extrem schnell generiert, weiss aber nicht so recht, was sie bedeuten und noch weniger, ob dies evtl. klar ist, ob man sie so schnell generieren kann!
Naja, wenn man sich mal die Formel zur Berechnung der Anzahl der Kanten anschaut, wird's eigentlich schnell klar...

e5fe

Da steckt praktisch null Rechenaufwand dahinter.
Mr.Dextar schrieb:Man verzeih mir diese unsaubere Schreibweise, aber der mir bekannte Formeleditor kennt keine Abrundungsfunktion.
Ich nehm' da immer den hier:
https://www.zahlen-kern.de/editor/index.php

Bei den Buttons findet sich zwar keine Gaußklammer, aber in LaTeX geht's mit \lfloor bzw. \rfloor. Und die Befehle funzen auch im obigen Editor. ;)


melden

Turan Graph

18.06.2017 um 10:37
Radix schrieb:weiss aber nicht so recht, was sie bedeuten
Was ein Graph ist, sollte zunächst klar sein (da hatte Mr. Dextar ja schon was geschrieben). Jetzt stellt sich die Frage, was genau denn nun ein Turán-Graph ist.

Dazu ein Beispiel: Sagen wir mal, unser Graph soll zunächst genau 13 Ecken haben. Bei deiner Zahlenfolge geht es um 5-partite Turán-Graphen. Aber nehmen wir mal die 4-partiten Turán-Graphen (hierzu findest du ebenfalls eine entsprechende Zahlenfolge).
Radix schrieb:Jenes habe ich mir auch angeschaut, verstehe hier aber nicht ganz recht, was die Zahlen in den Klammern bedeuten sollen.
In meinem Beispiel wäre hier die Notation: T(13,4). Also ein 4-partiter Turán-Graph mit 13 Ecken. Ein Turán-Graph zeichnet sich nun vor allem dadurch aus, dass man die Ecken auf k möglichst gleichgroße Mengen verteilt. In diesem Beispiel also auf 4 möglichst gleichgroße Mengen. Betrachte dazu die Ecken in diesem Bild:

470px-Turan 13-4.svg

13 Ecken auf 4 möglichst gleichgroße Mengen verteilt (da 13 nicht durch 4 teilbar ist, sind sie natürlich nicht exakt gleichgroß).

Eine weitere Bedingung an Turán-Graphen ist die Folgende: Zwei Ecken sollen genau dann durch eine Kante verbunden werden, wenn sie nicht innerhalb der gleichen Menge liegen (siehe Grafik). So sind also insbesondere die Ecken innerhalb der 'nördlich', 'östlich', 'südlich', 'westlich' liegenden Mengen nicht miteinander verbunden.

Und nun stellt sich die Frage, wie viele Kanten so ein Graph genau hat. Für 4-partite Turán-Graphen lässt sich dafür ebenfalls eine einfache Formel angeben:

e5fo

Fix noch die Anzahl der Ecken, also 13, eingesetzt, ergibt:

e5fr

PS: Die von dir verlinkte Grafik von Wolfram ist da für's Verständnis leider nicht sehr hilfreich... Hatte mich anfangs auch etwas verwirrt.


melden

Turan Graph

18.06.2017 um 11:52
@Noumenon


Ok. Visuell habe ich das kapiert. Verstehe zwar noch nicht wie Du auf die Nenner kommst, wo kommt die 8 her?
Welche Formel brauche ich für "t(n,5)"?

Ansonsten super erklärt, soweit habe ich es verstanden und meine Frage ist eigtl. erklärt.

Ganz lieben Dank.


melden

Turan Graph

18.06.2017 um 13:37
@Radix
Hier findest du bspw. die allg. Formel:
http://mathworld.wolfram.com/TuranGraph.html

Also:

e5hc

Daraus ergeben sich dann die obigen Formeln für k=4 bzw. k=5.


melden

Turan Graph

18.06.2017 um 14:04
Danke! @Noumenon. Alles begriffen. :-D


melden

Turan Graph

18.06.2017 um 21:20
Interessante Diskussion!

Etwas OT:

Pál Turán war ungarischer Jude und hat seinen berühmten Satz über Graphen und auch anderes zum Thema Graphen (etwa das Problem der Backstein-Fabrik) entwickelt als er im Arbeitslager war während des zweiten Weltkrieges. Einer der deutschen Bewacher hatte vor dem Krieg was mit Mathe zu tun und seinen Namen erkannt und ihn dann "protegiert", sonst hätte er das Lager vielleicht nicht überlebt.


melden

Turan Graph

18.06.2017 um 21:43
@wolfi7777
Finde ich gar nicht so OT. Aber auch nur weil ich es als Laie interessanter finde, als diese Feststellung was Dreiecke haben kann und wie man es ausrechnet ^^

Aber auch hier möchte ich gerne mal blöd fragen, wo diese Sache Anwendung findet?


melden

Turan Graph

18.06.2017 um 23:20
Skagerak schrieb:Aber auch hier möchte ich gerne mal blöd fragen, wo diese Sache Anwendung findet?
Hier ein Beispiel...
http://www.cs.unc.edu/~snoeyink/comp145/cogs.pdf


melden

Turan Graph

19.06.2017 um 00:52
@wolfi7777

OT ist das nicht wirklich, ist wohl eher "kontextuales" Lernen, wenn man das so nennen darf.
Wie haben die Protagonisten gelebt, wie sind sie auf die Idee gekommen usw...ich lese auch gerne die Biographien.

@Skagerak

Wikipedia: Graphentheorie

--> Anwendung

gleichwohl das behandelte hier -glaube ich- Extremale Graphentheorie ist.


melden

Turan Graph

19.06.2017 um 01:01
Achso, meine Rechnung ist für die 5er Gruppen schneller!

Knoten mal zwei und ins Quadrat gehoben, die Einer tilgen!
k=Knoten

(k2)²

Was genau deshalb geht, weil 5*2 (der Nenner) 10 ist.


melden

Turan Graph

19.06.2017 um 02:24
@Radix
Und statt der Multiplikation mit 2 kannste du ja auch noch die Bits einfach um eine Position nach links schieben. Ist auch noch einmal einen Tick schneller. ;)

Wikipedia: Bitweiser_Operator#Bitweise_Verschiebungen


melden

Turan Graph

19.06.2017 um 22:09
Ich hätte noch eine Frage. Der Turan Graph ist ja 2Dimensional, oder?
Wenn ich mir nun aber einen Graph in die dritte Dimension vorstelle,
wäre das:

t(n,k)= ((k-1)n³)/k2

bzw. in der x ten Dimension, wäre der Exponent x, das wäre richtig?


melden

Turan Graph

20.06.2017 um 06:36
Mal eine ganz andere Frage: Wozu braucht man sowas? :-)


melden

Turan Graph

20.06.2017 um 09:55
Radix schrieb:Wenn ich mir nun aber einen Graph in die dritte Dimension vorstelle
Sowas gibt es nicht...


melden

Turan Graph

20.06.2017 um 10:03
Du denkst vllt. an sowas hier:

cube1

Sieht zwar wie ein 3-dim. Würfel aus, aber letztendlich ist die Darstellung immer noch 2-dim. (ist ja auch eine 2-dim. Grafik!). Und die Ecken kann man auch einfach verschieben, das juckt den Graphen herzlich wenig:

cube2

Ein Graph besteht aus Ecken und Kanten. Ob die Ecken dabei 2-dim. oder 3-dim. Punkte repräsentieren, ist egal...


melden
Anzeige

Turan Graph

20.06.2017 um 11:42
@Noumenon

Den LaTex-Editor benutze ich selbst, allerdings wusste ich nicht, dass er auch regulären, dort nicht eingetragenen LaTex-Code erkennen kann. Cool, danke für den Hinweis! :) Und schön, dass Du hier die Fragen soweit auch beantworten konntest.

@McMurdo
McMurdo schrieb:Mal eine ganz andere Frage: Wozu braucht man sowas?
Bioinformatik und Pathfinding-Algorithmen, um mal wichtige Anwendungsbereiche der Graphentheorie zu nennen.


melden

Neuen Beitrag verfassen
Dies ist eine Vorschau, benutze die Buttons am Ende der Seite um deinen Beitrag abzusenden.
Bereits Mitglied?  
Schriftgröße:
Größe:
Dateien Hochladen
Vorschau
Bild oder Datei hochladen

Bleib auf dem Laufenden und erhalte neue Beiträge in dieser Diskussion per E-Mail.


Oder lad dir die Allmystery App um in Echtzeit zu neuen Beiträgen benachrichtigt zu werden:

Ähnliche Diskussionen

239 Mitglieder anwesend
Konto erstellen
Allmystery Newsletter
Alle zwei Wochen
die beliebtesten
Diskussionen per E-Mail.

Themenverwandt
Anzeigen ausblenden