notes/school/di-ma/uebung/04/pascal_04.tex

\documentclass[10pt,a4paper]{article}
\usepackage[utf8x]{inputenc}
\usepackage{ucs}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{tikz}
\title{Blatt 04}
\begin{document}

\maketitle
\newpage
\section{Aufgabe 1}
TODO
\section{Aufgabe 2}

\begin{tikzpicture}
\def \n {5}
\def \radius {3cm}
\def \margin {8} % margin in angles, depends on the radius
\node[draw, circle] (a) at (0,1) {a};
\node[draw, circle] (b)  at (1,2) {b};
\node[draw, circle] (c) at (2,2) {c};
\node[draw, circle] (d)  at (3,1) {d};
\node[draw, circle] (e)  at (2,0) {e};
\node[draw, circle] (f)  at (1,0) {f};
\draw (a)--(b);
\draw (a)--(c);
\draw (a)--(d);
\draw (a)--(f);
\draw (b)--(f);
\draw (b)--(e);
\draw (c)--(d);
\draw (d)--(e);
\end{tikzpicture}
\\
\subsection{1.)}
Graph $G=(V,E)$ mit\\
Knotenmenge: $V=\{a,b,c,d,e,f\}$\\
Kantenmenge: $E=
\{
\{a,b\},
\{a,c\},
\{a,d\},
\{a,f\},
\{b,f\},
\{b,e\},
\{c,d\},
\{d,e\}
\}
$
\\
Adjazens-Matrix:\\
\begin{tabular}{c|ccccccc}
& a & b & c & d & e &  f \\
\hline
a & 0 & 1 & 1 & 1 & 0 & 1 \\
b & 1 & 0 & 0 & 0 & 1 & 1 \\
c & 1 & 0 & 0 & 1 & 0 & 0 \\
d & 1 & 0 & 1 & 0 & 1 & 0 \\
e & 0 & 1 & 0 & 1 & 0 & 0 \\
f & 1 & 1 & 0 & 0 & 0 & 0 \\
\end{tabular} 
\\
\\
Inz.-Matrix:\\
\begin{tabular}{c|ccccccccc}
a & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\
b & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\
c & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\
d & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 \\
e & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\
f & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\
\end{tabular} 

\subsection{2.)}
\begin{tikzpicture}
\def \n {5}
\def \radius {3cm}
\def \margin {8} % margin in angles, depends on the radius
\node[draw, circle] (a) at (3,2) {a};
\node[draw, circle] (b)  at (1,1) {b};
\node[draw, circle] (c) at (2,1) {c};
\node[draw, circle] (d)  at (3,1) {d};
\node[draw, circle] (f)  at (4,1) {f};
\node[draw, circle] (e)  at (0,0) {e};

\draw (a)--(b);
\draw (a)--(c);
\draw (a)--(d);
\draw (a)--(f);
\draw (b)--(e);
\end{tikzpicture}
\\
$G \setminus \{\{b,f\},\{c,d\},\{d,e\}\}$

\begin{tikzpicture}
\def \n {5}
\def \radius {3cm}
\def \margin {8} % margin in angles, depends on the radius
\node[draw, circle] (b) at (2,2) {b};
\node[draw, circle] (a)  at (1,1) {a};
\node[draw, circle] (f) at (2,1) {f};
\node[draw, circle] (e)  at (3,1) {e};
\node[draw, circle] (c)  at (0,0) {c};
\node[draw, circle] (d)  at (2,0) {d};

\draw (b)--(a);
\draw (b)--(f);
\draw (b)--(e);
\draw (a)--(c);
\draw (a)--(d);

\end{tikzpicture}
\\
$G \setminus \{\{a,f\},\{c,d\},\{d,e\}\}$






\section{Aufgabe 3}


\begin{tikzpicture}
\def \n {5}
\def \radius {3cm}
\def \margin {8} % margin in angles, depends on the radius
\node[draw, circle] (1) at (0,1) {1};
\node[draw, circle] (2)  at (1,2) {2};
\node[draw, circle] (4) at (2,2) {4};
\node[draw, circle] (5)  at (3,1) {5};
\node[draw, circle] (6)  at (2,0) {6};
\node[draw, circle] (3)  at (1,0) {3};

\draw [->] 
(1) edge (2)
(1) edge (3)
(2) edge (3)
(3) edge (4)
(4) edge (5)
(5) edge (6)
(6) edge (4);
\end{tikzpicture}

\subsection{1.)}
Graph $G=(V,E)$ mit\\
Knotenmenge: $V=\{1,2,3,4,5,6\}$\\
Kantenmenge: $E=
\{
(1,2),
(1,3),
(2,3),
(3,4),
(4,5),
(5,6),
(6,4)
\}$
\\

Adjazens-Matrix:\\
\begin{tabular}{c|cccccc}
& 1 &  2 & 3 & 4 & 5 & 6 \\
\hline
1 & 0 & 1 & 1 & 0 & 0& 0 \\
2 & 0 & 0 & 1 & 0 & 0& 0 \\
3 & 0 & 0 & 0 & 1 & 0& 0 \\
4 & 0 & 0 & 0 & 0 & 1& 0 \\
5 & 0 & 0 & 0 & 0 & 0& 1 \\
6 & 0 & 0 & 0 & 1 & 0& 0 \\
\end{tabular}
\\
Inzid.-Matrix:\\
\begin{tabular}{c|ccccccc}
1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\
2 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\
3 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\
4 & 0 & 0 & 0 & 1 & 1 & 0 & 1 \\
5 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\
6 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\
\end{tabular}
\subsection{2.)}
\begin{tikzpicture}
\def \n {5}
\def \radius {3cm}
\def \margin {8} % margin in angles, depends on the radius
\node[draw, circle] (1) at (0,1) {1};
\node[draw, circle] (4) at (2,2) {4};
\node[draw, circle] (6)  at (2,0) {6};
\node[draw, circle] (3)  at (1,0) {3};
\draw [->] 
(1) edge (3)
(3) edge (4)
(6) edge (4);
\end{tikzpicture}
\\
$V'=\{1,3,4,6\}$\\
\\
\subsection{3.)}
\begin{tikzpicture}
\def \n {5}
\def \radius {3cm}
\def \margin {8} % margin in angles, depends on the radius
\node[draw, circle] (1) at (0,0) {1};
\node[draw, circle] (3) at (1,0) {3};
\node[draw, circle] (4)  at (2,0) {4};
\node[draw, circle] (5)  at (3,0) {5};
\draw [->] 
(1) edge (3)
(3) edge (4)
(4) edge (5);
\end{tikzpicture}
\\
$V'=\{1,3,4,5\}$\\
\section{Aufgabe 4}

Zu zeigen: Wenn ein Baum genau $k \geq 1$ Knoten vom Grad 4 enthält (außer Blätter), dann besitzt der Baum mindestenz $2 \cdot k + 2$ Blätter.\\
\\
IA: Ein Baum mit nur einem Knoten von Grad 4 muss 4 Blätter haben

\begin{tikzpicture}
\node[draw,circle] (1) at (2,1) {1};
\node[draw,circle] (2) at (0,0) {2};
\node[draw,circle] (3) at (1,0) {3};
\node[draw,circle] (4) at (3,0) {4};
\node[draw,circle] (5) at (4,0) {5};

\draw (1)--(2);
\draw (1)--(3);
\draw (1)--(4);
\draw (1)--(5);
\end{tikzpicture}
\\
$A(1) = 2 \cdot 1 + 2 = 4$\\
\\
\textbf{IV: $A(k) = 2 \cdot k +2$}\\
\\
IS: $k \rightarrow k+1$\\
Um einen Knoten mit Grad 4 hinzuzufügen, kann man nun eines der Blätter nehmen und drei Blätter anhängen. Man bekommt also 3 Blätter hinzu, verliert aber auch eines, da dieses zum neuen Knoten wird.\\
\\
$A(k+1) = A(k) + 3 - 1 \overset{(IV)}{=} (2 \cdot k+2)+3-1$ 
$= 2 \cdot (k+1)+2$\\
q.e.d
\end{document}