Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Kombinatorik & Graphentheorie » Welche Relationen/Verknüpfungen können mit Graphen dargestellt werden
Druckversion
Druckversion
Antworten
Antworten
Autor
Ausbildung Welche Relationen/Verknüpfungen können mit Graphen dargestellt werden
Mandelbrat1729
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 06.06.2020
Mitteilungen: 30
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-06-06


Guten Tag

Ich stehe vor dem Problem, dass ich keine exakten Angaben im Netz oder in Büchern gefunden habe, welche mir beantworten, welche Relationen und / oder Verknüpfungen ich mit Graphen überhaupt darstellen kann und welche nicht.
Wenn mir jemand eine exakte Beschreibung derjenigen Relationen / Verknüpfungen angeben könnte, welche durch Graphen beschreibbar sind, wäre ich sehr dankbar.


...
Wieso zum beispiel, kann ich einen Term t wie "x+3*y" nicht als Graphen darstellen.
Ich gehe davon aus, dass das daran liegt, dass dieser Term aus Funktionssymbolen aufgebaut ist.
Diese sind - soweit ich weiss - nicht als Graphen darstellbar.
Jedoch:
Ich könnte doch einfach das Funktionssymbol "+(x,y)" durch folgende Relation ersetzen:
R := " __ ist Argument des gleichen Funktionssymbols wie __".
R wäre dann im allgemeinen Fall eine n-stellige Relation.
Somit wäre dann aber der Term t wieder als Graph darstellbar, was ein Widerspruch ist.

Die Überlegung dabei ist, dass die Struktur des Terms auch nach der Ersetzung erhalten bleibt.
Daher, dass die Struktur des Terms t bei der oben genannten Transformation eine Invariante ist.
So könnte man auch sagen:
Wäre der Term t durch einen Graphen beschreibbar, so wäre dieser Graph isomorph zum durch die Transformation konstruierten Graphen.

usw...


Für Antworten zur Anfangs gestellten Frage und Meinungen zum unten genannten Problem
wäre ich sehr dankbar.



Freundliche Grüsse

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: 6033
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-06-06


Hallo Mandelbrat1729,

2020-06-06 11:19 - Mandelbrat1729 im Themenstart schreibt:
Wieso zum beispiel, kann ich einen Term t wie "x+3*y" nicht als Graphen darstellen.

Weil das ein Term und keine Relation ist. Aber du könntest etwa die Relation x+3*y = 7 als Grundlage für einen Graphen wählen. Zunächst musst du dir überlegen, was für Werte für x und y zulässig sein sollen. Das wäre dann die Eckenmenge. Nimm etwa die ganzen Zahlen. Dann könntest du den (unendlichen gerichteten) Graphen G= (V, E) definieren mit
\[V=\IZ,E=\{(x,y):x+3y=7\}\]
Mehrstellige Relationen, etwa x+3y-z=7 ergeben hier erst einmal keinen Sinn, da eine Kante immer nur zwei Ecken verbindet. Allerdings gibt es auch das Konstrukt des Hypergraphen.



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: 30
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-06-06


Hallo StrgAltEntf

Danke für den Tipp.
Das klingt schon einmal interessant.

Wie sieht es nun aber mit der Darstellbarkeit aus?
Sind denn einfach prinzipiell alle Relationen als Graph darstellbar?
(Was ich bezweifle.)

Und zu meiner Frage:
Ja es ist ein Term. Aber falls ich den Term durch Relationen ersetze,
so könnte ich doch Möglichkeiten finden ihn indirekt als Graph darzustellen?
Oder bin ich da auf dem Holzweg?

Motivation:
Strukturen von bspw. Termen analysieren...
Geht evt. auch in Richtung Algebra. (?)


Danke für die Hilfe.


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: 6033
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-06-06


2020-06-06 17:46 - Mandelbrat1729 in Beitrag No. 2 schreibt:
Wie sieht es nun aber mit der Darstellbarkeit aus?
Sind denn einfach prinzipiell alle Relationen als Graph darstellbar?
(Was ich bezweifle.)

Ja, warum nicht? Wenn R eine (zweistellige) Relation auf einer Menge X ist, dann ist G = (X, R) ein (gerichteter) Graph.

Oder was meinst du mit Darstellbarkeit?



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: 30
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2020-06-06


Hallo StrgAltEntf

Ja im Prinzip meine ich das mit Darstellbarkeit.
Bzw.: Darstellbar im Sinne von: Eine (beliebige) Relation kann als Graph ohne Widersprüche definiert werden. Der Graph unterscheidet sich im weiteren nur durch spezielle Eigenschaften wie bspw. isolierte Knoten, Mehrfachkanten, Gewichtungen oder Färbungen usw. ( von den Relationen).

Ich hätte zu diesem Prinzip noch eine andere Frage:
Wenn man das allgemeinste Konzept zugrunde legt, das ich persönlich in diesem Zusammenhang kenne, und das ist ein Hypergraph, so müsste man doch leicht zeigen können (mir erscheint es trivial), dass mit Hypergraphen prinzipiell jede mögliche Kombination von Relationen zwischen Knotenmengen formulierbar / darstellbar / definierbar ist.
Daher:
Falls es eine (unendlich mächtige) Menge gäbe, die alle möglichen diskreten Strukturen enthält (oder irgendwelche "Repräsentanten" von Ihnen), so wäre prinzipiell jede dieser Strukturen durch mindestens einen Hypergraphen konstruierbar.
Bzw. Müsste man vielleicht sagen, dass immer ein Hypergraph konstruierter ist, der zu einer solchen Struktur isomorph ist.

Damit meine ich in etwa: Eine allgemeine Theorie von Hypergraphen wäre insofern "strukturell vollständig", dass man in ihr jede beliebige denkbare Struktur konstruieren könnte.

Es geht mir darum:
Wenn ich eine beliebige diskrete Struktur beschreiben / modellieren wollte, so wüsste ich - falls obige Aussage korrekt ist - das ich dies mit einem Hypergraphen prinzipiell immer machen könnte.
Ist das korrekt so?


Vielen Dank für deine Hilfe und Geduld (!).


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: 6033
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2020-06-06


2020-06-06 18:42 - Mandelbrat1729 in Beitrag No. 4 schreibt:
Wenn man das allgemeinste Konzept zugrunde legt, das ich persönlich in diesem Zusammenhang kenne, und das ist ein Hypergraph, so müsste man doch leicht zeigen können (mir erscheint es trivial), dass mit Hypergraphen prinzipiell jede mögliche Kombination von Relationen zwischen Knotenmengen formulierbar / darstellbar / definierbar ist.
Daher:
Falls es eine (unendlich mächtige) Menge gäbe, die alle möglichen diskreten Strukturen enthält (oder irgendwelche "Repräsentanten" von Ihnen), so wäre prinzipiell jede dieser Strukturen durch mindestens einen Hypergraphen konstruierbar.

Hallo Mandelbrat1729,

in der Mathematik gilt: Triviale Sachverhalte brauchen nicht weiter begründet zu werden, es reicht ein "das ist trivial". Jedoch sollte man in der Lage sein, für eine Trivialität einen Beweis aus dem Ärmel zu schütteln. Wenn das nicht so ist, so ist es eben nicht trivial. Wobei das natürlich sehr stark von der Person abhängt, die sagt oder schreibt "das ist trivial".

Zu deinem Problem: Hier ist erst einmal eine saubere Definition von "Kombination von Relationen" erforderlich und was es heißt, dass eine Kombination von Relationen mit einem Hypergraphen darstellbar ist.

Weiterhin: Was verstehst du unter einer Struktur, und was heißt es, dass eine Struktur durch einen Hypergraphen konstruierbar 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: 30
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2020-06-06


Hallo StrgAltEntf

1. Zum Begriff "Struktur".
Ich verstehe den Begriff der Struktur eines Graphen indirekt über die Isomorphie.
Soll heissen: Wenn man einen Graphen durch einen Isomorphismus Transformiert, so ist das bzw. etwas, was dem Ausgangsgraphen und dem Transformierten Graphen gemeinsam ist (i.d.r. die/eine Invariante) das was ich unter der Struktur (eines Graphen) verstehe.
Man sagt ja auch ismorphe Graphen seien "strukturgleich".
Daher versuche ich unter diesem Begriff das zu verstehen, was eben bei zwei Isomorphen Graphen gleich ist.
In einem anderen Beitrag stelle ich auch die Frage nach einer unabhängigen Definition von diesem Begriff, da mir ausser der oben genannten keine bekannt ist.

Ich weiss, das ist ein wenig behelfsmässig aber mir ist im Moment leider noch nichts besseres eingefallen.
Ich beziehe mich dabei einfach auf die Vermutung/Behauptung, dass, wenn zwei Objekte Strukturgleich sein können (daher Isomorph), so müssen sie doch auch eine Eigenschaft besitzen die man Struktur nennen kann. Ansonsten könnte diese Eigenschaft ja nicht bei zwei Objekten gleich sein. Diese Eigenschaft will ich dann selbstverständlich als Struktur bezeichnen.
Ich gehe dabei aber davon aus, dass man prinzipiell nicht nur über diesen Begriff sprechen kann, wenn man zwei Graphen vergleicht, sondern auch dann, wenn man einzelne Graphen betrachtet - wie oben beschrieben.
Es tut mir aber leid, dass ich dir keine unabhängige Definition bieten kann.


Ich hoffe so ist es wenigstens halbwegs klar.

2. "was heisst es, dass eine Struktur durch einen Hypergraphen konstruierbar ist..."
Ich meine damit folgendes:
Wenn man davon ausgeht, dass ein Strukturbegriff (oder Konzept) "unabhängig" vom Konzept des Graphen existiert, so kann man ja später auch unabhängige aussagen darüber treffen.
Ich verfolge dabei folgende Vorstellung.

Ein Graph hat eine Struktur. Man könnte auch sagen er stellt eine dar oder ist "Repräsentant" einer Struktur.
Jedoch gibt es bekanntlich mehrer Graphen, die die gleiche Struktur darstellen - ansonsten gäbe es ja keine Isomorphie.
Es gibt also jeweils zu (jeder)/einer Struktur eine Klasse von Graphen welche diese Struktur besitzen bzw. Repräsentieren. Damit meine ich, alle Graphen dieser Klasse sind jeweils paarweise isomorph. Damit ist mindestens eine Eigenschaft, die diesen Graphen allen gemeinsam ist (daher eine Invariante), das, was ich mit "die Struktur des Graphen G" bezeichne. Eine solche oben beschrieben Klasse von paarweisen Isomorphen Graphen soll Isomorphieklasse heissen. Ist sie "vollständig", so enthält sie alle möglichen Graphen einer bestimmten Struktur.

Ich versuche also das Konzept der Struktur vom Konzept des Graphen loszulösen...

"Konstruierbar" soll in diesem Zusammenhang nun genauer heissen, dass bei gegebener (unabhängiger) Struktur S ein (Hyper-)Graph konstruiert werden kann, welcher genau diese Struktur "Repräsentiert".

Daher:
Wäre eine beliebige Menge von (im obigen Sinne) Strukturen \(S_n\) gegeben, so könnte man zu jeder solchen Struktur einen Graphen finden / konstruieren, der genau diese Struktur repräsentiert und damit selbst als Eigenschaft besitzt.

Es macht vermutlich wenig Sinn (!) dann von einer "Gleichheit der Struktur des Graphen mit der Struktur der Struktur" zu sprechen!

Man könnte aber vielleicht sagen, dass eine Struktur "als Eigenschaft vorliegt".
Daher könnte man sagen: Gesucht ist ein Graph G mit (beliebiger) Struktur S.
Satz 1: "G existiert". oder: "G ist konstruierbar".

Das wäre die eigentliche Aussage auf die ich hinaus will.


Im Prinzip wäre der Beweis wie folgt trivial:
Beschränken wir uns auf endliche Graphen.

So kann ich prinzipiell einen Graphen \(G = (V,E)\) mit beliebig vielen Konten definieren, solange es endlich viele sind (nach obiger Einschränkung).

Machen wir ein Beispiel für zweistellige Kanten:
Ich kann prinzipiell jede beliebige zweielementige Teilmenge von V als Kante definieren ohne auf einen Widerspruch zu stossen.
Sodann kann ich dies auch sooft ich will wiederhohlen.
Anschaulich: Ich kann zwischen zwei beliebigen Knoten des Graphen G immer Kanten zeichnen und zwar immer beliebig viele, solange es endlich viele sind.

Daher müsste ich "nach Adam Ries" jede Beliebige Kombination Kanten (und damit Relationen (!) -> Frage) in beliebigen Knotenmenge realisieren können.

Somit wäre, wenn man diesem Konstruktionsprinzip folgt sicher auch jede Struktur in diesem Sinne definierbar / konstruierbar.
Umgekehrt gilt offensichtlich das gleiche.


Die Argumentation kann wohl problemlos auch auf beliebige endliche Hypergraphen erweitert werden, man muss dazu nur die Mächtigkeit der betrachteten Teilmengen der Knotenmengen anpassen und evt. noch ein paar fälle mehr betrachten.
Doch das Argument sollte auch im allgemeinen Fall anwendbar sein.


Ich hoffe damit deine Frage geklärt zu haben und entschuldige mich
für meine etwas engstirnige und eigensinnige Begrifflichkeit.




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]