Was sind Graphen in Laienbegriffen?

18

Was sind Graphen in der Informatik und wofür werden sie verwendet? Für Laien am liebsten.

Ich habe die Definition auf Wikipedia gelesen :

In der Informatik ist ein Graph ein abstrakter Datentyp, der die graphischen und hypergraphischen Konzepte der Mathematik implementieren soll.

Eine Graphendatenstruktur besteht aus einer endlichen (und möglicherweise veränderlichen) Menge geordneter Paare, Kanten oder Bögen genannt, bestimmter Entitäten, Knoten oder Scheitelpunkte genannt. Wie in der Mathematik heißt es, eine Kante (x, y) zeige oder gehe von x nach y. Die Knoten können Teil der Graphstruktur sein oder können externe Entitäten sein, die durch ganzzahlige Indizes oder Referenzen dargestellt werden.

aber ich suche eine weniger formale, leichter zu verstehende Definition.

ConditionRacer
quelle
Meinen Sie Grafiken der Datenstruktur?
System Down
1
Ja Entschuldigung. Grafiken wie hier beschrieben ( en.wikipedia.org/wiki/Graph_(abstract_data_type) , nur suche ich eine weniger formale, leichter verständliche Definition.
ConditionRacer
@ Justin984 Wikipedia-Links mit Klammern (und es gibt so viele von ihnen) funktionieren nicht, die Klammern passen nicht zum Markdown-Format für Links. Zum späteren Nachschlagen fügen Sie bitte Ihrer Frage in der Frage selbst Erläuterungen hinzu, nicht in Kommentaren. Sie sind nicht so sichtbar und können leicht übersehen werden. Ich werde Ihren obigen Kommentar in der Frage bearbeiten ...
Yannis
@ Justin984 Beachten Sie auch, dass Computer Science Stack Exchange für Fragen wie diese möglicherweise besser geeignet ist als für Programmierer. Verstehen Sie mich nicht falsch, die Frage ist hier genau richtig und hat großartige Antworten erhalten, aber es würde nicht schaden, wenn Sie eine Community auschecken würden, die sich ein bisschen mehr auf grundlegende Informatikkonzepte konzentriert als wir (nicht) Die gleiche Frage auf mehreren Websites posten. Wenn Sie sie auf der falschen Website veröffentlichen, können wir sie automatisch auf die richtige verschieben.
Yannis

Antworten:

26

Ein perfektes Beispiel für Laien könnte Facebook sein . Das Netzwerk von Ihnen, Ihren Freunden und ihren Freunden usw. wird gemeinsam als sozialer Graph bezeichnet .

In diesem "Graphen" werden die Personen als Knoten des Graphen betrachtet und die Kanten sind Freundschaftsverbindungen .

Bei Facebook ist friend eine bidirektionale Beziehung (A ist B's Friend => B ist A's Friend), daher ist das Diagramm ein ungerichtetes Diagramm . Ein Netzwerk wie Google+ oder Twitter würde als gerichteter Graph angesehen, da die Richtung der Beziehung hier eine Bedeutung hat.

Alle diese Graphen werden als zyklische Graphen bezeichnet, da die Beziehungen zwischen Knoten Zyklen bilden können. Ein Stammbaum , auf der anderen Seite, ist eine besondere Art von Graphen, die unter anderem ist Azyklisches da es nicht Zyklen im Stammbaum relatioship sein kann. (Es wird technisch als Directed Acyclic Graph (DAG) bezeichnet, da es sowohl gerichtet als auch azyklisch ist.)

Dies sollte den gesamten grundlegenden Jargon abdecken, der Diagramme umfasst, sodass Sie nun in der Lage sein sollten, den Rest des Materials auf dem Feld zu verfolgen.

Karthik T
quelle
1
Ich kann nicht glauben, dass mir nicht aufgefallen ist, dass es die Facebook-Grafik-API heißt. Gutes Beispiel!
ConditionRacer
4
Stammbaum nicht zyklisch? Es sollte nicht sein, aber es ist leider ...
Marjan Venema
1
@MarjanVenema, der Stammbaum ist zyklisch ? (Es ist ein gerichteter Graph, daher ist die Richtung wichtig, um die Zyklen zu bestimmen, und vermutlich zählen Stufenbeziehungen nicht wirklich.)
Donnerstag,
@dbaupp: Ich möchte hier nicht auf Details eingehen, deshalb erwähne ich nur ein Wort: Inzest.
Marjan Venema
5
@ MarjanVenema, du vermisst meinen Standpunkt. Ein Zyklus in einem gerichteten Graphen ist ein Muster wie A -> B -> C -> A(dh ein Kreis von Pfeilen), Inzest gibt nur A -> B -> Cund A -> D -> C(dh ein Diamant). Ein Zyklus in einem Stammbaum braucht eine Zeitreise.
Huon
16

Graphen sind eines der wichtigsten mathematischen Konzepte der Informatik.

Sie haben viele Male Grafiken gesehen. Stellen Sie sich vor, Sie fliegen mit dem Flugzeug von einer Stadt in eine andere. In der Sitztasche vor Ihnen befindet sich zwangsläufig ein schönes Hochglanzmagazin der Fluggesellschaft. Nahe der Rückseite dieses Magazins finden Sie fast immer eine Karte, auf der die von dieser Fluggesellschaft bedienten Städte als Kreise dargestellt sind, wobei die Flüge, die diese Städte verbinden, als gekrümmte Linien dargestellt sind. Das ist eine Grafik! Die Städte, die als Kreise dargestellt sind, sind die Knoten dieses Diagramms, und die Flüge, die als gekrümmte Linien dargestellt sind, sind die Kanten. Graphen sind nur Dinge mit Knoten und Kanten, die Knoten verbinden.

Sie können diese einfachen Diagramme auf verschiedene Arten verschönern. Sie möchten nicht nur ein paar Kreise und Linien sehen, wenn Sie sich diese Karte ansehen. Diese Städte haben Namen. Das Beschriften dieser Städte führt zu einem beschrifteten Diagramm. (Sie können auch die Kanten beschriften, z. B. Flug 1234.) Die Informatik ordnet den Knoten häufig Daten zu, manchmal auch den Kanten. Dies ist jedoch nur eine Erweiterung der Beschriftung. Es ist immer noch eine beschriftete Grafik. Eine weitere Verschönerung ergibt sich, wenn Sie direkt von Stadt A nach Stadt B fliegen können, jedoch nicht von Stadt B nach Stadt A. Eine naheliegende Möglichkeit, dies darzustellen, besteht darin, einen Pfeil auf die Linie zu setzen, die die Städte verbindet, um diese Einbahnstraßenbeziehung darzustellen. Jetzt haben Sie einen gerichteten Graphen.

Verknüpfte Listen, Bäume, Zustandsübergangsdiagramme und viele andere Informatikdatenstrukturen sind Beispiele für Diagramme. Es ist ein sehr mächtiges Konzept.

David Hammen
quelle
Ich würde dieses Beispiel sogar erweitern, um festzustellen, dass alle in Ihrem Beispiel beschriebenen Entitäten als Scheitelpunkte in einem Diagramm dargestellt werden können (Stadt, Ebene, Magazin, Karte usw.), wobei die Karte selbst nur ein einzelner Scheitelpunkt ist.
Demian Brecht
14

Eine bessere Frage wäre "Wofür werden keine Grafiken verwendet?". Informatik ist in vielerlei Hinsicht das Studium von Graphen.

Ein Graph ist für Laien eine Sammlung beliebiger abstrakter Objekte, die als "Knoten" oder "Eckpunkte" bezeichnet werden und Verbindungspunkte darstellen. Sie werden dann über "Pfade" oder "Kanten" verbunden. Der abstrakte Datentyp "Graph" ist eine Implementierung des mathematischen "Graph". Im Grunde haben Sie Knoten und Kanten als Felder und verschiedene Operationen, die Sie an ihnen ausführen können. Sie können beispielsweise der Diagrammsammlung einen neuen Knoten hinzufügen (dies kann je nach Sprache eine Liste oder ein Array oder eine andere Struktur sein). Sie können diesen Knoten dann mit vorhandenen Knoten verknüpfen. Zu den Vorgängen gehören auch das Durchlaufen des Diagramms, das Überprüfen, ob zwei Knoten eine Kante gemeinsam haben (verbunden sind), das Abrufen von Werten von Knoten oder Kanten und das Löschen von Knoten oder Kanten aus dem Diagramm.

Bei der Verwendung werden Grafiken überall verwendet. Networking nutzt sie besonders stark, findet sich jedoch in den Bereichen Künstliche Intelligenz, Data Mining, Spieleentwicklung, Geoinformatik und vielen anderen Disziplinen. In der formalen Informatik sehen sie noch mehr Nutzen, nämlich als Repräsentationsform des Staates.

Tatsächlich kann alles, was Sie als Satz von Verbindungen darstellen können, als Diagramm dargestellt und über dieses ADT in irgendeiner Form implementiert werden.

Hier ist eine Beispielgrafik, die ich erstellt habe:

Diagramm Beispiel

Weltingenieur
quelle
3

Ein Graph ist nur eine Sammlung von Objekten, die durch Linien, sogenannte Vertices, miteinander verbunden sind.

Der Begriff "Graph" ist eine Abstraktion und Verallgemeinerung vieler Datenstrukturen, die in der Softwareentwicklung verwendet werden. Verknüpfte Listen, Binärbäume und ASTs sind alle Diagramme.

Grundsätzlich ist jede Sammlung von Objekten mit Zeigern, die die Objekte miteinander verknüpfen, ein Diagramm. Sobald Sie einen Graphen haben, können Sie die Prinzipien der Graphentheorie anwenden , um bestimmte Probleme zu lösen .

Robert Harvey
quelle