path: root/Info/11/NTG/1/Intro/slides.md

---
header-includes: |
    \makeatletter
    \beamer@ignorenonframefalse
    \makeatother
    \usepackage[most]{tcolorbox}
    \usetikzlibrary {decorations.markings}
---

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

### Diskutiert folgende Aussage:

\vspace{1cm}
> Damit der Computer sich etwas merken kann, muss eine Variable oder ein Attribut zuerst **initialisiert** und dann **deklariert** werden.
> Die beiden Schritten sind [immer]{.underline} von einander getrennt und dürfen [niemals]{.niemals} in der selben Zeile stehen.

## \faIcon{hands-helping} / \faIcon{chalkboard} Arbeitsauftrag: Objekt Erzeugung \hfill{} 2/5

### Diskutiert folgende Aussage:

\vspace{1cm}
> Die besondere Methode, die Objekte einer Klasse erzeugt, heißt **Konstruktor**, weil sie ein neues Objekt *konstruiert*.
> In Java hat der Konstruktor immer den Namen `new`{.java}, da ein **neues** Objekt erzeugt wird.

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

### Diskutiert folgende Aussage:

\vspace{1cm}
> Im folgenden Klassendiagramm erbt die Klasse `Person` von der Klasse `Lebewesen` und die Klasse `Gruppe` erbt von der Klasse `Person`.

\begin{center}
\begin{tikzpicture}
\begin{class}[text width=3cm]{Lebewesen}{0, 3}
\attribute{alter}
\operation{bewegen()}
\end{class}

\begin{class}[text width=3cm]{Person}{0, 0}
\attribute{name}
\inherit{Lebewesen}
\end{class}

\begin{class}[text width=3cm]{Gruppe}{6, 0}
\attribute{mitglieder}
\end{class}

\association{Person}{}{0..n}{Gruppe}{2..*}{};
\end{tikzpicture}
\end{center}

## \faIcon{hands-helping} / \faIcon{chalkboard} Arbeitsauftrag: Code verstehen \hfill{} 4/5

### Diskutiert folgende Aussage:

::: {.columns}
:::: {.column width=45%}
```java
int[] zahlen = {3, 6, 2, 7, 1};
for (int i = zahlen.length - 1; i > 1; i--) {
  println(zahlen[i]);
}

```
::::

:::: {.column width=55%}
\vspace{2.5cm}
> Der Code gibt [alle]{.underline} Einträge des Arrays `zahlen` absteigend sortiert aus.
::::
:::

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

### Diskutiert folgende Aussage:

::: {.columns}
:::: {.column width=45%}
```java
class A {
  int a;
  A() { a = 42; }
  void gibAus() {
    println(a);
  }
}
```
::::

:::: {.column width=55%}
```java
class B extends A {
  B(int b) {
    super(b);
    gibAus();
  }
}
```
::::
:::

\vspace{1cm}
> Dieser Code ist ein korrektes Java Programm!


## Worum gehts heute?

\begin{center}
\begin{tikzpicture}
\only<1> {
  \node[rotate=-2] {\Huge{Grafen}};
}
\only<2,3>{
  \node[rotate=3] at (0, 0) {\includegraphics[keepaspectratio, width=6cm]{img/vlad_tepes_002.jpg}};
}
\only<4> { \node[rotate=-1] {\Huge{Graph\underline{en}}};
}
\only<5,6> {
  \node[rotate=-2] {\includegraphics[keepaspectratio, width=8cm]{img/graphen.jpg}};
}
\only<3, 6> {
  \draw[red, line width=2pt] (-3.5, -3.5) -- (3.5, 3.5) (3.5, -3.5) -- (-3.5, 3.5);
}
\end{tikzpicture}
\end{center}

##

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

##

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

## \faIcon{pencil-alt} Graphen

\pause
Ein \boldred{Graph} besteht aus einer endlichen Menge von \boldred{Knoten V} (engl. vertices) und einer endlichen Menge von \boldred{Kanten E} (engl. edges).

\pause

\vspace{0.5cm}
Jede Kante verbindet **genau zwei** \boldred{Knoten}, die man auch als \boldred{Nachbarknoten} bezeichnet.

## Beispiele {.standout}

Was lässt sich als Graph darstellen?

## \faIcon{pencil-alt} Beispiel

\begin{tikzpicture}[edge/.style = {}, path/.style={}, cycle/.style={}, blocked/.style={}]
\node[align=center] at (10, 5) {\begin{tabular}{r l} \textbf{V} = & \{Nürnberg, \\ & Feucht, \\ & Wendelstein, \\ & ..., München\} \end{tabular}};
\node at (5, 4) {\resizebox{!}{7cm}{\input{graph.tikz}}};
\node[align=center] at (0, 2) {\begin{tabular}{r l} \textbf{E} = & \{Nürnberg- \\ &Wendelstein, \\ & Nürnberg- \\ & Feucht, ... \} \end{tabular}};
\end{tikzpicture}

## Wege durch Graphen

::: {.columns align=center}
:::: {.column width=50%}
Manchmal gibt es nur in eine Richtung einen Radweg und das Fahren in der Gegenrichtung wäre zu gefährlich.  

\vspace{0.5cm}
Beschreibe wie sich diese Gegebenheit mithilfe des Graphen darstellen ließe.

\vspace{0.5cm}
\only<1>{
  {\Large \phantom{$\Rightarrow$ Graph mit \boldred{gerichteten} Kanten}}
}
\only<2>{
  {\Large $\Rightarrow$ Graph mit \boldred{gerichteten} Kanten}
}
::::

:::: {.column width=50%}

\resizebox{\textwidth}{!}{
  \tikzstyle{path} = []
  \tikzstyle{cycle} = []
  \tikzstyle{blocked} = []
\only<1> {
  \tikzstyle{edge} = []
  \input{graph.tikz}
}
\only<2> {
  \tikzstyle{edge} = [-Latex]
  \input{graph.tikz}
}
}

::::
:::

## Wege durch Graphen
::: {.columns align=center}
:::: {.column width=50%}
Aufgrund von unterschiedlichen Distanzen zwischen zwei Orten und Steigungen/Gefällen benötigt ein Radfahrer unterschiedlich lange für die verschiedenen Fahrten zwischen zwei Orten.

\vspace{0.5cm}
Beschreibe wie sich diese Gegebenheit mithilfe des Graphen darstellen ließe.

\vspace{0.5cm}
\only<1>{
  {\Large \phantom{$\Rightarrow$ \boldred{Kantengewichte}}}
}
\only<2>{
  {\Large $\Rightarrow$ \boldred{Kantengewichte}}
}
::::

:::: {.column width=50%}

\resizebox{\textwidth}{!}{
\only<1> {
  \tikzstyle{blocked} = []
  \tikzstyle{path} = []
  \tikzstyle{cycle} = []
  \tikzstyle{edge} = [-Latex]
  \input{graph.tikz}
}
\only<2> {
  \input{weighted_graph.tikz}
}
}

::::
:::

## \faIcon{pencil-alt} Kanten von Graphen

Die Kanten eines Graphen können ...

* \boldred{gerichtet} oder \boldred{ungerichtet} sein.
* eine \boldred{Gewichtung} haben oder nicht.

\pause
\vspace{0.2cm}
![](img/Copyrighted/graphs.png){.center}

<!-- ::: {.columns} -->
<!-- :::: {.column width=33%} -->
<!-- \begin{center} -->
<!-- \textbf{ungerichtet} -->

<!-- \begin{tikzpicture}[vert/.style={draw, circle}] -->
<!-- \node[vert] (a) {A}; -->
<!-- \node[vert, below left=of a] (b) {B}; -->
<!-- \draw (a) -- (b); -->
<!-- \node[vert, right=of b] (c) {C}; -->
<!-- \draw (a) -- (c); -->
<!-- \node[vert, right=of c] (d) {D}; -->
<!-- \draw (a) -- (d); -->
<!-- \node[vert, below=of c] (e) {E}; -->
<!-- \draw (c) -- (e); -->
<!-- \node[vert, below=of d] (f) {F}; -->
<!-- \draw (d) -- (f); -->
<!-- \end{tikzpicture} -->
<!-- \end{center} -->
<!-- :::: -->

<!-- :::: {.column width=33%} -->
<!-- **gerichtet** -->
<!-- ```{.graphviz} -->
<!-- digraph { -->
  <!-- bgcolor=transparent -->
  <!-- size=5 -->
  <!-- A -> B -->
  <!-- A -> C -->
  <!-- A -> D -->
  <!-- C -> E -->
  <!-- E -> C -->
  <!-- D -> F -->
  <!-- F -> D -->
<!-- } -->
<!-- ``` -->
<!-- :::: -->

<!-- :::: {.column width=33%} -->
<!-- **gewichtet** -->
<!-- ```{.graphviz} -->
<!-- graph { -->
  <!-- bgcolor=transparent -->
  <!-- size=5 -->
  <!-- A -- B [label=10, len=1] -->
  <!-- A -- C [label=15, len=1] -->
  <!-- A -- D [label=20, len=1] -->
  <!-- C -- E [label=30, len=1] -->
  <!-- D -- F [label=20, len=1] -->
<!-- } -->
<!-- ``` -->
<!-- :::: -->
<!-- ::: -->

## Wege durch Graphen

::: {.columns align=center}
:::: {.column width=50%}
Ein \boldred{Pfad (bzw. Weg)} ist eine Folge von Knoten, wobei aufeinanderfolgende Knoten
durch eine Kante miteinander verbunden sind.
::::

:::: {.column width=50%}

\resizebox{\textwidth}{!}{
  \tikzstyle{edge} = []
  \tikzstyle{path} = [draw=blue, thick]
  \tikzstyle{cycle} = []
  \tikzstyle{blocked} = []
  \input{graph.tikz}
}
::::
:::

## Wege durch Graphen

Als \boldred{Länge} eines Pfades bezeichnet man bei ... 

* \boldred{ungewichteten} Graphen die Anzahl der durchlaufenden Kanten
* \boldred{gewichteten} Graphen die Summe der Kantengewichte der durchlaufenden Kanten

## Beispiele

::: {.columns}
:::: {.column width=55%}
Gib die Länge folgender Pfade an:

\begin{tcolorbox}[enhanced,title=1,
  attach boxed title to top left={yshift=-\tcboxedtitleheight/2},
  boxed title style={size=small,colback=blue}]
Wendelstein - Postbauer-Heng - \\ Beilngries - Ingolstadt - Greding
\end{tcolorbox}

\begin{tcolorbox}[enhanced,title=2,
  attach boxed title to top left={yshift=-\tcboxedtitleheight/2},
  boxed title style={size=small,colback=blue}]
Feucht - Neumark i. d. O. - Beilngries~- Kelheim - München - Ingolstadt - Greding
\end{tcolorbox}
::::

:::: {.column width=45%}
\resizebox{\textwidth}{!}{
  \tikzstyle{edge} = []
  \tikzstyle{path} = []
  \tikzstyle{cycle} = []
  \tikzstyle{blocked} = []
  \input{graph.tikz}
}
::::
:::

## Beispiele

::: {.columns}
:::: {.column width=55%}
Gib die Länge folgender Pfade an:

\begin{tcolorbox}[enhanced,title=1,
  attach boxed title to top left={yshift=-\tcboxedtitleheight/2},
  boxed title style={size=small,colback=blue}]
Nürnberg – Wendelstein – Schwanstetten
\end{tcolorbox}

\begin{tcolorbox}[enhanced,title=2,
  attach boxed title to top left={yshift=-\tcboxedtitleheight/2},
  boxed title style={size=small,colback=blue}]
Nürnberg – Wendelstein – \\ Feucht – Nürnberg
\end{tcolorbox}

::::

:::: {.column width=45%}
\resizebox{\textwidth}{!}{
  \input{weighted_graph.tikz}
}
::::
:::

## Wege durch Graphen

::: {.columns align=center}
:::: {.column width=50%}
Ein \boldred{Zyklus (bzw. Kreis)} ist ein einfacher Pfad, bei dem Start- und Zielknoten identisch sind.
::::

:::: {.column width=50%}

\resizebox{\textwidth}{!}{
  \tikzstyle{edge} = []
  \tikzstyle{path} = []
  \tikzstyle{cycle} = [draw=orange, thick]
  \tikzstyle{blocked} = []
  \input{graph.tikz}
}
::::
:::

## Wege durch Graphen

::: {.columns align=center}
:::: {.column width=50%}
Marie hat sich für das Wochenende vorgenommen von Nürnberg nach Kelheim zu radeln.
Am Morgen liest sie jedoch, dass es mehrere Baumaßnahmen gibt:

* Schwanstetten – Greding
* Postbauer-Heng – Beilngries
* Neumarkt i. d. Oberpfalz – Beilngries

sind gesperrt.

Gib an, ob sie ihr Vorhaben dennoch umsetzen kann.

\vspace{0.5cm}
\only<1>{
  {\Huge \phantom{$\Rightarrow$ Nein!}}
}
\only<2>{
  {\Huge $\Rightarrow$ Nein!}
}
::::

:::: {.column width=50%}
\resizebox{\textwidth}{!}{
  \tikzstyle{edge} = []
  \tikzstyle{path} = []
  \tikzstyle{cycle} = []
  \only<1> {
    \tikzstyle{blocked} = []
    \input{graph.tikz}
  }
  \only<2> {
    \tikzstyle{blocked} = [red, dashed, thick]
    \input{graph.tikz}
  }
}
::::
:::

## \faIcon{pencil-alt} Grundbegriffe und Definitionen

Ein Graph heißt ...

* \boldred{zusammenhängend}, wenn von jedem Knoten zu jedem anderen Knoten mindestens ein Pfad existiert.

![](img/Copyrighted/graphs2.png){.center width=70%}

## \faIcon{hands-helping} Grundbegriffe und Definitionen

Fünf Freunde treffen sich auf einer Party und jeder schüttelt jedem die Hand.

Stellen Sie die beschriebene Situation in einem Graphen dar und geben Sie an, wie viele Händeschüttler es gibt.

\pause

\begin{center}
\begin{tikzpicture}[vert/.style={fill=black, circle, inner sep=0pt, minimum size=0.2cm}]
\node[vert] (a) {};
\node[vert, below left = 0.7cm and 0.7cm of a] (b) {};
\node[vert, below right = 0.7cm and 0.7cm of a] (c) {};
\node[vert, below right = 0.7cm and 0.3cm of b] (d) {};
\node[vert, below left = 0.7cm and 0.3cm of c] (e) {};
\draw (a) -- (b);
\draw (a) -- (c);
\draw (a) -- (d);
\draw (a) -- (e);
\draw (b) -- (c);
\draw (b) -- (d);
\draw (b) -- (e);
\draw (c) -- (d);
\draw (c) -- (e);
\draw (d) -- (e);
\end{tikzpicture}
\end{center}

## \faIcon{pencil-alt} Grundbegriffe und Definitionen

Ein Graph heißt ...

* \boldred{zusammenhängend}, wenn von jedem Knoten zu jedem anderen Knoten mindestens ein Pfad existiert.
* \boldred{vollständig}, wenn je zwei Knoten durch genau eine Kante direkt miteinander verbunden sind.

## \faIcon{desktop} Big Bad Joe

[https://www.matheprisma.uni-wuppertal.de/Module/Graphen/index.htm?3](https://www.matheprisma.uni-wuppertal.de/Module/Graphen/index.htm?3)

## \faIcon{desktop} Was haben wir gelernt? {.standout}

\Huge QUIZ