\( \newcommand{\data}{\textnormal{data}} \newcommand{\lower}{\textnormal{lower}} \newcommand{\upper}{\textnormal{upper}} \newcommand{\array}{\textnormal{array}} \newcommand{\depth}{\textnormal{depth}} \newcommand{\height}{\textnormal{height}} \newcommand{\BST}{\textnormal{BST}} \newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\ceil}[1]{\left\lceil #1 \right\rceil} \newcommand{\lognpone}{\ceil{\log_2(n+1)}} \newcommand{\bitsize}{\textnormal{bitSize}} \newcommand{\mult}{\textnormal{mult}} \newcommand{\inneighbors}{\textnormal{inNeighbors}} \newcommand{\outneighbors}{\textnormal{outNeighbors}} \newcommand{\neighbors}{\textnormal{neighbors}} \newcommand{\indeg}{\textnormal{indeg}} \newcommand{\outdeg}{\textnormal{outdeg}} \newcommand{\scc}{\textnormal{scc}} \newcommand{\R}{\mathbb{R}} \newcommand{\val}{\textnormal{val}} \newcommand{\dist}{\textnormal{dist}} \newcommand{\flows}{\textnormal{flows}} \newcommand{\Z}{\mathbb{Z}} \)

Wie können wir einen Graphen im PRAM-Modell darstellen?

  1. Liste von Kanten. Das heißt, $G$ ist gegeben als ein Array der Länge $m$, und jede Zelle des Arrays enthält eine Kante $(u,v)$ (bzw. $\{u,v\}$ falls $G$ ungerichtet ist).
  2. Adjazenzlisten. Hier haben wir ein Knotenarray $[v_1,v_2,\dots,v_n]$, und jede der $n$ Zellen enthält, neben dem Namen des Knoten, einen Zeiger auf dessen Adjazenzliste, also die Liste aller Nachbarn.

    In dieser Darstellung ist uns wichtig, dass die Adjazenzlisten "kompakt" im Speicher liegen, also insgesamt in einem Bereich von $O(m)$ (oder sogar nur $m$) Speicherzellen.

Wir wollen nun sehen, dass wir effizient aus der Kantenlistendarstellung die Adjazenzlisten berechnen können. Hierfür eine kleine Aufwärmübung, die an die Präfixsummen anknüpft.

Übungsaufgabe Sei $A = [a_1, \dots, a_n]$ ein Array mit Elementen aus $\{0,1\}$. Als Ergebnis wollen wir

  1. ein Array $B = [b_1, \dots, b_n]$, wobei $b_i$ die Anzahl der Einsen im Präfix $[a_1,\dots,a_i]$ ist und, weniger einfach,
  2. ein Array $C = [c_1, \dots, c_n]$, so dass $c_i$ der Index der nächsten $1$ links von $i$ ist, also \begin{align*} c_i := \begin{cases} \max \{j \leq i \ | \ a_j = 1\} & \textnormal{falls es so ein $j$ gibt}\\ -1 & \textnormal{sonst.} \end{cases} \end{align*}

Zeigen Sie, wie man das in $O(n)$ Arbeit und $O(\log n)$ Zeit berechnen kann.

Übungsaufgabe Sei $G=(V,E)$ als Liste der Kanten gegeben, also als Array $[e_1, e_2, \dots, e_m]$. Zeigen Sie, wie man daraus in $O(\log n)$ die Darstellung als Adjazenzlisten berechnen kann.

Übungsaufgabe Sei $G = (V,E)$ ein Graph. Im Allgemeinen kann die Knotenmenge $V$ ja beliebig sein. $G$ könnte also gegeben sein als Array

[{Chemnitz, Riesa}, {Leipzig, Geithain}, {Chemnitz, Freiberg}, {Freiberg, Dresden}, {Dresden, Riesa}, {Leipzig, Riesa}, {Chemnitz, Geithain}]

Zeigen Sie, dass wir immer $V = \{1, \dots, n\}$ annehmen können. Konkret würden wir beispielsweise den obigen Graphen darstellen durch zwei Arrays:

[(1, Chemnitz), (2, Leipzig), (3, Riesa), (4, Freiberg), (5, Dresden), (6, Geithain)]
[{1,3}, {2,6}, {1,4}, {4,5}, {5,3}, {2,3}, {1,6}]