Book a Demo!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In
Download

📚 The CoCalc Library - books, templates and other resources

132931 views
License: OTHER
Tweet
Share
Share
1
\subsection{Grundlagen}

2
\begin{frame}{Graph}

3
\begin{block}{Graph}

4
Ein Graph ist ein Tupel $(E, K)$, wobei $E \neq \emptyset$ die Eckenmenge und

5
$K \subseteq E \times E$ die

6
Kantenmenge bezeichnet.

7
\end{block}

8
\pause

9
\tikzstyle{vertex}=[draw,fill=black,circle,minimum size=10pt,inner sep=0pt]

10


11
\begin{gallery}

12
    \galleryimage[Green]{graphs/graph-1}

13
    \galleryimage[Green]{graphs/graph-2}

14
    \galleryimage[Green]{graphs/k-3-3}

15
    \galleryimage[Green]{graphs/k-5}\\

16
    \galleryimage[Green]{graphs/k-16}

17
    \galleryimage[Green]{graphs/graph-6}

18
    \galleryimage[Green]{graphs/star-graph}

19
    \galleryimage[Green]{graphs/tree}

20
\end{gallery}

21
\end{frame}

22


23
\begin{frame}{Synonyme}

24


25
\begin{center}

26
\Huge{Knoten $\Leftrightarrow$ Ecken}

27
\end{center}

28


29
\end{frame}

30


31
\framedgraphic{Modellierung, Flüsse, Netzwerke}{../images/Unit_disk_graph.png}

32
\framedgraphic{Karten}{../images/map.png}

33
\framedgraphic{Good Will Hunting}{../images/good-will-hunting.jpg}

34
\framedgraphic{Graham's Number}{../images/hypercube.png}

35


36
\begin{frame}{Isomorphe Graphen}

37
\begin{center}

38
\href{http://www.martin-thoma.de/uni/graph.html}{martin-thoma.de/uni/graph.html}

39
\end{center}

40
\end{frame}

41


42
\begin{frame}{Grad einer Ecke}

43
\begin{block}{Grad einer Ecke}

44
Der \textbf{Grad} einer Ecke ist die Anzahl der Kanten, die von dieser Ecke

45
ausgehen.

46
\end{block}

47


48
\begin{block}{Isolierte Ecke}

49
Hat eine Ecke den Grad 0, so nennt man sie \textbf{isoliert}.

50
\end{block}

51


52
\begin{gallery}

53
    \galleryimage{graphs/graph-1}

54
    \galleryimage{graphs/graph-2}

55
    \galleryimage{graphs/k-3-3}

56
    \galleryimage{graphs/k-5}\\

57
    \galleryimage{graphs/k-16}

58
    \galleryimage{graphs/graph-6}

59
    \galleryimage{graphs/star-graph}

60
    \galleryimage{graphs/tree}

61
\end{gallery}

62
\end{frame}

63


64
\begin{frame}{Schlinge}

65
\begin{block}{Schlinge}

66
Sei $G=(E, K)$ ein Graph und $k=\Set{e_1, e_2} \in K$ eine Kante.

67


68
$k$ heißt \textbf{Schlinge} $:\Leftrightarrow e_1 = e_2$

69
\end{block}

70


71
Ein Graph ohne Schlingen heißt \enquote{schlingenfrei}

72


73
\begin{gallery}

74
    \galleryimage{graphs/graph-1}

75
    \galleryimage{graphs/graph-2-schlinge}

76
    \galleryimage{graphs/k-3-3}

77
    \galleryimage{graphs/k-5-schlinge}

78
\end{gallery}

79
\end{frame}

80


81
\begin{frame}{Aufgabe 1}

82
Zeichnen Sie alle schlingenfreien Graphen mit genau vier Ecken.

83


84
\only<2>{

85
    \begin{gallery}

86
        \galleryimage{aufgabe-1/graph-8}    % vier einzelne Punkte

87
        \galleryimage{aufgabe-1/graph-7}    % nur eine Kante

88
        \galleryimage{aufgabe-1/graph-6}    % zwei Kanten

89
        \galleryimage{aufgabe-1/graph-11}   % zwei Kanten -------------

90
        \galleryimage{aufgabe-1/graph-12}   % drei Kanten: umgedrehtes u

91
        \galleryimage{aufgabe-1/graph-5}    % drei Kanten

92
        \galleryimage[red]{aufgabe-1/graph-4}    % drei Kanten: S3 - fehlt im Buch

93
        \galleryimage{aufgabe-1/graph-10}   % vier Kanten: Viereck

94
        \galleryimage{aufgabe-1/graph-3}    % vier Kanten: Dreieck mit Spitze

95
        \galleryimage[red]{aufgabe-1/graph-2} % fünf kanten - fehlt im Buch

96
        \galleryimage{aufgabe-1/graph-9}    %  fünf Kanten: nur Diagonale fehlt

97
        \galleryimage{aufgabe-1/graph-1}    % sechs Kanten: K_4

98
    \end{gallery}

99
}

100
\end{frame}

101


102
\begin{frame}{Inzidenz}

103
\begin{block}{Inzidenz}

104
Sei $e \in E$ und $k = \Set{e_1, e_2} \in K$.

105


106
$e$ heißt \textbf{inzident} zu $k :\Leftrightarrow e = e_1$ oder $e = e_2$

107
\end{block}

108


109
\pause

110
\tikzstyle{vertex}=[draw,fill=black,circle,minimum size=10pt,inner sep=0pt]

111


112
\begin{gallery}

113
    \galleryimage[Green]{inzidenz/graph-1}

114
    \galleryimage[Green]{inzidenz/graph-2}

115
    \galleryimage[Green]{inzidenz/k-3-3}

116
    \galleryimage[Green]{inzidenz/k-5}\\

117
    \galleryimage[Green]{inzidenz/k-16}

118
    \galleryimage[red]{inzidenz/graph-6}

119
    \galleryimage[Green]{inzidenz/star-graph}

120
    \galleryimage[Green]{inzidenz/tree}

121
\end{gallery}

122
\end{frame}

123


124