Matroids Matheplanet Forum Index
Moderiert von matroid
Kombinatorik & Graphentheorie » Graphentheorie » Strukturen von Graphen
Druckversion
Druckversion
Antworten
Antworten
Autor
Ausbildung Strukturen von Graphen
Mandelbrat1729
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 06.06.2020
Mitteilungen: 21
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-06-06


Hallo zusammen

Frage:
Gibt es eine Möglichkeit das Konzept eines Graphen auf seine Struktur zu reduzieren?
Daher: Kann man, wenn man über Graphen spricht auch direkt von deren Struktur sprechen und darüber Aussagen machen.

Meine Motivation dabei ist, dass ich mich frage, wieso ich überhaupt über Objekte sprechen und nachdenken sollte, welche ein Problem der Bezeichnung und Darstellung (isomorphieproblem) aufwerfen, wobei es ja um Welten einfacher wäre, einfach direkt über diskrete Strukturen zu sprechen....
Ich meine damit, dass das, was mich an einem Graphen wirklich interessiert - vielleicht einfach mich persönlich... - ja eigentlich seine Struktur ist und nicht seine Darstellung oder die Bezeichnung seiner Elemente.
Soviel zu meiner Meinung.



Falls jemand etwas zu/über diesem/dieses Thema weiss, wäre ich über eine Antwort sehr glücklich.

Gruss

Mandelbrat1729



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 5999
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-06-07


Hallo Mandelbrat1729,

2020-06-06 16:57 - Mandelbrat1729 im Themenstart schreibt:
Gibt es eine Möglichkeit das Konzept eines Graphen auf seine Struktur zu reduzieren?
Daher: Kann man, wenn man über Graphen spricht auch direkt von deren Struktur sprechen und darüber Aussagen machen.

Für einige einfach strukturierte Graphen kann man das wohl tun - indem man etwa \(K_n\) für den vollständigen Graphen mit n Ecken oder \(C_n\) für einen Kreis mit n Ecken oder \(K_{1,n}\) für einen Stern mit einem Mittelpunkt und n Enden schreibt. Die Ecken- und Kantenmenge sind hier a priori uninteressant.

Aber so wie es etwas komplizierter wird, ist das schwierig. Nimm mal wieder meinen Lieblingsgraphen, den Petersen-Graph P. Man könnte sagen, dass \(P=K_2(C_5,C_5)\) (mit zwei disjunkten Kreisen der Länge 5) und 5 weiteren disjunkten Kanten, die die beiden Kreise verbinden. (Zu \(K_2\) siehe deinen anderen Thread.) Damit ist aber noch nicht der Petersen-Graph definiert. Du kannst ja mal überlegen, wie viele nicht-isomorphe Graphen mit dieser Eigenschaft existieren. Du wirst also nicht drum herum kommen, den Ecken der beiden Kreise Namen zu geben.

Das gilt erst recht, wenn du irgend welche Aussagen über P beweisen möchtest, etwa dass die Kanten nicht mit drei Farben färbbar sind oder dass P nicht planar ist.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Mandelbrat1729
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 06.06.2020
Mitteilungen: 21
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-06-07


Hallo StrgAltEntf

Ja, so in etwa hab ich mir das schon gedacht...

Eine Kategorisierung von Graphen in bestimmte Typen, in dem Sinne, das eine Kategorie
dann nur genau eine Struktur definiert, ist wohl sehr schwer zu erreichen - wenn nicht gar unmöglich.
Aber ich kann mir einfach nicht vorstellen, dass man über etwas sprechen kann,
was prinzipiell nicht definierbar ist. Das erscheint doch absurd.

Was möglich wäre:
Wenigstens eine Kategorisierung nach bestimmten Merkmalen / Eigenschaften, sodass
bestimmte Strukturen voneinander getrennt werden und am Schluss nur noch Mengen
von Graphen übrig bleiben, in welchen man nach isomorphen Graphen suchen kann.
Wie in deinem Beispiel:
Man könnte Graphen nach der Anzahl ihrer Knoten Kategorisieren.
So könnten zwei Graphen aus unterschiedlichen Klassen dann nicht mehr Isomorph sein...
Fände man also einen Weg, dieses Spiel so weit zu treiben, dass dabei nur noch Klassen
isomorpher Graphen übrig bleiben, so wäre man am ziel.

Nur:
Man sieht am Beispiel gut, dass dies - wenn möglich - sehr schwer sein wird.
Denn selbst wenn das Ziel erreichen würde hätte man doch immer noch
unendlich mächtige Klassen von isomorphen Graphen.
Ich bin mit bei diesem Punkt leider nicht sicher, aber in meinen Augen
sollte es ja im Allgemeinen unendlich viele solche verschiedene isomorphe Graphen
geben, welche alle paarweise isomorph sind.


Ich selbst wollte es ursprünglich wie folgt angehen:
Sei I eine vollständige Isomorphieklasse von paarweise isomorphen Graphen.
"Vollständig" soll hier heissen, dass alle Graphen in I enthalten sind, welche zu einem beliebigen Graphen aus der Isomorphieklasse I isomorph ist.
Daher hätte man eine Klasse aller Repräsentanten einer Struktur.

Die Idee war nun, zu sagen: Wir haben also eine Eigenschaft, welche wir "Struktur" nennen,
und diese ist all diesen Graphen aus I gemeinsam. Das wäre dann eine indirekte Definition des
Begriffs. Man könnte also die Struktur so als Invariante definieren.
Das Problem dabei ist natürlich offensichtlich. Denn die Eigenschaft nach der wir suchen,
ist natürlich nicht die einzige Invariante oder gemeinsame Eigenschaft der Elemente dieser
Isomorphieklasse...
Nur als Beispiel: Offensichtlich haben ja alle Graphen aus I auch die gleiche Anzahl von Knoten.
Denn ansonsten könnte sie ja gar nicht paarweise Isomorph sein.
Soviel zu meinem vergeblichen Versuch...

Man müsste also einen Weg finden, alle anderen Eigenschaften, die allen Elementen aus
I gemeinsam sind auszuschliessen, Sodass nur noch die gesuchte Eigenschaft überbleibt.
Oder aber sich so auf die Eigenschaft der Struktur beziehen, dass alle anderen ausgeschlossen werden.

Das absurde dabei ist aber:
Selbst wenn einem dies gelingen würde, so könnte man mehr oder weniger immer noch
keine richtigen Aussagen über die Eigenschaft der Struktur machen, da man sie ja
nach wie vor nur auf einem indirekten Weg definiert hat.

Der Einfachheit halber könnte man aber Aussagen über den Begriff bzw. die Eigenschaft der "Struktur" einfach auf Aussagen über Isomorphieklassen reduzieren. Sozusagen als Konvention.
Ob das so aber einer genaueren logischen Untersuchung standhalten würde, bezweifle ich.


Gruss

Mandelbrat














Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 5999
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-06-07


2020-06-07 12:47 - Mandelbrat1729 in Beitrag No. 2 schreibt:
Aber ich kann mir einfach nicht vorstellen, dass man über etwas sprechen kann,
was prinzipiell nicht definierbar ist. Das erscheint doch absurd.

Verstehe ich nicht. Was ist denn hier nicht definierbar?

Ich verstehe auch dein grundsätzliches Problem nicht. Warum soll man nicht einen bestimmten Graphen aus einer Isomorphieklasse herausnehmen und diesen untersuchen? Die erlangten Erkenntnisse (*) gelten damit für alle zu ihm isomorphen Graphen.

(*) Hiermit meine ich graphentheoretische Erkenntnisse. Nicht so etwas wie "\(\pi\) ist eine Ecke des Graphen".



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Mandelbrat1729
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 06.06.2020
Mitteilungen: 21
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2020-06-07


Hallo StrgAltEntf

Ja die Erkenntnisse über einen Graphen sind natürlich auch gültig für die zu ihm
Isomorphen Graphen.
Nur weiss ich ja nicht wirklich welche das sind.
Ich muss halt immer erst zwei Graphen auf ihre Isomorphie prüfen um dann sagen zu können, dass Erkenntnisse über den einen auch für den anderen gelten. usw...

Mein Problem ist hier eigentlich, dass ich das Gefühl habe, es wäre viel einfacher, wenn ich direkt über die Dinge sprechen könnte, welche für mich wirklich relevant sind - daher in diesem Fall die Struktur eines Graphen - und nicht erst zeigen müsste, dass irgendwelche Erkenntnisse für bestimmte Graphen dann gelten sollen oder eben nicht gelten sollen. Das ganze erscheint mir so einfach zu umständlich.
Zudem gibt es ja unzählige paarweise Isomorphie Graphen. So müsste ich also, wenn ich eine (grössere) Menge von bspw. 100'000 Graphen als Grundlage habe, davon jedes Paar auf Isomorphie prüfen um dann zu zeigen welche dieser Graphen dieselben Eigenschaften haben.
Oder ich müsste für jeden Graphen einzeln die Eigenschaften aufzeigen und wüsste dabei nicht, wie oft ich dann für eigentlich isomorphe Graphen dieselben Eigenschaften zeige.
Nur schon vom Rechenaufwand her ist das ja absurd.


Ich verstehe dabei einfach nicht, wieso man nicht gleich von Anfang an über die Dinge spricht, welche am Schluss relevant sind.
Denn könnte ich Aussagen über einzelne Strukturen von Graphen machen, ohne mich dabei eines Graphen bedienen zu müssen, so könnte ich mir am Ende der Betrachtung einfach beliebig viele Graphen konstruieren / definieren die dann die gewünschten Eigenschaften besitzen.

Aber natürlich müsste ich genau so wie vorher bei einem gegebenen Graphen prüfen, ob er denn die gewünschte Struktur besitzt, so wie es dann halt vorgegeben wäre. usw.


Vielleicht habe ich ja die Thematik / das Konzept einfach noch nicht ganz durchschaut...



Gruss

Mandelbrat1729




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Mandelbrat1729 hat die Antworten auf ihre/seine Frage gesehen.
Mandelbrat1729 wird per Mail über neue Antworten informiert.
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]