---
header-includes: |
    \usepackage[most]{tcolorbox}
    \usetikzlibrary {decorations.markings}
---

## {.standout}
Herzlich Willkommen!

Du kannst dich schon anmelden

\texttt{vorname.nachname}

und den Bildschirm ausschalten.

## \faIcon{hands-helping} / \faIcon{chalkboard} Arbeitsauftrag: Fachbegriffe \hfill{} 1/5

### Diskutiert folgende Aussage:

\vspace{0.3cm}
`\only<1,2>{`{=latex}

> Folgender \boldred{Graf} ist \boldred{gerichtet}, da die \boldred{Punkte} mit gerichteten \boldred{Connections} verbunden sind.

`}`{=latex}

`\only<3>{`{=latex}

> Folgender \boldgreen{Graph} ist **gerichtet**, da die \boldgreen{Knoten/vertices} mit gerichteten \boldgreen{Kanten/edges} verbunden sind.

`}`{=latex}

\hspace{1cm}
\begin{tikzpicture}
\node[draw, circle] (a) at (0, -1) {A};
\node[draw, circle] (b) at (2, -1) {B};
\node[draw, circle] (c) at (2, 1) {C};
\node[draw, circle] (d) at (2, 2.5) {D};
\draw[-Triangle] (a) -- (b);
\draw[-Triangle] (b) -- (c);
\draw[-Triangle] (c) -- (a);
\draw[-Triangle] (c) -- (d);

\only<1> {
  \node[opacity=0] at (13.5, 3.25) {foo};
}
\only<2> {
  \node[rotate=3] at (9, 1) {\includegraphics[keepaspectratio, width=4.5cm]{../Intro/img/vlad_tepes_002.jpg}};
  \draw[red, line width=2pt] (6cm, -2cm) -- (12cm, 3.5cm) (12cm, -2cm) -- (6cm, 3.5cm);
}
\end{tikzpicture}

\only<2>{
\begin{tikzpicture}[overlay, remember picture]
  \node[rotate=-30,scale=3] at (6, 3) {\large \boldred{Falsch}};
\end{tikzpicture}
}

## \faIcon{hands-helping} / \faIcon{chalkboard} Arbeitsauftrag: Wege durch Graphen \hfill{} 2/5

### Diskutiert folgende Aussage:

\vspace{0.2cm}
> Ein Graph heißt \only<1,2>{\boldred{zusammenhängend}}\only<3>{\boldgreen{vollständig}}, wenn jeder Knoten mit jedem anderen Knoten verbunden ist.
> Ein derartiger Graph hat immer \only<1,2>{$n^2$}\only<3>{$\frac{(n^2-n)}{2}$} Kanten, wenn n die Anzahl der Knoten ist.

`\begin{center}`{=latex}
`\only<1>{`{=latex}
```{.graphviz dpi=150 height=5cm}
digraph {
  bgcolor=transparent
  node [shape=circle]
  layout=circo
  A -> B
  A -> C
  A -> D
  A -> E
  B -> C
  B -> D
  B -> E
  C -> D
  C -> E
  D -> E
}
```
`}\only<2>{`{=latex}
```{.graphviz dpi=150 height=5cm}
graph {
  bgcolor=transparent
  node [shape=circle]
  layout=circo
  A -- B
  A -- C
  A -- D
  A -- E
  B -- C
  B -- D
  B -- E
  C -- D
  C -- E
  D -- E
}
```
`}\end{center}`{=latex}

\only<2>{
\begin{tikzpicture}[overlay, remember picture]
  \node[rotate=-30,scale=3] at (11.5, 3) {\large \boldred{Falsch}};
\end{tikzpicture}
}

## \faIcon{hands-helping} / \faIcon{chalkboard} Arbeitsauftrag: Wege durch Graphen \hfill{} 3/5

### Diskutiert folgende Aussage:

\vspace{0.5cm}
> Der \boldred{Pfad} `A/B/D` ist kürzer als der Pfad `A/B/C/D`, weil er [weniger]{.underline} Knoten enthält.

`\begin{center}`{=latex}
```{.graphviz dpi=150 height=3cm}
digraph {
  bgcolor=transparent
  rankdir=LR
  node [shape=circle]
  A -> B [label=2]
  B -> C [label=1]
  B -> D [label=3]
  C -> D [label=1]
}
```
`\end{center}`{=latex}

\pause

Die Länge eines Pfades in einem [gewichteten]{.underline} Graphen ist die **Summe der Kantengewichte**.

::: {.columns}
:::: {.column width=50%}
* Länge(`A/B/D`) = 5
::::

:::: {.column width=50%}
* Länge(`A/B/C/D`) = \boldred{4}
::::
:::

## \faIcon{hands-helping} / \faIcon{chalkboard} Arbeitsauftrag: Arrays initialisieren \hfill{} 4/5

### Diskutiert folgende Aussage:

```java
int[] zahlen;
zahlen = new zahlen[10];
verwende(zahlen[2]);

Knoten[] knoten = new Knoten[42];
verwende(knoten[4]);
```
\vspace{0.7cm}
> Um die Werte eines Array verwenden zu können, reicht es aus das Array zu deklarieren und dieses anschließend zu initialisieren.

\pause
\begin{tikzpicture}[overlay, remember picture]
  \node[rotate=-30,scale=3] at (10, 3) {\large \boldred{Falsch}};
\end{tikzpicture}

Die \boldred{einzelnen} Einträge müssen ebenfalls initialisiert werden.

## \faIcon{hands-helping} / \faIcon{chalkboard} Arbeitsauftrag: Graphendarstellung \hfill{} 5/5

### Diskutiert folgende Aussage:

\vspace{0.2cm}
> Alle vier Graphen sind identisch!

![](img/Copyrighted/Cornelsen_S11_A6.png){.center}

\pause

\boldred{iii} ist mit den anderen nicht identisch, da beispielsweise \textbf{A} keine Kante zu \textbf{E} hat.

##

\vspace{0.4cm}
![](../Intro/img/bike.png)

## \faIcon{pencil-alt} Arbeitsauftrag: Abitur 2021 Burning Man - 10min

[...] Aufgrund der großen Distanzen zwischen den Orten des Festivals nutzen viele Besucher Fahrräder als Transportmittel.


::: {.columns}
:::: {.column width=50%}
![](img/abi2021_burning_man_a4_graph.png){.center}

*Die Besucher wollen ein [vollständiges]{.underline} Radwege-Netz.*
::::

:::: {.column width=50%}
1. Zeichne einen Teilgraphen von G mit drei Knoten, der vollständig ist.
2. Zeichne außerdem einen Teilgraphen von G mit fünf Knoten, der mit möglichst wenig weiteren Kanten zu einem vollständigen Graphen ergänzt werden kann.
   Gib an, wie viele Kanten hinzugefügt werden müssten.
3. Bestimme darüber hinaus, wie viele Radwege zusätzlich zu den 19 vorhandenen noch gebaut werden müssen.

::::
:::


##

\begin{center}
\begin{tikzpicture}[]
  \node[draw, thick] at (0, 0) {%
    \includegraphics[keepaspectratio=FALSE, height=8cm, width=4.5cm]{../Intro/img/Copyrighted/navi.png}};
  \node[draw, thick] at (4.75, 0) {%
    \includegraphics[keepaspectratio=FALSE, height=8cm, width=4.5cm]{../Intro/img/Copyrighted/route.png}};
  \node[draw, thick] at (9.5, 0) {%
    \includegraphics[keepaspectratio=FALSE, height=8cm, width=4.5cm]{../Intro/img/Copyrighted/graph.png}};
\end{tikzpicture}
\end{center}

##

\vfill{}
![](img/Copyrighted/bike_matrix.png){.center}
\vfill{}

## Darstellung von Graphen

::: {.columns}
:::: {.column width=50%}
![](../Intro/img/Copyrighted/graph.png){height=90%}
::::

:::: {.column width=50%}
![](img/Copyrighted/bike_adj_matrix.png)
::::
:::

## Adjazenzmatrix

::: {.columns align=center}
:::: {.column width=50%}
\resizebox{0.9\textwidth}{!}{
  \tikzstyle{edge} = [thick]
  \input{graph.tikz}
}
::::

:::: {.column width=50%}
\begin{center}
\begin{tabular}{c | c | c | c | c | c}
\rowcolor{gray!30}\cellcolor{gray} & v1 & v2 & v3 & v4 & v5 \\
\hline
\cellcolor{gray!30} v1 & \only<3>{\cellcolor{gray!30}0} & \only<2->{\textbf 1} & \only<3>{0} & \only<3>{0} & \only<2->{\textbf 1} \\
\hline
\cellcolor{gray!30} v2 & \only<2->{\textbf 1} & \only<3>{\cellcolor{gray!30}0} & \only<2->{\textbf 1} & \only<3>{0} & \only<2->{\textbf 1} \\
\hline
\cellcolor{gray!30} v3 & \only<3>{0} & \only<2->{\textbf 1} & \only<3>{\cellcolor{gray!30}0} & \only<2->{\textbf 1} & \only<2->{\textbf 1} \\
\hline
\cellcolor{gray!30} v4 & \only<3>{0} & \only<3>{0} & \only<2->{\textbf 1} & \only<3>{\cellcolor{gray!30}0} & \only<2->{\textbf 1} \\
\hline
\cellcolor{gray!30} v5 & \only<2->{\textbf 1} & \only<2->{\textbf 1} & \only<2->{\textbf1} & \only<2->{\textbf 1} & \only<3>{\cellcolor{gray!30}0} \\
\end{tabular}
\end{center}
::::
:::

## Adjazenzmatrix - gerichtet

::: {.columns align=center}
:::: {.column width=45%}
\resizebox{0.9\textwidth}{!}{
  \tikzstyle{edge} = [thick, -Triangle]
  \input{graph.tikz}
}
::::

:::: {.column width=55%}
\begin{center}
\begin{tikzpicture}
\node {
\begin{tabular}{c | c | c | c | c | c}
\cellcolor{gray} & \only<-2>{\cellcolor{gray!30}} \only<3>{\cellcolor{teal!30}}v1 & \only<-2>{\cellcolor{gray!30}} \only<3>{\cellcolor{teal!30}}v2 & \only<-2>{\cellcolor{gray!30}} \only<3>{\cellcolor{teal!30}}v3 & \only<-2>{\cellcolor{gray!30}} \only<3>{\cellcolor{teal!30}}v4 & \only<-2>{\cellcolor{gray!30}} \only<3>{\cellcolor{teal!30}}v5 \\
\hline
\only<-2>{\cellcolor{gray!30}}\only<3>{\cellcolor{yellow!30}} v1 & \only<2->{\cellcolor{gray!30}0} & \only<2->{\textbf 1} & \only<2->{0} & \only<2->{0} & \only<2->{\textbf 1} \\
\hline
\only<-2>{\cellcolor{gray!30}}\only<3>{\cellcolor{yellow!30}} v2 & \only<2->{0} & \only<2->{\cellcolor{gray!30}0} & \only<2->{\textbf 1} & \only<2->{0} & \only<2->{\textbf 1} \\
\hline
\only<-2>{\cellcolor{gray!30}}\only<3>{\cellcolor{yellow!30}} v3 & \only<2->{0} & \only<2->{0} & \only<2->{\cellcolor{gray!30}0} & \only<2->{\textbf 1} & \only<2->{\textbf 1} \\
\hline
\only<-2>{\cellcolor{gray!30}}\only<3>{\cellcolor{yellow!30}} v4 & \only<2->{0} & \only<2->{0} & \only<2->{0} & \only<2->{\cellcolor{gray!30}0} & \only<2->{\textbf 1} \\
\hline
\only<-2>{\cellcolor{gray!30}}\only<3>{\cellcolor{yellow!30}} v5 & \only<2->{0} & \only<2->{0} & \only<2->{0} & \only<2->{0} & \only<2->{\cellcolor{gray!30}0} \\
\end{tabular}
};
\only<-2> {
  \node[opacity=0, fill=yellow!30, rotate=90] at (-3.2, 0) {Startknoten};
  \node[opacity=0, fill=teal!30] at (1, 2.1) {Zielknoten};
}
\only<3> {
  \node[fill=yellow!30, rotate=90] at (-3.2, 0) {Startknoten};
  \node[fill=teal!30] at (1, 2.1) {Zielknoten};
}
\end{tikzpicture}
\end{center}
::::
:::

## Adjazenzmatrix - gewichtet

::: {.columns align=center}
:::: {.column width=50%}
\resizebox{0.9\textwidth}{!}{
  \input{weighted_graph.tikz}
}
::::

:::: {.column width=50%}
\begin{center}
\begin{tabular}{c | c | c | c | c | c}
\rowcolor{gray!30} \cellcolor{gray} & v1 & v2 & v3 & v4 & v5 \\
\hline
\cellcolor{gray!30} v1 & \cellcolor{gray!30} \only<2->{\boldred{-1}} & \only<2->{\textbf{10}} & \only<2->{\boldred{-1}} & \only<2->{\boldred{-1}} & \only<2->{\textbf{30}} \\
\hline
\cellcolor{gray!30} v2 & \only<2->{\textbf{10}} & \cellcolor{gray!30}\only<2->{\boldred{-1}} & \only<2->{\textbf{40}} & \only<2->{\boldred{-1}} & \only<2->{\textbf{50}} \\
\hline
\cellcolor{gray!30} v3 & \only<2->{\boldred{-1}} & \only<2->{\textbf{40}} & \cellcolor{gray!30}\only<2->{\boldred{-1}} & \only<2->{\textbf{10}} & \only<2->{\textbf{30}} \\
\hline
\cellcolor{gray!30} v4 & \only<2->{\boldred{-1}} & \only<2->{\boldred{-1}} & \only<2->{\textbf{10}} & \cellcolor{gray!30}\only<2->{\boldred{-1}} & \only<2->{\textbf{20}} \\
\hline
\cellcolor{gray!30} v5 & \only<2->{\textbf{30}} & \only<2->{\textbf{50}} & \only<2->{\textbf{30}} & \only<2->{\textbf{20}} & \cellcolor{gray!30}\only<2->{\boldred{-1}} \\
\end{tabular}
\end{center}


\vspace{0.5cm}
\only<-2>{
\phantom{Der Eintrag \boldred{-1} symbolisiert \textit{"keine Kante"}, um das Kantengewicht 0 zu ermöglichen.}
}
\only<3>{
Der Eintrag \boldred{-1} symbolisiert \textit{"keine Kante"}, um das Kantengewicht 0 zu ermöglichen.
}
::::
:::

## \faIcon{pencil-alt} Arbeitsauftrag - Arbeitsblatt 10min

### Lückentext

### Arbeitsauftrag 1: Graph $\rightarrow$ Adjazenzmatrix

### Arbeitsauftrag 2: Adjazenzmatrix $\rightarrow$ Graph 

## {.standout}

So jetzt für den Computer!

\Huge \faIcon{java}

## Implementierung einer Adjazenzmatrix

::: {.columns}
:::: {.column width=50%}
`\begin{center}`{=latex}
```{.graphviz dpi=150 height=3.5cm}
graph {
  bgcolor=transparent
  layout=circo
  node [shape=circle]
  nodesep=0.5
  v1 -- v2
  v2 -- v3
  v3 -- v4
  v4 -- v1
}
```
`\end{center}`{=latex}

\pause
\begin{center}
\begin{tabular}{c|c|c|c|c}
\rowcolor{gray!30}\cellcolor{gray} & v1 & v2 & v3 & v4 \\
\hline
\cellcolor{gray!30} v1 & \cellcolor{gray!30}0 & 1 & 0 & 1 \\
\hline
\cellcolor{gray!30} v2 & 1 & \cellcolor{gray!30}0 & 1 & 0 \\
\hline
\cellcolor{gray!30} v3 & 0 & 1 & \cellcolor{gray!30}0 & 1 \\
\hline
\cellcolor{gray!30} v4 & 1 & 0 & 1 & \cellcolor{gray!30}0 \\
\end{tabular}
\end{center}
::::

:::: {.column width=50%}
\pause
Welche Datenstruktur ist geeignet?

\begin{tikzpicture}
  \foreach \y in {0,...,3} {
    \node at (-0.25, 3.5 - \y) {\textbf \y};
  }

  \foreach \y in {0,...,3} {
    \node[anchor=south west, minimum size=1cm, draw] at (0, \y) {};
  }

  \node[opacity=0] at (5, 4.5) {3};
  \node[opacity=0, anchor=south west, minimum size=1cm, draw] at (4.5, 3.5) {};
  \node[opacity=0, anchor=south west, minimum size=1cm, draw] at (4.5, -0.5) {};
\end{tikzpicture}

```java
int[] matrix = new int[4]; ?
```
::::
:::

<!-- FIXME use code in only env -->
## Implementierung einer Adjazenzmatrix

::: {.columns}
:::: {.column width=50%}
`\begin{center}`{=latex}
```{.graphviz dpi=150 height=3.5cm}
graph {
  bgcolor=transparent
  layout=circo
  node [shape=circle]
  nodesep=0.5
  v1 -- v2
  v2 -- v3
  v3 -- v4
  v4 -- v1
}
```
`\end{center}`{=latex}

\begin{center}
\begin{tabular}{c|c|c|c|c}
\rowcolor{gray!30}\cellcolor{gray} & v1 & v2 & v3 & v4 \\
\hline
\cellcolor{gray!30} v1 & \cellcolor{gray!30}0 & 1 & 0 & 1 \\
\hline
\cellcolor{gray!30} v2 & 1 & \cellcolor{gray!30}0 & 1 & 0 \\
\hline
\cellcolor{gray!30} v3 & 0 & 1 & \cellcolor{gray!30}0 & 1 \\
\hline
\cellcolor{gray!30} v4 & 1 & 0 & 1 & \cellcolor{gray!30}0 \\
\end{tabular}
\end{center}
::::

:::: {.column width=50%}
Welche Datenstruktur ist geeignet?

\begin{tikzpicture}
  \foreach \y in {0,...,3} {
    \node at (-0.25, 3.5 - \y) {\textbf \y};
  }

  \foreach \y in {0,...,3} {
    \node[anchor=south west, minimum size=1cm, draw] at (0, \y) {};
  }

  \foreach \x in {0,...,3}
    \node at (\x + 2, 4.5) {\textbf \x};

  \foreach \y in {0,...,3} {
    \foreach \x in {0,...,3} {
      \node[anchor=south west, minimum size=1cm, draw] at (1.5 + \x , -0.5 + \y + \y*0.25) {};
    }

    \node[draw, circle, fill, inner sep=1pt] at (0.5, \y + 0.5) {};
    \draw[-Triangle, thick] (0.5, \y + 0.5) -- (1.5, \y + \y*0.25);
  }
\end{tikzpicture}

```java
int[][] matrix = new int[4][4];
```
::::
:::

<!-- FIXME use code in only env -->
## Implementierung einer Adjazenzmatrix

::: {.columns}
:::: {.column width=50%}
`\begin{center}`{=latex}
```{.graphviz dpi=150 height=3.5cm}
graph {
  bgcolor=transparent
  layout=circo
  node [shape=circle]
  nodesep=0.5
  v1 -- v2
  v2 -- v3
  v3 -- v4
  v4 -- v1
}
```
`\end{center}`{=latex}

\begin{center}
\begin{tabular}{c|c|c|c|c}
\rowcolor{gray!30}\cellcolor{gray} & v1 & \cellcolor{teal!30} v2 & v3 & v4 \\
\hline
\cellcolor{gray!30} v1 & \cellcolor{gray!30} 0 & 1 & 0 & 1 \\
\hline
\cellcolor{gray!30} v2 & 1 & \cellcolor{gray!30} 0 & 1 & 0 \\
\hline
\cellcolor{yellow!30} v3 & 0 & \boldred{1} & \cellcolor{gray!30} 0 & 1 \\
\hline
\cellcolor{gray!30} v4 & 1 & 0 & 1 & \cellcolor{gray!30} 0 \\
\end{tabular}
\end{center}
::::

:::: {.column width=50%}
Welche Datenstruktur ist geeignet?

\begin{tikzpicture}
  \foreach \y in {0,...,3} {
    \node at (-0.25, 3.5 - \y) {\textbf \y};
  }

  \foreach \y in {0,...,3} {
    \node[anchor=south west, minimum size=1cm, draw] at (0, \y) {};
  }

  \foreach \x in {0,...,3}
    \node at (\x + 2, 4.5) {\textbf \x};

  \foreach \y in {0,...,3} {
    \foreach \x in {0,...,3} {
      \node[anchor=south west, minimum size=1cm, draw] at (1.5 + \x , -0.5 + \y + \y*0.25) {};
    }

    \node[draw, circle, fill, inner sep=1pt] at (0.5, \y + 0.5) {};
    \draw[-Triangle, thick] (0.5, \y + 0.5) -- (1.5, \y + \y*0.25);
  }

  \node[fill=teal!30] at (3, 4.5) {1};
  \node[fill=yellow!30] at (-0.25, 1.5) {2};
  \node at (3, 1.25) {\boldred{1}};
\end{tikzpicture}

```java
int[][] matrix = new int[4][4];
matrix[2][1] = 1;
```
::::
:::

## \faIcon{desktop} Arbeitsauftrag: Implementierung \hfill Rest der Stunde

Öffne die Online-IDE ([https://online-ide.de](https://online-ide.de)) und den *Adjazenzmatrix*-Workspace.

1. Ergänze die nötige Initialisierung der Attribute `adjazenzmatrix` und `anzKnoten`, im Konstruktor.
2. Befülle die Matrix, sodass sie keine Kanten enthält (`-1`).
3. Implementiere die Methode `kanteEinfuegen(int start, int ziel, int gewicht)`{.java}.
3. Implementiere die Methode `ungerichteteKanteEinfuegen(int knoten1, int knoten2, int gewicht)`{.java}.
5. \faIcon{earlybirds} **Für Schnelle**: Schreibe eine Methode `int pfadLaengeGeben(int[] pfad)`{.java}, die die Länge des Pfades zurückgibt.