Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Introduction Kapitel lesen Erstes Kapitel lesen

2018 | OriginalPaper | Buchkapitel

2. Graphs

verfasst von : Bernhard Korte, Jens Vygen

Erschienen in: Combinatorial Optimization

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Graphs are a fundamental combinatorial structure used throughout this book. In this chapter we not only review the standard definitions and notation, but also prove some basic theorems and mention some fundamental algorithms.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Introduction
Nächstes Kapitel Linear Programming
Literatur
Berge, C. [1985]: Graphs. Second Edition. Elsevier, Amsterdam 1985
Bollobás, B. [1998]: Modern Graph Theory. Springer, New York 1998
Bondy, J.A. [1995]: Basic graph theory: paths and circuits. In: Handbook of Combinatorics; Vol. 1 (R.L. Graham, M. Grötschel, L. Lovász, eds.), Elsevier, Amsterdam 1995
Bondy, J.A., and Murty, U.S.R. [2008]: Graph Theory. Springer, New York 2008
Diestel, R. [2010]: Graph Theory. Fourth Edition. Springer, New York 2010
Wilson, R.J. [2010]: Introduction to Graph Theory. Fifth Edition. Addison-Wesley, Reading 2010
Aoshima, K., and Iri, M. [1977]: Comments on F. Hadlock’s paper: finding a maximum cut of a planar graph in polynomial time. SIAM Journal on Computing 6 (1977), 86–87
Camion, P. [1959]: Chemins et circuits hamiltoniens des graphes complets. Comptes Rendus Hebdomadaires des Séances de l’Académie des Sciences (Paris) 249 (1959), 2151–2152
Camion, P. [1968]: Modulaires unimodulaires. Journal of Combinatorial Theory A 4 (1968), 301–362
Dirac, G.A. [1952]: Some theorems on abstract graphs. Proceedings of the London Mathematical Society 2 (1952), 69–81
Edmonds, J., and Giles, R. [1977]: A min-max relation for submodular functions on graphs. In: Studies in Integer Programming; Annals of Discrete Mathematics 1 (P.L. Hammer, E.L. Johnson, B.H. Korte, G.L. Nemhauser, eds.), North-Holland, Amsterdam 1977, pp. 185–204
Euler, L. [1736]: Solutio problematis ad geometriam situs pertinentis. Commentarii Academiae Petropolitanae 8 (1736), 128–140
Euler, L. [1758]: Demonstratio nonnullarum insignium proprietatum quibus solida hedris planis inclusa sunt praedita. Novi Commentarii Academiae Petropolitanae 4 (1758), 140–160
Hierholzer, C. [1873]: Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren. Mathematische Annalen 6 (1873), 30–32
Hopcroft, J.E., and Tarjan, R.E. [1974]: Efficient planarity testing. Journal of the ACM 21 (1974), 549–568
Kahn, A.B. [1962]: Topological sorting of large networks. Communications of the ACM 5 (1962), 558–562
Karzanov, A.V. [1970]: An efficient algorithm for finding all the bi-components of a graph. In: Trudy 3-ĭ Zimneĭ Shkoly po Matematicheskomu Programmirovaniyu i Smezhnym Voprosam (Drogobych, 1970), Issue 2, Moscow Institute for Construction Engineering (MISI) Press, Moscow, 1970, pp. 343–347 [in Russian]
Knuth, D.E. [1968]: The Art of Computer Programming; Vol. 1. Fundamental Algorithms. Addison-Wesley, Reading 1968 (third edition: 1997)
König, D. [1916]: Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. Mathematische Annalen 77 (1916), 453–465
König, D. [1936]: Theorie der endlichen und unendlichen Graphen. Teubner, Leipzig 1936; reprint: Chelsea Publishing Co., New York 1950
Kuratowski, K. [1930]: Sur le problème des courbes gauches en topologie. Fundamenta Mathematicae 15 (1930), 271–283
Legendre, A.M. [1794]: Éléments de Géométrie. Firmin Didot, Paris 1794
Minty, G.J. [1960]: Monotone networks. Proceedings of the Royal Society of London A 257 (1960), 194–212
Moore, E.F. [1959]: The shortest path through a maze. Proceedings of the International Symposium on the Theory of Switching; Part II. Harvard University Press 1959, pp. 285–292
Rédei, L. [1934]: Ein kombinatorischer Satz. Acta Litt. Szeged 7 (1934), 39–43
Robbins, H.E. [1939]: A theorem on graphs with an application to a problem of traffic control. American Mathematical Monthly 46 (1939), 281–283
Robertson, N., and Seymour, P.D. [1986]: Graph minors II: algorithmic aspects of tree-width. Journal of Algorithms 7 (1986), 309–322
Robertson, N., and Seymour, P.D. [2004]: Graph minors XX: Wagner’s conjecture. Journal of Combinatorial Theory B 92 (2004), 325–357
Tarjan, R.E. [1972]: Depth first search and linear graph algorithms. SIAM Journal on Computing 1 (1972), 146–160
Thomassen, C. [1980]: Planarity and duality of finite and infinite graphs. Journal of Combinatorial Theory B 29 (1980), 244–271
Thomassen, C. [1981]: Kuratowski’s theorem. Journal of Graph Theory 5 (1981), 225–241
Tutte, W.T. [1961]: A theory of 3-connected graphs. Proceedings of the Koninklijke Nederlandse Akademie van Wetenschappen A 64 (1961), 441–455
Wagner, K. [1937]: Über eine Eigenschaft der ebenen Komplexe. Mathematische Annalen 114 (1937), 570–590
Whitney, H. [1932]: Non-separable and planar graphs. Transactions of the American Mathematical Society 34 (1932), 339–362
Whitney, H. [1933]: Planar graphs. Fundamenta Mathematicae 21 (1933), 73–84
Metadaten
Titel
Graphs
verfasst von
Bernhard Korte
Jens Vygen
Copyright-Jahr
2018
Verlag
Springer Berlin Heidelberg
Buch
Combinatorial Optimization

Print ISBN: 978-3-662-56038-9

Electronic ISBN: 978-3-662-56039-6

Copyright-Jahr: 2018

DOI
https://doi.org/10.1007/978-3-662-56039-6_2