Epidemiologische Distanz

Wiki2Reveal

Kurs enthält Wiki2Reveal-Folien

Dieser Wiki2Reveal Foliensatz wurde für den Lerneinheit Kurs:Räumliche Modellbildung' erstellt der Link für die Wiki2Reveal-Folien wurde mit dem Wiki2Reveal-Linkgenerator erstellt.

Einleitung

Wenn wir die zeitliche Entwicklung betrachten, mit der sich eine ansteckende Krankheit räumlich ausbreitet, dann ist das Bewegungsverhalten der Individuen eine entscheidende Größe für die Verbreitung. Wenn es schnelle Flugverbindungen zwischen zwei Orten A und B gibt und viele Personen sich auf dieser Flugverbindung bewegen, dann liegen diese Ort ggf. geographisch weit auseinander, aber epidemiologisch sind die Orte benachbart.

Räumliche Interaktion und Begegnung

Die Mobilität ist eine Dimension, in der man die Verbreitung betrachtet. Die Konnektivität der Menschen untereinander ist eine weitere. Ein einfaches Beispiel zeigt diese Aspekte. Wenn alle Personen, die mobil sind, sich allein in einer Fahrgastzelle und keine Kontakte mit anderen Menschen haben, kann die Mobilität nicht zur Ansteckung führen. Die Kontakte zu anderen Personen ermöglichen erst eine Ansteckung. Bei hoher Mobilität kann der Virus nur größere Distanzen schneller überwinden.

Wegenetze

Wegenetze beschreiben die Verbindung zwischen Punkten im Raum. Diese können auch als Image-Map webbasiert zugänglich gemacht werden. Ein Klick auf eine Bildelement folgt einer Verbindung zwischen einer Webseite zu einer anderen Webseite (Links sind ungewichtete gerichtete Verbindungen zwischen Webseiten. So gesehen erzeugt man mit Links ein digitales Wegenetz.

Digitales Wegenetze

Wegenetze digital abbilden.

Kapazität von Wegen

Wege zwischen zwei Punkten können eine unterschiedliche Breite haben und die Bewegung mit unterschiedlicher Geschwindigkeit ermöglichen. Betrachten Sie in der folgenden Abbildung gerichtet Wege auf den Treppen. Haben beide Wegrichtung die gleiche Kapazität (Trepper herauf, Treppe herab)? Wie kann man die Kapazität der Wege messen und sinnvoll einer Verbindung zuordnen?

Abbildung zur Kapazität von Wegen

Kapazität von Wegen im Wegenetz.

Konnektivitätsnetze Personen

Die Konnektivität zwischen Personen und Peronengruppen kann auch durch Graphen beschrieben werden. Die gewichtete Verbindung zwischne den Personen beschreibt die Intensität der Verbindung. Das Gewicht 0 zwischen einer Verbindung repräsentiert, dass die Personen nicht verbunden sind (d.h. sie begegnen sich nicht). Diese Konnektivität von Personen entspricht nicht der räumlichen Distanz. Zwei Personen, die jeweils in getrennten direkt benachbarten Büros sitzen und sich weder auf dem Gang treffen noch privat Kontakt haben, sind ggf. weniger epidemiologisch verbunden, als zwei Personen die einem Großraumbüro miteinander arbeiten und die gleiche räumliche Distanz zwischen sich haben.

Norm, Metrik, Topologie

Solche topologischen Beziehungen zwischen Punkten können durch Metriken beschrieben werden (Wiki2Reveal-Audio-Präsentation).

Aufgabe für Lernende

• Definieren Sie eine Metrik auf einem Graphen! Zeigen, Sie dass die Eigenschaften einer Metrik erfüllt sind!
• Begründen Sie, warum epidemiologischen Distanzen zwischen Mumbai und Melbourne ggf. kleiner sind als von Melbourne zu einem weit abgelegenen Ort im Outback von Australien.

Graphen

Mit Graphen kann man den Raum diskretisieren und auf eine endliche Menge von Knoten und den Verbindungen zwischen Knoten beschränken. Die Verbindungen können gerichtet und ungerichtet sein. Gerichtete Verbindung können zusätzliche Kantengewichte zugeordnet werden, die z.B. die Transportkapazität der Verbindung repräsentieren (4-spurige Autobahn im Vergleich zu einer 6-spurigen Autobahn). Allgemein kann man Graphen verwenden um Wegnetze zu kodieren (z.B. U-Bahnnetze, Flugnetze)

Ungerichtete Graphen

Bei ungerichteten Graphen kommt es nur auf darauf an, ob eine Verbindung von einem Knoten zum anderen existiert. In dieser folgenden Definition sind auch Verbindung von einem Knoten zu sich selbst in einem ungerichteten Graphen zulässig.

Abbildung: ungerichteter Graph

Ungerichteter Graph mit 6 Knoten:

Definition: Ungerichteter Graph

Sei $V\neq \emptyset$ eine Menge von Knoten (engl. vertex) und $E=\{e\subseteq \wp (V)\,|\,|e|=1\vee |e|=2\}$ eine Mengen ungerichteten Knotenverbindungen/Kantenmenge (engl. edges) zwischen den Knoten aus der Menge e, dann nennt man $G=(V,E)$ einen ungerichteten Graphen.

Beispiel: ungerichteter Graph

Sei $V:=\{v_{1},v_{2},v_{3},v_{4}\}$ eine Menge von Knoten (engl. vertex) und $E={\big \{}\{v_{1},v_{2}\},\{v_{2},v_{3}\},\{v_{3},v_{4}\},\{v_{4},v_{1}\},\{v_{1},v_{3}\},\{v_{2}\}{\big \}}$. Zeichnen Sie den ungerichteten Graphen.

Gerichtete Graphen

Bei gerichteten Graphen wird die Richtung zwischen zwei Knoten im Graphen berücksichtigt. In einem ungerichteten Graphen bezeichnet $e_{1}:=\{v_{2},v_{3}\}$ und $e_{2}:=\{v_{3},v_{2}\}$ die gleiche Verbindung (engl. edge), während in einem gerichteten Graphen $e_{1}:=(v_{2},v_{3})$ und $e_{2}:=(v_{3},v_{2})$ als Tupel unterschiedliche Richtungen kodieren. $e_{1}:=(v_{2},v_{3})$ ist die Verbindung von $v_{2}$ nach $v_{3}$, während $e_{2}:=(v_{3},v_{2})$ die Verbindung von $v_{2}$ nach $v_{3}$ kodiert.

Definition: Gerichteter Graph

Sei $V\neq \emptyset$ eine Menge von Knoten (engl. vertex) und $E\subseteq V\times V$ eine Mengen Knotenverbindungen/Kantenmenge (engl. edges), dann nennt man $G=(V,E)$ einen gerichteten Graphen.

Beispiel: gerichteter Graph

Sei $V:=\{v_{1},v_{2},v_{3},v_{4}\}$ eine Menge von Knoten (engl. vertex) und $E={\big \{}(v_{1},v_{2}),(v_{2},v_{3}),(v_{3},v_{3}),(v_{3},v_{4}),(v_{4},v_{1}),(v_{1},v_{3}){\big \}}$. Zeichnen Sie den gerichteten Graphen.

Vom Graph zur formalen Beschreibung

Geben Sie zu dem Folgenden gerichteten Graphen $G=(V,E)$ die Mengen $V$ und $E$ konkret an.

Vereinigung von zwei gerichteten Graphen

Zu zwei Graphen $G_{1}=(V_{1},E_{1})$ und $G_{2}=(V_{2},E_{2})$ mit disjunkten Knotenmengen $V_{1}$ und $V_{2}$ nennt man den Graphen mit der Knotenmenge $V_{1}\vee V_{2}$ und der Kantenmenge $E_{1}\vee E_{2}\subseteq (V_{1}\vee V_{2})\times (V_{1}\vee V_{2})$ die disjunkte Vereinigung der Graphen $G_{1}$ und $G_{2}$.

Gerichtete gewichteter Graphen

Bei gerichteten gewichteten Graphen $G=(V,E,w)$wird nicht nur die Richtung zwischen zwei Knoten im Graphen berücksichtigt, sondern diese gerichteten Verbindung auch eine reelle Zahl zugeordnet. In einem gerichteten Graphen bezeichnet $e:=(v_{2},v_{3})$ als Verbindung $e$ (engl. edge) zwischen den Knoten $v_{2}$ und $v_{3}$ wird eine Gewichtung mit einer Funktion

$W:E\to \mathbb {R}$

In der Regel verwendet man als Definitionsbereich von $W$ die Menge $E:=V\times V$ bildet nicht vorhandene gerichtete Verbindungen auf 0 ab.

Einordnung in die Mathematik

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.

Anwendungsgebiete

Graphen sind mathematische Modelle für netzartige Strukturen in Natur und Technik (wie soziale Strukturen, Straßennetze, Computernetze, elektrische Schaltungen, Versorgungsnetze oder chemische 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. Für die Epidemiologie werden Graphen für Transportnetze und für die Konnektivität zwischen Personen und Orten verwendet.

Grapheneigenschaften

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.

Algorithmen auf Graphen

Weil 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. Die Untersuchung von Graphen ist auch Inhalt der Netzwerktheorie. Graphen werden insbesondere durch die Datenstrukturen Adjazenzmatrix, Inzidenzmatrix oder Adjazenzliste repräsentiert.

Graphen in der Epidemiologie

In der Epidemiologie geht es um die Konnektivität von Personen und Orten, denn die Konnektivität bestimmt die Ausbreitungsgeschwindigkeit zwischen den Knoten im Netz.

• Flughäfen als Knoten und Fluglinien als Verbindung und die Transportkapaziät als Gewichtung auf den Verbindungen.
• Personen als Knoten und die gewichtete Verbindung zwischen den Personen. Zwischen Personen unterschiedlicher immunologischem Status besteht eine gerichtete Verbindung. Warum?

Geschichte

Die Ursprünge und Vorläufer der Graphentheorie kann man bis in die Antike zurückverfolgen.

Antike

Ein von der Graphentheorie unabhängiger Vorläufer in der Antike war die Methode Dihairesis, mit deren Hilfe man (nur teilweise grafisch) zoologische, musikwissenschaftliche und andere Begriffe hierarchisierte. Es entstanden so frühe Systematiken innerhalb verschiedener Wissensgebiete.

Euler 1 - Anfänge Graphentheorie

Die Anfänge der Graphentheorie gehen bis in das Jahr 1736 zurück. Damals publizierte Leonhard Euler eine Lösung für das Königsberger Brückenproblem. Die Frage war, ob es einen Rundgang durch die Stadt Königsberg (Preußen) gibt, der jede der sieben Brücken über den Fluss Pregel genau einmal benutzt. Euler konnte eine für dieses Problem nicht erfüllbare notwendige Bedingung angeben und so die Existenz eines solchen Rundganges verneinen.

Euler 2 - Brückenproblem als Karte

Euler 3 - Brückenproblem als Graph

Guthrie 1 - Färbungsproblem

1852 bemerkte der Mathematiker und Botaniker Francis Guthrie, dass vier Farben reichen, um eine Landkarte so zu färben, dass zwei aneinander grenzende Länder stets unterschiedlich gefärbt sind. Viele Mathematiker beschäftigten sich mit diesem Färbungsproblem.

Guthrie 2 - Färbungsproblem - Beweis

Es dauerte jedoch bis 1976 bis der Vier-Farben-Satz mittels Computer bewiesen werden konnte. Erst 1997 stellten Neil Robertson, Daniel Sanders, Paul Seymour, Robin Thomas einen neuen Beweis vor.

Ursprung der Bezeichnung Graph

Der Begriff Graph wurde in Anlehnung an graphischen Notationen chemischer Strukturen erstmals 1878 von dem Mathematiker James Joseph Sylvester verwendet. Als weiterer Begründer der frühen Graphentheorie gilt Arthur Cayley. Eine der ersten Anwendungen waren chemische Konstitutionsformeln. (Siehe auch Chemische Graphentheorie und Literatur: Bonchev/Rouvray, 1990). Das erste Lehrbuch zur Graphentheorie erschien 1936 von Dénes Kőnig.

In der zweiten Hälfte des 20. Jahrhunderts hat William Thomas Tutte maßgeblich an der Weiterentwicklung der Graphentheorie gearbeitet und dieses Teilgebiet der Mathematik stark geprägt.

Teilgebiete der Graphentheorie

Teilgebiete der Graphentheorie sind:

• Algorithmische Graphentheorie: Dieses Teilgebiet beschäftigt sich mit auf Graphen anwendbaren Algorithmen (Liste der Graphalgorithmen).
• Chemische Graphentheorie: Die chemische Graphentheorie gehörte zu den ersten Anwendungen der Strukturerkenntnisse und wendet diese auf chemische Molekülstrukturen an.
• Extremale Graphentheorie: Die extremale Graphentheorie untersucht, welche Graphen einer gegebenen Klasse einen bestimmten Graphenparameter maximieren oder minimieren.

Teilgebiete der Graphentheorie 2

• Geometrische Graphentheorie und Topologische Graphentheorie: Diese Teilgebiete betten Graphen in Ebenen und anderen geometrischen Objekten ein.
• Netzwerkforschung: In der Netzwerkforschung werden komplexe Netzwerke empirisch untersucht. Sie findet Anwendungen in Disziplinen wie Biologie, Wirtschaftswissenschaften und Soziologie.
• Probabilistische Graphentheorie: Mittels Zufallsgraph können Eigenschaften für beliebig große Graphen nachgewiesen werden.

Teilgebiete der Graphentheorie 3

Spektrale Graphentheorie (auch algebraische Graphentheorie): Die spektrale Graphentheorie untersucht Graphen anhand ihrer Adjazenzmatrizen und Laplace-Matrizen durch die Analyse von Eigenwerten, Eigenvektoren und charakteristischen Polynomen. Ungerichtete Graphen besitzen symmetrische Adjazenzmatrizen und deshalb reelle Eigenwerte. Alle Eigenwerte zusammengenommen werden als Spektrum des Graphen bezeichnet. Während die Adjazenzmatrix von der Knotensortierung abhängig ist, ist das Spektrum davon unabhängig.

Graphen und Vektorräume

Im Kontext der Epidemiologie kann man in der Graphentheorie auch Knoten mit Orten im euklidischen Vektorraum miteinander verbinden, indem man in einem Graph mit jedem Knoten auch Ortskoordinaten zuordnet. Damit können sich sich Personen sowohl in einem euklischen Raum bewegen als auch im Graphen über die Menge der Kanten. Eine gerichtete Kante ist hierbei eine Verbindung von zwei Knoten im Graph. Aber gleichzeitig verbindet der Graph auch entfernte Punkt im Vektorraum.

Beispiel für die Verbindung von Graph und Vektorraum

Sind $A=(a_{1},a_{2})\in \mathbb {R} ^{2}$ und $B=(b_{1},b_{2})\in \mathbb {R} ^{2}$ zwei Vektoren in der Ebene zwischen den man einen Euklischen Abstand mit einer Norm über $\|A-B\|$ berechnen kann. Gleichzeitig betrachtet man diese als Knoten miteinander über die Verbindung $(A,B)$ bzw. $(B,A)$ in Beziehung stehen. , bzw. ob sie in der bildlichen Darstellung des Graphen verbunden sind.

Konnektivität herstellen - Veränderung im Graph

Nachbarschaft

Zwei Knoten, die durch eine Kante verbunden sind, heißen benachbart oder adjazent. Wenn die Kanten statt durch Mengen durch geordnete Paare von Knoten angegeben sind, spricht man von gerichteten Graphen. In diesem Falle unterscheidet man zwischen der Kante (a,b) – als Kante von Knoten a zu Knoten b – und der Kante (b,a) – als Kante von Knoten b zu Knoten a.

Darstellung

Knoten und Kanten können in Darstellungen mit Farben gekennzeichnet. Man spricht dann von knoten- bzw. kantengefärbten oder -gewichteten Graphen. Für einw formale Darstellung eignen sich Matrizen, bei denen die Verbindung mit natürlichen Zahlen beschrieben wird (0 keine Verbindung bzw. 1 Verbindung oder auch die Vielfachheit der Verbindung. Werden die Gewichten (d. h. rationalen oder reellen Zahlen) versehen, entspricht die Zahl z.B. der Transportkapazität der Verbindung. Bei negativen Werte der Verbindung (wie z.B. bei künstlichen neuronalen Netzen) kann man durch das Vorzeichen auch hemmende und erregende Verbindung in der Wirkung von Signalen zwischen den Nervenzellen unterscheiden.

Graphentypen

Komplexere Graphentypen sind:

• Multigraphen, bei denen die Kantenmenge eine Multimenge ist
• Hypergraphen, bei denen eine Kante eine beliebig große Menge von Knoten darstellt (man spricht in diesem Falle auch von Hyperkanten)
• Petri-Netze mit zwei Arten von Knoten

Ist die Menge der Knoten endlich, spricht man von endlichen Graphen, ansonsten von unendlichen Graphen.

Grapheigenschaften

Zusammenhangskomponenten

Graphen können verschiedene Eigenschaften haben. So kann ein Graph

• zusammenhängend (im Allgemeinen k-zusammenhängend),
• bipartit (im Allgemeinen k-partit),
• planar,
• eulersch oder hamiltonisch sein.

Teilgraphen

Teilgraphen in der Epidemiologie beziehen sich auch Gemeinschaften mit hoher Interaktion und Kontakten, die sich schnell wechselseitig anstecken können. Mathematisch kann nach der Existenz spezieller Teilgraphen oder Minoren gefragt werden oder bestimmte Parameter untersucht werden, wie zum Beispiel Knotenzahl, Kantenzahl, Minimalgrad, Maximalgrad, Taillenweite, Durchmesser, Knotenzusammenhangszahl, Kantenzusammenhangszahl, Bogenzusammenhangszahl, chromatische Zahl, Knotenüberdeckungszahl (Faktor), Unabhängigkeitszahl (Stabilitätszahl) oder Cliquenzahl. Zwei Graphen können isomorph (strukturell gleich) oder automorph zueinander sein.

Beziehung zwischen Grapheneigenschaften

Hat man eine hochvernetzte Gruppe von Personen mit hoher Interaktivität oder einen eher "langgezogenen" Graphen, in dem sich eine Infektion nur in einer Kette ausbreiten kann. Die topologischen Eigenschaften zwischen den Knoten im Graph und die Prozesse die darin ablaufen hängen von den verschiedenen Eigenschaften des Graphen ab, die zueinander in Beziehung stehen. Die Beziehungen zu untersuchen ist eine Aufgabe der Graphentheorie. Beispielsweise ist die Knotenzusammenhangszahl nie größer als die Kantenzusammenhangszahl, welche wiederum nie größer als der Minimalgrad des betrachteten Graphen ist. In ebenen Graphen ist die Färbungszahl immer kleiner als fünf. Diese Aussage ist auch als der Vier-Farben-Satz bekannt.

Algorithmische Bestimmung von Grapheneigenschaften

gerichteter zyklischer Graph

Für die Modellbildung ist die algorithmische Bestimmung von Eigenschaften wesentlich, um Vorhersagen über ein Ausbreitung im Graphen zu machen. Einige der aufgezählten Grapheneigenschaften sind relativ schnell algorithmisch bestimmbar, etwa wenn der Aufwand höchstens mit dem Quadrat der Größe der Graphen wächst. Andere Eigenschaften praktisch angewandter Graphen sind innerhalb der Lebensdauer heutiger Computer nicht exakt zu bestimmen. Allerdings kann in diesen Fällen der Einsatz von heuristischen Verfahren zu sinnvollen Näherungslösungen führen.

Graphenklassen bzgl. Zusammenhang

Bipartiter Graph

Grundsätzlich werden Graphen in gerichtete und ungerichtete Graphen unterteilt.

Aufgrund des Zusammenhangs unterscheidet man:

• azyklische Graphen: Weg, Pfad, Wald, Baum, DAG (directed acyclic graph)
• zyklische Graphen, beispielsweise: Zyklus, Kreis, Vollständige Graphen.

Weitere Graphenklassen

Aufgrund des Vorhandenseins bestimmter Eigenschaften lassen sich weitere Graphenklassen unterscheiden wie

• Bipartite Graphen,
• Planare Graphen,
• Reguläre Graphen,
• Chordale Graphen,
• Perfekte Graphen,
• Magische Graphen.

Wenn ein Knoten besonders ausgezeichnet ist, spricht man von einer Wurzel bzw. einem gewurzeltem Graphen. Besondere Bedeutung haben gewurzelte Bäume unter anderem auch als Baumstruktur.

Probleme

Die wichtigsten Probleme und Ergebnisse der Graphentheorie werden im Folgenden dargestellt:

Graphfärbung

Färbung

Ein bekanntes Problem fragt, wie viele Farben man braucht um die Länder einer Landkarte einzufärben, sodass keine zwei benachbarten Länder die gleiche Farbe zugewiesen bekommen. Die Nachbarschaftsbeziehung der Länder kann man als planaren Graph repräsentieren. Das Problem kann nun als Knoten-Färbungsproblem modelliert werden. Nach dem Vier-Farben-Satz braucht man maximal vier verschiedene Farben. Ob sich im Allgemeinen ein Graph mit weniger Farben einfärben lässt, kann man nach heutigem Wissensstand nicht effizient entscheiden. Das Problem gilt als eines der schwierigsten Probleme in der Klasse der NP-vollständigen Probleme. Unter der Voraussetzung, dass P≠ NP, ist selbst eine bis auf einen konstanten Faktor angenäherte Lösung nicht effizient möglich.

Suchprobleme

Eine wichtige Anwendung der algorithmischen Graphentheorie ist die Suche nach einer kürzesten Route zwischen zwei Orten in einem Straßennetz. Dieses Problem kann man als Graphenproblem modellieren. Hierzu abstrahiert man das Straßennetz, in dem man alle Orte als Knoten aufnimmt, und eine Kante hinzufügt, wenn es eine Verbindung zwischen diesen Orten gibt. Die Kanten dieses Graphen werden je nach Anwendung gewichtet, zum Beispiel mit der Länge der assoziierten Verbindung. Mit Hilfe eines Algorithmus zum Finden von kürzesten Pfaden (beispielsweise mit dem Algorithmus von Dijkstra) kann eine kürzeste Verbindung effizient gefunden werden. (siehe auch: Graphsuchalgorithmen)

Handlungsreisendenproblem

Durchlaufbarkeit von Graphen

Algorithmisch deutlich schwieriger ist die Bestimmung einer kürzesten Rundreise (siehe Problem des Handlungsreisenden), bei der alle Orte eines Straßennetzes genau einmal besucht werden müssen. Da die Zahl der möglichen Rundreisen faktoriell mit der Zahl der Orte wächst, ist der naive Algorithmus, alle Rundreisen auszuprobieren und die kürzeste auszuwählen, für praktische Anwendungen nur für sehr kleine Netzwerke praktikabel. Es existieren für dieses Problem eine Reihe von Approximationsalgorithmen, die eine gute aber nicht eine optimale Rundreise finden. So liefert die Christofides-Heuristik eine Rundreise die maximal 1,5-mal so lang ist wie die bestmögliche. Unter der Annahme, dass P ≠ NP (siehe P-NP-Problem), existiert kein effizienter Algorithmus für die Bestimmung einer optimalen Lösung, da dieses Problem NP-schwer ist.

Königsberger Brückenproblem

Das Königsberger Brückenproblem fragt nach der Existenz eines Eulerkreises. Während sich das Eulerkreisproblem mittels Hierholzer-Verfahren in linearer Zeit lösen lässt, ist das Finden eines Hamiltonkreises (ein geschlossener Pfad in einem Graphen, der jeden Knoten genau einmal enthält) NP-schwierig. Beim Briefträgerproblem wird nach nach einem kürzesten Zyklus gefragt, der alle Kanten mindestens einmal durchläuft.

Zusammenhang

Beim Zusammenhang wird gefragt, ob bzw. über wie viele Wege zwei Knoten untereinander erreichbar sind. Dies spielt beispielsweise bei der Beurteilung der Versorgungsnetze hinsichtlich der kritischen (ausfallbedrohten Teile) eine Rolle.

Graph mit Cliquen

Cliquenproblem

Die Frage nach dem Vorhandensein (ggf. maximaler) Cliquen sucht die Teile eines Graphen, die untereinander vollständig mit Kanten verbunden sind.

Knotenüberdeckung

Das Knotenüberdeckungsproblem sucht nach einer Teilmenge von Knoten eines Graphen, die von jeder Kante mindestens einen Endknoten enthält.

Flüsse und Schnitte in Netzwerken

Mit der Frage nach dem maximalen Fluss lassen sich Versorgungsnetze hinsichtlich ihrer Kapazität beurteilen.

Matching im bipartiten Graphen

Matching

Matchingprobleme, die sich auf Flussprobleme zurückführen lassen, fragen nach der optimalen Auswahl von Kanten, so dass keine zwei Kanten inzident zu einem Knoten sind. Damit lassen sich Zuordnungsprobleme, beispielsweise der Ressourcennutzung wie Raum- oder Maschinenbelegung lösen.

Weitere Graphenprobleme

Zu den weiteren Graphenproblemen zählen

• das Finden einer stabilen Menge,
• das Graphzeichnen (hierfür existiert Software zur Visualisierung von Graphen: yEd, Graphviz) und
• die Transformation von Graphen anhand von regelbasierten Graphersetzungssystemen. Graphersetzungssysteme, die dem Aufzählen aller Graphen einer Graphsprache dienen, werden auch Graphgrammatik genannt

Literatur

• Martin Aigner: Graphentheorie: eine Entwicklung aus dem 4-Farben-Problem. 1984 (269 Seiten).
• Daniel Bonchev, D. H. Rouvray: Chemical Graph Theory: Introduction and Fundamentals. Abacus, New York NY 1990/1991, ISBN 0-85626-454-7.
• J. Sedlacek: Einführung in die Graphentheorie. B. G. Teubner, Leipzig 1968, 1972.
• M. Nitzsche: Graphen für Einsteiger (Rund um das Haus vom Nikolaus). Vieweg, Wiesbaden 2004, ISBN 3-528-03215-4.
• R. Diestel: Graphentheorie. 3. Auflage. Springer, Heidelberg 2005, ISBN 3-540-67656-2 (online-download).
• Peter Gritzmann, René Brandenberg: Das Geheimnis des kürzesten Weges. Ein mathematisches Abenteuer. 2. Auflage. Springer, Berlin/Heidelberg 2003, ISBN 3-540-00045-3.
• Peter Tittmann: Graphentheorie. Eine anwendungsorientierte Einführung. 3 Auflage. Hanser, München 2019, ISBN 978-3-446-46052-2

Weblinks

• 

 Wikibooks: Mathematik-Glossar: Graphentheorie – Lern- und Lehrmaterialien

Seiten-Information

Diese Seite wurde auf Basis der folgenden Wikipedia-Quelle erstellt:

• Graphentheorie https://de.wikipedia.org/wiki/Graphentheorie
• Datum: 13.5.2020 - Versionsgeschichte Wikipedia
• Wikipedia2Wikiversity-Konverter: https://niebert.github.com/Wikipedia2Wikiversity

Siehe auch

• Normen, Metriken, Topologie
• Mathematik-Glossar: Graphentheorie
• Kurs:Räumliche Modellbildung

Seiteninformation

Dieser Wiki2Reveal Foliensatz wurde für den Lerneinheit Kurs:Räumliche Modellbildung' erstellt der Link für die Wiki2Reveal-Folien wurde mit dem Wiki2Reveal-Linkgenerator erstellt.

• Die Seite wurde als Dokumententyp PanDocElectron-SLIDE erstellt.
• Link zur Quelle in Wikiversity: https://de.wikiversity.org/wiki/Epidemiologische%20Distanz
• siehe auch weitere Informationen zu Wiki2Reveal und unter Wiki2Reveal-Linkgenerator.