imported>Anthroporraistes: /* Verwendung */ Rechtschreibung

2023-05-26T09:48:06Z

Verwendung: Rechtschreibung

Neue Seite

[[Datei:Markovkate 01.svg|mini|Ein einfacher Übergangsgraph mit zwei Knoten. Die [[Adjazenzmatrix]] des Graphen ist <math>A = \begin{bmatrix}
0.3 & 0.7 \\
0.4 & 0.6 \\
\end{bmatrix}</math>.
Da alle Einträge größer als 0 sind und alle Zeilensummen 1, ergeben ist sie [[Übergangsmatrix|zeilenstochastisch]].]]

'''Übergangsgraphen''' sind spezielle [[Gerichteter Graph|gerichtete]] Graphen mit [[Kantengewicht]]en, die eine Verbindung zwischen [[Stochastik]] und [[Graphentheorie]] schlagen. Sie eignen sich besonders zur anschaulichen Darstellung von zeitdiskreten homogenen [[Markow-Kette]]n.

== Definition ==

Ein gerichteter und kantengewichteter [[Graph (Graphentheorie)|Graph]] <math> G </math> heißt Übergangsgraph, wenn für jeden [[Knoten (Graphentheorie)|Knoten]] <math>i</math> die Kantengewichte der von <math>i</math> ausgehenden [[Kante (Graphentheorie)|Kanten]] größer 0 sind und sich zu 1 aufsummieren:

:<math> \sum_{j \in N_G^+(i)} c_{ij}=1 </math>.

Dabei ist <math>N_G^+(i)</math> die [[Nachbarschaft (Graphentheorie)|Nachfolgermenge]] von Knoten <math>i</math>, also die Menge aller Knoten, die durch von <math>i</math> ausgehende Kanten erreicht werden können.

Äquivalent dazu ist, dass der Graph <math> G </math> [[Adjazenzgraph]] einer [[Übergangsmatrix|zeilenstochastischen Matrix]] ist.

== Verwendung ==
Übergangsgraphen dienen zur anschaulichen Darstellung von [[Markow-Kette#Diskrete Zeit und höchstens abzählbar unendliche Zustandsmenge|homogenen Markow-Ketten mit endlichem Zustandsraum in diskreter Zeit]]. Dabei entspricht jeder Knoten einem Zustand des Systems und die Kantengewichte sind die [[Übergangswahrscheinlichkeit]]en zwischen den Zuständen. Dann ist <math> c_{ij} </math> genau die [[Wahrscheinlichkeit]], vom Zustand <math> i </math> in den Zustand <math> j </math> zu wechseln. Einige Eigenschaften der Markow-Kette finden sich direkt im Übergangsgraph wieder:
* Der Übergangsgraph ist genau dann [[Zusammenhang (Graphentheorie)| stark zusammenhängend]], wenn die Markow-Kette [[Irreduzible Markow-Kette| irreduzibel]] ist.
* Der Zustand <math> j </math> ist von dem Zustand <math> i </math> aus [[Kommunizierende Zustände#Definition|erreichbar]], wenn es einen <math>i-j</math>-Pfad im Übergangsgraph gibt.
* Zwei Zustände i und j [[Kommunizierende Zustände|kommunizieren]] genau dann, wenn sowohl ein <math> i-j</math>-Pfad als auch ein <math> j-i</math>-Pfad im Übergangsgraph existiert.
* Ist der Übergangsgraph [[Bipartiter Graph|bipartit]], so hat jeder Zustand der Markow-Kette gerade [[Periodische Markow-Kette|Periode]].
* Ist der Übergangsgraph [[Bipartiter Graph|bipartit]] und zusammenhängend, so hat die Markow-Kette gerade Periode.

== Anwendungsbeispiel ==
Mit Hilfe von Übergangsgraphen lässt sich das [[Wahlverhalten|Wahl-]] und [[Kaufverhalten]] visualisieren. Dargestellt werden die prozentuale Zahl von Wieder- und Wechselwählern. Bezogen auf die obigen Abbildung würden 60 % der [[Politische Partei|Partei]] bzw. dem [[Produkt (Wirtschaft)|Produkt]] A treu bleiben und 40 % zu Partei bzw. Produkt E wechseln. Die Zahl der Wiederwähler bei Partei bzw. Produkt E liegt bei 30 %, die Zahl der Wechselwähler bei 70 %.
Allerdings wird der Übergangsgraph schon ab vier Parteien bzw. Produkten recht unübersichtlich.

== Literatur ==

* {{Literatur|Autor=[[Hans-Otto Georgii]]|Titel=Stochastik|TitelErg=Einführung in die Wahrscheinlichkeitstheorie und Statistik|Auflage=4.|Verlag=Walter de Gruyter|Ort=Berlin|Jahr=2009|ISBN=978-3-11-021526-7 |DOI=10.1515/9783110215274}}
* Marion Patyna, Klaus Schilling: ''Lineare Algebra: Mehrstufige Prozesse – Matrizenrechnung'', Eins Verlag Köln, 1. Auflage 2011, S. 104–118, ISBN 978-3-427-04440-6.

{{SORTIERUNG:Ubergangsgraph}}
[[Kategorie:Graphentheorie]]
[[Kategorie:Graph]]
[[Kategorie:Markow-Prozesse]]

Übergangsgraph - Versionsgeschichte

imported>Anthroporraistes: /* Verwendung */ Rechtschreibung