--- header-includes: | \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. \pause \begin{tikzpicture}[overlay, remember picture] \node[rotate=-30,scale=3] at (10, 0) {\large \boldred{Falsch}}; \end{tikzpicture} \pause `int n = 3;`{.java} ## \faIcon{hands-helping} / \faIcon{chalkboard} Arbeitsauftrag: Objekt Erzeugung \hfill{} 2/5 ### Diskutiert folgende Aussage: \vspace{1cm} `\only<1>{`{=latex} > 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. `}`{=latex} `\only<2->{`{=latex} > 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 \boldred{der Klasse}. `}`{=latex} \only<2->{ \begin{tikzpicture}[overlay, remember picture] \node[rotate=-30,scale=3] at (10, 0) {\large \boldred{Falsch}}; \end{tikzpicture} } \pause `Auto a1 = new Auto();`{.java} ## \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..*}{}; \only<2>{ \node[rotate=-30,scale=3] at (6, 1) {\large \boldred{Falsch}}; } \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. :::: ::: \only<2>{ \begin{tikzpicture}[overlay, remember picture] \node[rotate=-30,scale=3] at (10.5, 2.5) {\large \boldred{Falsch}}; \end{tikzpicture} } ## \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! \only<2>{ \begin{tikzpicture}[overlay, remember picture] \node[rotate=-30,scale=3] at (10, 2) {\large \boldred{Falsch}}; \draw[red] (8, 4.2) -- (9, 4.2); \draw[red] (0, 4.2) -- (1, 4.2); \end{tikzpicture} } ## 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} ## 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} Übung - Big Bad Joe ::: {.columns align=center} :::: {.column width=50%} Bearbeite die ersten vier Seiten (*Wege*) auf folgender Webseite: :::: :::: {.column width=50%} ![](img/matheprisma_qrcode.png){.center height=60%} :::: ::: [https://www.matheprisma.uni-wuppertal.de/Module/Graphen/index.htm](https://www.matheprisma.uni-wuppertal.de/Module/Graphen/index.htm) ## \faIcon{desktop} Was haben wir gelernt? {.standout} \Huge QUIZ