\documentclass[12pt]{amsart} 
\usepackage[dvips]{graphics, color}
\theoremstyle{plain}

\newtheorem{theorem}{Theorem}[section]
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}

\theoremstyle{lemma}
\newtheorem{lemma}[theorem]{Lemma}
\theoremstyle{exempel}
\newtheorem{exempel}[theorem]{Exempel}
\theoremstyle{corollary}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{proposition}
\newtheorem{proposition}[theorem]{{Proposition}}
\theoremstyle{clam}
\newtheorem{clam}[theorem]{Claim}
\theoremstyle{conjecture}
\newtheorem{con}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{re}[theorem]{{Remark}}
\newtheorem{no}[theorem]{Notation}



\newtheorem{quest}[theorem]{Question}

\newtheorem{problem}[theorem]{Problem}





\newtheorem{worning}[theorem]{{\rm W\sc orning}}

\newtheorem{para}[theorem]{}

\newtheorem{examp}[theorem]{Example}

\newtheorem{exercise}[theorem]{Exercise}

\newcommand\pn[1]{{\mathbb P}^{#1}}
\newcommand\cal[1]{\mathcal {#1}}
\newcommand\cL{\mathcal L}
\newcommand\cZ{\mathcal Z}
\newcommand\cO[1]{\cal{O}_{\cal{{#1}}}}
\newcommand\X[1]{X^{[{#1}]}}
\newcommand\zed{{\mathbb Z}}
\newcommand\nat{{\mathbb N}}
\newcommand\rat{{\mathbb Q}}
\newcommand\real{{\mathbb R}}
%\newcommand\a{{\aa}}
\textwidth16cm
\textheight20cm
\oddsidemargin-0.3cm
\evensidemargin0.4cm
%\pagestyle{plain} 
\newtheorem{Definition}{\sf Definition}

�\title{Lektion 03-24}

\begin{document}
\maketitle

L�t $a,b$ vara noder i en graph $G$. En {\bf v\"ag} fr\aa n $a$ till $b$ defineras som en elternande foljd av noder och kanter 
$$a=a_0, e_1, a_1, e_2, ... ,e+n,a_n=b$$
s\aa dan att $e_i=a_{i-1}a_i$ och s\aa dan att inte anv\"ander samma kant flera g\aa nger. Talet $n$ kallas v\"agens l\"angt.

Vi ska betekna v\"agen bara med $a_1a_2...a_n$.

\begin{itemize}
\item Tv{\aa} noder $a$ och $b$ kallas {\bf grannar} om $ab$ \"ar en kant i grafen.
\item En v\"ag som passerar varje nod h\"ogst en g\aa ng kallas en {\bf enkel v\"ag} eller en stig.
\item En v\"ag som b\"orjar och slutar i samma nod och som passerar andra noder h\"ogst en g\aa ng kallas en {\bf cykel}.
\item En v\"ag som inte \"ar en cykel kallas en {\bf oppen v\"ag}.
\end{itemize}

�\vspace{.2in}

\noindent {\it Exempel.} 

$K_5: $ \hspace{.2in}\setlength{\unitlength}{1.5cm}
\begin{picture}(3,2.5)
\put(1,0){\circle*{0.1}}
\put(.9,-.3){e}
\put(0,1){\circle*{0.1}}
\put(-.2,1){c}
\put(2,0){\circle*{0.1}}
\put(2,-.2){d}
\put(2,2){\circle*{0.1}}
\put(2.1,2.1){a}
\put(3,1){\circle*{0.1}}
\put(3.2,1){b}
\put(1,0){\line(1,0){1}}
\put(1,0){\line(-1,1){1}}
\put(1,0){\line(1,2){1}}
\put(2,0){\line(1,1){1}}
\put(2,0){\line(0,2){2}}
\put(3,1){\vector(-1,0){3}}
\put(0,1){\line(2,1){2}}
\put(2,2){\vector(1,-1){1}}
\put(0,1){\vector(2,-1){2}}
%\put(2,0){\line(-2,1){2}}
\put(1,0){\line(2,1){2}}
\end{picture}

\vspace{.1in}


$abcde$ \"ar en enkel oppen v\"ag fr\aa n $a$ till $e$, av l\"angt $4$.\\
$abcdbe$ \"ar en icke-enkel v\"ag fr\aa n $a$ till $e$ �av l\"angt $5$.\\
{\it \"Ovning:} Ber\"akna alla cyklar i $K_5$.




{\bf Avst\aa ndet} mellan tv{\aa} noder $a,b$ \"ar l\"angden av den kortaste v\"ag fr\aa n $a$ till $b$. Vi ska betekna det med:
$av(a,b)$

\vspace{.2in}

\noindent {\it Exempel.} 
\begin{itemize}
\item Avst\aa ndet mellan varje par noder i $K_n$ \"ar lika med $1$.
\item Betrakta grafen $W_4$:
\setlength{\unitlength}{1.5cm}
\begin{picture}(3,2.5)
\put(1,0){\circle*{0.1}}
\put(.7,0){a}
\put(0,1){\circle*{0.1}}
\put(0,1.2){b}
\put(2,0){\circle*{0.1}}
\put(2.2,0){c}
\put(2,2){\circle*{0.1}}
\put(2,2.1){d}
\put(3,1){\circle*{0.1}}
\put(3.1,1){e}
\put(1,0){\line(1,0){1}}
\put(1,0){\line(-1,1){1}}
\put(1,0){\line(1,2){1}}
\put(2,0){\line(1,1){1}}
\put(2,0){\line(0,2){2}}
\put(0,1){\line(1,0){3}}
\put(0,1){\line(2,1){2}}
\put(2,2){\line(1,-1){1}}
\end{picture}
$av(d,e)=1$, $av(e,a)=2$.
\end{itemize}
\newpage

\begin{definition}
L\aa t $G=(V,E)$ vara en enkel graf och $v\in V$ vara en nod av $G$. Med {\bf valensen} eller {\bf graden } av $v$, $deg(v)$, menas antalet kanter som \"ar \"andpunkt i $v$.
\end{definition}

\vspace{.2in}

\noindent {\it Exempel.} 

F\"or varje nod $v$ i $K_n$ g\"aller $deg(v)=n-1$.
�
Valencer av noder ber\aa r p{\aa} antalet kanter, p{\aa} grund av f\"oljande satsen:

\vspace{.2in}

\noindent{\it SATS.} L\aa t $G=(V,E)$ vara en enkel graf. D{\aa} \"ar:
$$\sum_{v\in V} deg(v)=2|E|$$

\noindent{\it Bevis.} Varje kant $e=ab$ ger bidraget $1$ till $deg(a)$ och $deg(b)$. S{\aa} varje kant ger bidraget $2$ till $\sum_{v\in V}deg(v)$.

\vspace{.2in}

\noindent {\it Exempel.} \begin{itemize}
\item Det \"ar klart att om en graf har $n$ noder \"ar $0\leq deg(v)\leq n-1$ f\"or varje nod $v$.

Om en graf $G$ har $n$ noder och $deg(v)= n-1$ f\"or varje nod i $G$ \"ar alla par noder f\"orbunda. S{\aa} $G=K_n$.

Om $G\neq K_n$ kan man s\"aga att $deg(v)\leq n-2$ f\"or n\aa gon nod i $G$.

\item Om en graf har alla noder med udd grad s{\aa} \"ar antalet noder j\"amt.
\item En enkel graf har $20$ kanter, och alla noder har samma grad. Hur m\aa nga noder har grafen?

Antag att grafen har $n$ stycken noder och $deg(v)=k$ f\"or varje nod $v$. Det g\"aller att
$$kn=2\cdot 20=2^3\cdot 5$$
Det finns allts{\aa} $4$ olika alternativ:
\begin{enumerate}
\item $n=40,k=1$:\setlength{\unitlength}{1cm}
\begin{picture}(5,1.5)
\put(0,0){\circle*{0.1}}
\put(0.5,0){\circle*{0.1}}
\put(1,0){\circle*{0.1}}
\put(1.5,0){\circle*{0.1}}
\put(2,0){\circle*{0.1}}
\put(2.5,0){\circle*{0.1}}
\put(3,0){\circle*{0.1}}
\put(3.5,0){\circle*{0.1}}
\put(4,0){\circle*{0.1}}
\put(4.5,0){\circle*{0.1}}
\put(5,0){\circle*{0.1}}
\put(5.5,0){\circle*{0.1}}
\put(6,0){\circle*{0.1}}
\put(6.5,0){\circle*{0.1}}
\put(7,0){\circle*{0.1}}
\put(7.5,0){\circle*{0.1}}
\put(8,0){\circle*{0.1}}
\put(8.5,0){\circle*{0.1}}
\put(9,0){\circle*{0.1}}
\put(9.5,0){\circle*{0.1}}
\put(0,1){\circle*{0.1}}
\put(0.5,1){\circle*{0.1}}
\put(1,1){\circle*{0.1}}
\put(1.5,1){\circle*{0.1}}
\put(2,1){\circle*{0.1}}
\put(2.5,1){\circle*{0.1}}
\put(3,1){\circle*{0.1}}
\put(3.5,1){\circle*{0.1}}
\put(4,1){\circle*{0.1}}
\put(4.5,1){\circle*{0.1}}

\put(5,1){\circle*{0.1}}
\put(5.5,1){\circle*{0.1}}
\put(6,1){\circle*{0.1}}
\put(6.5,1){\circle*{0.1}}
\put(7,1){\circle*{0.1}}
\put(7.5,1){\circle*{0.1}}
\put(8,1){\circle*{0.1}}
\put(8.5,1){\circle*{0.1}}
\put(9,1){\circle*{0.1}}
\put(9.5,1){\circle*{0.1}}
\put(0,1){\circle*{0.1}}
\put(0,0){\line(0,1){1}}
\put(0.5,0){\line(0,1){1}}
\put(1,0){\line(0,1){1}}
\put(1.5,0){\line(0,1){1}}
\put(2,0){\line(0,1){1}}
\put(2.5,0){\line(0,1){1}}
\put(3,0){\line(0,1){1}}
\put(3.5,0){\line(0,1){1}}
\put(4,0){\line(0,1){1}}
\put(4.5,0){\line(0,1){1}}
\put(5,0){\line(0,1){1}}
\put(5.5,0){\line(0,1){1}}
\put(6,0){\line(0,1){1}}
\put(6.5,0){\line(0,1){1}}
\put(7,0){\line(0,1){1}}
\put(7.5,0){\line(0,1){1}}
\put(8,0){\line(0,1){1}}
\put(8.5,0){\line(0,1){1}}
\put(9,0){\line(0,1){1}}
\put(9.5,0){\line(0,1){1}}
\end{picture}
\item $n=20, k=2$\setlength{\unitlength}{1cm}
\begin{picture}(5,1.5)
\put(0,0){\circle*{0.1}}
\put(0.5,0){\circle*{0.1}}
\put(1,0){\circle*{0.1}}
\put(1.5,0){\circle*{0.1}}
\put(2,0){\circle*{0.1}}
\put(2.5,0){\circle*{0.1}}
\put(3,0){\circle*{0.1}}
\put(3.5,0){\circle*{0.1}}
\put(4,0){\circle*{0.1}}
\put(4.5,0){\circle*{0.1}}
\put(0,1){\circle*{0.1}}
\put(0.5,1){\circle*{0.1}}
\put(1,1){\circle*{0.1}}
\put(1.5,1){\circle*{0.1}}
\put(2,1){\circle*{0.1}}
\put(2.5,1){\circle*{0.1}}
\put(3,1){\circle*{0.1}}
\put(3.5,1){\circle*{0.1}}
\put(4,1){\circle*{0.1}}
\put(4.5,1){\circle*{0.1}}
\put(0,0){\line(1,0){.5}}
\put(.5,0){\line(1,0){.5}}
\put(1,0){\line(1,0){.5}}
\put(1.5,0){\line(1,0){.5}}
\put(2,0){\line(1,0){.5}}
\put(2.5,0){\line(1,0){.5}}
\put(3,0){\line(1,0){.5}}
\put(3.5,0){\line(1,0){.5}}
\put(4,0){\line(1,0){.5}}
\put(4.5,0){\line(0,1){1}}
\put(0,1){\line(1,0){.5}}
\put(0.5,1){\line(1,0){.5}}
\put(1,1){\line(1,0){.5}}
\put(1.5,0){\line(1,0){.5}}
\put(2,0){\line(1,0){.5}}
\put(2.5,1){\line(1,0){.5}}
\put(3,1){\line(1,0){.5}}
\put(3.5,1){\line(1,0){.5}}
\put(4,1){\line(1,0){.5}}
\put(0,0){\line(0,1){1}}
\end{picture}
\item $n=10, k=4$:\setlength{\unitlength}{1cm}
\begin{picture}(5,2)
\put(0,0){\circle*{0.1}}
\put(1,0){\circle*{0.1}}
\put(2,0){\circle*{0.1}}
\put(3,0){\circle*{0.1}}
\put(4,0){\circle*{0.1}}
\put(0,1){\circle*{0.1}}
\put(1,1){\circle*{0.1}}
\put(2,1){\circle*{0.1}}
\put(3,1){\circle*{0.1}}
\put(4,1){\circle*{0.1}}
\put(0,0){\line(1,0){1}}
\put(1,0){\line(1,0){1}}
\put(1,0){\line(0,1){1}}
\put(1,0){\line(-1,1){1}}
\put(2,0){\line(1,0){1}}
\put(2,0){\line(0,1){1}}
\put(2,0){\line(-1,1){1}}
\put(3,0){\line(1,0){1}}
\put(3,0){\line(0,1){1}}
\put(3,0){\line(-1,1){1}}
\put(4,0){\line(0,1){1}}
\put(4,0){\line(-1,1){1}}
\put(0,1){\line(1,0){1}}
\put(1,1){\line(1,0){1}}
\put(2,1){\line(1,0){1}}
\put(3,1){\line(1,0){1}}
%\put(4,1){\line(1,0){1}}
\put(0,0){\line(0,1){1}}
\qbezier(0,0),(2,-.5)(4,0)
\qbezier(0,1),(2,1.5)(4,1)
\put(0,0){\line(4,1){4}}
\end{picture}
\item $n=8,k=5$\setlength{\unitlength}{1cm}
\begin{picture}(5,2.5)
\put(0,0){\circle*{0.1}}
\put(1,0){\circle*{0.1}}
\put(2,0){\circle*{0.1}}
\put(0,1){\circle*{0.1}}
\put(2,1){\circle*{0.1}}
\put(0,2){\circle*{0.1}}
\put(1,2){\circle*{0.1}}
\put(2,2){\circle*{0.1}}
\put(0,0){\line(1,0){1}}
\put(0,0){\line(0,1){1}}
\put(0,0){\line(1,1){2}}
\qbezier(0,0),(1,-.5)(2,0)
\qbezier(0,0),(-.5,1)(0,2)
\put(1,0){\line(1,0){1}}
\put(1,0){\line(0,1){2}}
\put(1,0){\line(1,1){1}}
\put(1,0){\line(-1,1){1}}
\put(2,0){\line(-1,1){2}}
\put(2,0){\line(0,1){1}}
\qbezier(2,0),(2.5,1)(2,2)
\put(0,1){\line(0,1){1}}
\put(0,1){\line(1,0){2}}
\put(2,1){\line(-1,1){1}}
\put(0,1){\line(1,1){1}}
\put(2,1){\line(0,1){1}}
\put(0,2){\line(1,0){2}}
\qbezier(0,2),(1,2.5)(2,2)
\end{picture}
\end{enumerate}

\end{itemize}

\vspace{.2in}

Grafen (a) \"ar en ej-sammanh\"angande (connected) �och har $20$ komponenter.
\begin{definition}
En graf kallas {\bf sammanh\"angande} om varje tv{\aa} noder kan f\"orbindas.
\end{definition}
En nod som \"ar inte f\"orbindat till ingen annan nod kallas isolerade.
\begin{definition}
L\aa t $G$ vara en graf. D{\aa} kallas grafen $G'=(V',E')$ en {\bf delgraf} till $G$ om $\emptyset\neq V'\subseteq V$ och $E'\subseteq E$.
\end{definition}
Notera att varje graf med $n$ noder kan t\"ankas son en delgraf av en kompletta graf $K_n$. D{\aa} kan vi definera:
\begin{definition}
L\aa t $G$ vara en graf med $n$ noder. Med {\bf komplement} $\overline{G}$ menas den delgraf av $K_n$ som inneh\aa ller alla noder av $G$ och alla kanter som inte finns i $G$.
\end{definition}

\vspace{.1in}

\noindent{\it Exempel.} L\aa t $G$ vara en enkel grak med $n$ noder s\aa dan att $G$ har $175$ kanter och dess komplement $56$ kanter. Brst\"am $n$.

grafen $K_n$ har $n\choose 2$ kanter, dt h\"ar talet m\aa ste vara lika med antalet kanter i $G$ plus antalet kanter i $\overline{G}$:
$$231=175+56={n\choose 2}\,\, \leftrightarrow 231=\frac{n(n-1)}{2}$$
Vi ska l\"osa ekvationen $n^2-n-462=0$ som har l\"osningar $n=22,-21$. Det \"ar klart att $n=-21$ \"ar ejgodk\"ant, s{\aa} svaret \"ar $n=22$.
\section*{\"Ovning}

\begin{enumerate}
\item Sju st\"ader $A,B,C,D,E,F,G$ \"ar f\"orenade med ett v\"agsystem p{\aa} f\"oljande s\"att:
\begin{itemize}
\item En v\"ag g\aa r mellan $A$ och $C$ och passerar d\"arvid $B$.
\item En v\"ag g\aa r fr{\aa}n $C$ till i ordning $D, B,F$.
\item En v\"ag g\aa r fr\aa n $D$ genom $E$ till $A$.
\item en v\"ag g\aa r fr\aa n $F$ till $B$ via $G$.
\item en v\"ag g\aa r mellan $D$ och $G$.
\end{itemize}
\begin{enumerate}
\item Rita en graf med st\"aderna som noder som beskriver denna situation.
\item Ange alla enkla v\"agar fr\aa n $G$ till $A$.
\item \"Ar det m\"ojlight att starta i $C$ och passera samtliga st\"ader precis en g\aa ng och sedan {\aa}terv\"anda till $C$?
\end{enumerate}
\item Best\"am $|V|$ om grafen $G=(V,E)$ har $9$ kanter och varje nod har grad $3$.
\item En viss graf $G$ har $n$ noder, alla av grad $4$, I dess komplement har alla noder grad $6$. Best\"am $n$.
\item Hur m\aa nga delgrafer $H=(V,E)$ i $K_6$ uppfyller $|V|=3$?
\item Antag att grafen $G$ har $20$ stycken kanter och att alla noder har samma grad. Hur m\aa nga noder har grafen?
\item Visa att om $G$ \"ar en sammanh\"angande graf finns det en enkel v\"ag mellan tv{\aa} godtyckliga noder. 
\end{enumerate}

\end{document}
 