Metraipolis › archive › dc_118ecb313b31

Graphentheorie — Wikipedia (de)

Source
Wikipedia (de)
Original
https://de.wikipedia.org/wiki/Graphentheorie
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-06T10:14:52.882Z
SHA-256 of the archived text
fc1963ad3bde5a84810c8ddb41588f46a922312bac6f0259c0080e02d24efc66
Stable URL of this page
https://metraipolis.com/documento/dc_118ecb313b31

How to cite

Graphentheorie — Wikipedia (de) — Wikipedia (de), https://de.wikipedia.org/wiki/Graphentheorie (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_118ecb313b31 (Metraipolis archive dc_118ecb313b31, sha256 fc1963ad3bde5a84810c8ddb41588f46a922312bac6f0259c0080e02d24efc66)
BibTeX
@misc{dc118ecb313b31,
  title = {Graphentheorie — Wikipedia (de)},
  howpublished = {Wikipedia (de)},
  url = {https://de.wikipedia.org/wiki/Graphentheorie},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_118ecb313b31; sha256 fc1963ad3bde5a84810c8ddb41588f46a922312bac6f0259c0080e02d24efc66},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (de), https://de.wikipedia.org/wiki/Graphentheorie. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Die Graphentheorie (seltener auch Grafentheorie) ist ein Teilgebiet der diskreten Mathematik und der theoretischen Informatik. Betrachtungsgegenstand der Graphentheorie sind Graphen (Mengen von Knoten und Kanten), deren Eigenschaften und ihre Beziehungen zueinander. Graphen sind mathematische Modelle für netzartige Strukturen in Natur und Technik (wie soziale Strukturen, Straßennetze, Verwandtschaftsbeziehungen, Computernetze, elektrische Schaltungen, Versorgungsnetze oder Moleküle). In der Graphentheorie untersucht man lediglich die abstrakte Netzstruktur an sich. Die Art, Lage und Beschaffenheit der Knoten und Kanten bleibt unberücksichtigt. Es verbleiben jedoch viele allgemeingültige Graphen-Eigenschaften, die bereits auf dieser Abstraktionsstufe untersucht werden können und sich in allgemeingültigen Aussagen (Sätze der Graphentheorie) wiederfinden. Ein Beispiel hierfür ist das Handschlaglemma, wonach die Summe der Knotengrade in einem Graphen stets gerade ist (in der nebenstehenden Abbildung: 14). Dadurch, dass einerseits viele algorithmische Probleme auf Graphen zurückgeführt werden können und andererseits die Lösung graphentheoretischer Probleme oft auf Algorithmen basiert, ist die Graphentheorie auch in der Informatik, insbesondere der Komplexitätstheorie, von großer Bedeutung. Insbesondere lassen sich viele Aufgaben der kombinatorischen Optimierung in der Sprache der Graphentheorie formulieren und umgekehrt graphentheoretische Probleme als lineare ganzzahlige Optimierungsprobleme modellieren. Die Untersuchung von Graphen ist auch Inhalt der Netzwerktheorie. Graphen werden insbesondere durch die Datenstrukturen Adjazenzmatrix, Inzidenzmatrix oder Adjazenzliste repräsentiert.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «Graphentheorie»).
Fonte: Wikipedia in tedesco, voce «Graphentheorie» — https://de.wikipedia.org/wiki/Graphentheorie
Wikidata Q131476 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q131476
Autori: i contributori di Wikipedia (cronologia: https://de.wikipedia.org/wiki/Graphentheorie?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 259816468, consultata il 2026-10-06T09:45:24.154Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 3debe79563ff5a06db72dd2a72f06fdf0a3889c2d3671fc1b7ce8ad0df55d30f