Standard- oder Top-Text zur angewandten Graphentheorie

8

Ich suche einen Referenztext zur angewandten Graphentheorie und zu Graphalgorithmen. Gibt es einen Standardtext, der in den meisten Informatikprogrammen verwendet wird? Wenn nicht, was sind die angesehensten Texte auf diesem Gebiet? Ich habe Cormen et al.

algorithms graph-theory reference-request education books JEHR
quelle
An welchen Bewerbungen interessieren Sie sich? Algorithmische Anwendungen?
A.Schulz
Ich interessiere mich für gerichtete Graphen, möchte aber einen endgültigen Text, falls es so etwas gibt. Ich dachte (hoffte), dass es einen speziellen Text geben könnte, der Theorie, Geschichte und Anwendungen abdeckt. Danke für die Antwort.
JEHR
3
Die Suche bei Amazon nach "angewandter Graphentheorie" liefert zahlreiche Ergebnisse. Ich schlage vor, Sie beginnen dort (oder eine ähnliche Suche an anderer Stelle), gehen in Ihre Bibliothek und suchen nach den vielversprechendsten Kandidaten. Kaufen Sie diejenige, die Sie am besten zugänglich finden. passend zu Ihren Bedürfnissen. Nicht jedes Buch hilft jedem, das ist eine sehr personenspezifische Angelegenheit.
Raphael
1
Ich habe Amazon durchsucht, bevor ich hier gefragt habe. Ich dachte, das wäre offensichtlich. Daher bin ich hierher gekommen, um zu sehen, ob es einen endgültigen Text für das Thema gibt, der in CS-Programmen weit verbreitet ist (siehe meine ursprüngliche Frage).
JEHR
1
Nach meiner Erfahrung gibt es kaum einen "endgültigen Text", insbesondere in der Informatik (einem jungen Bereich). Verschiedene Bücher sprechen unterschiedliche Zielgruppen und Vorlieben an, sowohl hinsichtlich der Auswahl der Inhalte als auch hinsichtlich der Präsentation.
Raphael

Antworten:

3

Insbesondere für Digraphen gibt es Band-Jensen & Gutins "Digraphen: Theorie, Algorithmen und Anwendungen" . Es deckt ziemlich viel Material ab.

Die erste Ausgabe kann jetzt kostenlos heruntergeladen werden, da die zweite Ausgabe erschienen ist (auf ihrer Seite befindet sich ein Link zum PDF). Wenn Sie Zugriff auf ein Springerlink-Konto haben, können Sie natürlich stattdessen die zweite Ausgabe erhalten!

Abgesehen davon, dass es frei ist, obwohl ich mir seiner Popularität nicht sicher bin (besonders wenn man bedenkt, dass es "relativ" jung ist), ist es ein gewichtiger Band, der eine umfassende Berichterstattung von Grundlagen bis zu ziemlich fortgeschrittenen Themen sowie aus praktischer und theoretischer Perspektive bietet.

Der andere Vorteil ist, dass es sich um einen der wenigen (vielleicht nur?) Vollständigen Texte handelt, die sich speziell mit Digraphen befassen, und nicht um ein allgemeines Buch zur Graphentheorie mit Material zu Digraphen.

Luke Mathieson
quelle
Vielen Dank! Kostenlos ist immer sehr gut. Sieht so aus, als würde es mein Hauptinteresse (gerichtete Grafiken) recht gut abdecken!
JEHR
3
Angesichts einer laufenden Diskussion über Meta möchte ich Sie ermutigen, zu versuchen, diese Antwort zu verbessern, indem Sie nachweisen, dass insbesondere dieser Text Ihre Empfehlung ist. Welche Beweise müssen Sie dafür liefern, dass es beliebt oder weit verbreitet ist? Welche Beweise haben Sie dafür, dass es respektiert wird? Beachten Sie, dass es noch keine Richtlinien für "Fragen auflisten" gibt, aber ich persönlich (nicht offiziell) bin gespannt, wie viel Rechtfertigung Menschen liefern können.
Patrick87
Luke, ich habe das von Ihnen vorgeschlagene Buch nur in begrenztem Umfang rezensiert und es ist das beste Buch über gerichtete Grafiken, das ich je gesehen habe. Mit mehr als 700 Seiten ist es ziemlich heftig. Wenn ich nur das Intro lese und mir die Themen ansehe, kann ich sagen, dass dies das ist, wonach ich gesucht habe - und es ist kostenlos !! In meiner Lernphase ist dies für meine Bedürfnisse hinreichend eindeutig. Ich werde ein Jahr brauchen, um das durchzuhalten. Danke für einen tollen Vorschlag.
JEHR
5

Ich würde mir das kostenlose Buch von Bondy und Murty ansehen: Graph Theory with Applications . Dieses Buch ist weniger algorithmisch und graphentheoretischer als andere hier empfohlene Ressourcen. Es gibt auch eine neuere Version des Buches , die nicht kostenlos im Internet verfügbar ist, aber sehr gut geschrieben und mit aktualisierter Notation. Im Vergleich zu anderen kostenlosen Büchern zur Graphentheorie (wie zum Beispiel Diestel ) verwendet Bondy / Murty einen weniger formalen Ansatz, um die Theorie zu beweisen und zu erklären.

Der Grund, warum ich es benutzt habe, ist, dass es das primäre Lehrbuch im Kurs über Graphentheorie an der Technischen Universität von Dänemark ist, der von Carsten Thomassen gehalten wird und in dem ich seit 2 Jahren Assistenzlehrer bin.

utdiscant
quelle
Wow, ein weiterer freier Text, der ziemlich gut aussieht! Danke für diesen tollen Vorschlag!
JEHR
2
Angesichts einer laufenden Diskussion über Meta möchte ich Sie ermutigen, zu versuchen, diese Antwort zu verbessern, indem Sie nachweisen, dass insbesondere dieser Text Ihre Empfehlung ist. Welche Beweise müssen Sie dafür liefern, dass es beliebt oder weit verbreitet ist? Welche Beweise haben Sie dafür, dass es respektiert wird? Beachten Sie, dass es noch keine Richtlinien für "Fragen auflisten" gibt, aber ich persönlich (nicht offiziell) bin gespannt, wie viel Rechtfertigung Menschen liefern können.
Patrick87
Ich habe meine Antwort mit einiger Begründung aktualisiert.
utdiscant
3

Es gibt immer die kostenlose algorithmische Graphentheorie, die Graphalgorithmen, Datenstrukturen, Durchquerungen und verschiedene andere Themen abdeckt. Wenn es nicht das hat, wonach Sie suchen, sind Sie zumindest nicht unterwegs.

Alt
quelle
Danke, davon habe ich noch nie gehört. Ich werde es meiner Bibliothek hinzufügen. Es scheint, dass es keinen endgültigen Text gibt, der weit verbreitet ist, daher ist dies möglicherweise ein guter Fund.
JEHR
Vielen Dank für diesen Hinweis. Dieses Buch war mir nicht bekannt. Es sieht sehr schön aus und hat viele Übungen! Und es ist kostenlos!
A.Schulz
1
Angesichts einer laufenden Diskussion über Meta möchte ich Sie ermutigen, zu versuchen, diese Antwort zu verbessern, indem Sie nachweisen, dass insbesondere dieser Text Ihre Empfehlung ist. Welche Beweise müssen Sie dafür liefern, dass es beliebt oder weit verbreitet ist? Welche Beweise haben Sie dafür, dass es respektiert wird? Beachten Sie, dass es noch keine Richtlinien für "Fragen auflisten" gibt, aber ich persönlich (nicht offiziell) bin gespannt, wie viel Rechtfertigung Menschen liefern können.
Patrick87
3

Schauen Sie sich die (nicht freie) Algorithmic Graph Theory von Alan Gibbons an. Es ist ein Oldie, aber in CS weit verbreitet. Es hat einen rechnerischen Ansatz, deckt aber auch die Theorie ab. Mit rund 250 Seiten ist es nicht zu einschüchternd und wird gut respektiert.

ncke
quelle
2
Angesichts einer laufenden Diskussion über Meta möchte ich Sie ermutigen, zu versuchen, diese Antwort zu verbessern, indem Sie nachweisen, dass insbesondere dieser Text Ihre Empfehlung ist. Welche Beweise müssen Sie dafür liefern, dass es beliebt oder weit verbreitet ist? Welche Beweise haben Sie dafür, dass es respektiert wird? Beachten Sie, dass es noch keine Richtlinien für "Fragen auflisten" gibt, aber ich persönlich (nicht offiziell) bin gespannt, wie viel Rechtfertigung Menschen liefern können.
Patrick87
2

Es gibt das Buch "Verwalten und Mining von Graphendaten" von Charu C. Aggarwal.

Es enthält (unter anderem):

  • Graph Mining: Gesetze und Generatoren
  • Graph Data Management und Mining
  • Diagrammindizierung
  • Abfragen zur Erreichbarkeit von Diagrammen
  • Graph Matching
  • Graphklassifizierung

Wie der Titel schon sagt, konzentriert er sich auf Diagrammdaten und Algorithmen für diesen Datentyp. Ich weiß nicht, ob Sie danach suchen, aber ich kann dieses Buch wirklich empfehlen:

Verwalten und Mining von Diagrammdaten

EDIT: Da in einem Kommentar nach "Beweisen" für die Relevanz meiner Antwort gefragt wurde, möchte ich auf Folgendes hinweisen:

  • Charu Aggarwal ist eines der Leitmotive im Bereich Data Mining ( Top 20 Autoren ).
  • Das Buch ist sehr gut geschrieben und auch mit wenig Vorkenntnissen leicht zu verstehen.
  • Es gibt eine Rezension dieses Buches von der ACM , in der eine Empfehlung zum Lesen des Buches angegeben ist.
  • Und schließlich: Ich mag es: D.

quelle
2
Angesichts einer laufenden Diskussion über Meta möchte ich Sie ermutigen, zu versuchen, diese Antwort zu verbessern, indem Sie nachweisen, dass insbesondere dieser Text Ihre Empfehlung ist. Welche Beweise müssen Sie dafür liefern, dass es beliebt oder weit verbreitet ist? Welche Beweise haben Sie dafür, dass es respektiert wird? Beachten Sie, dass es noch keine Richtlinien für "Fragen auflisten" gibt, aber ich persönlich (nicht offiziell) bin gespannt, wie viel Rechtfertigung Menschen liefern können.
Patrick87
Ich hoffe, ich konnte klarstellen, warum ich dieses Buch für relevant halte.