\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-26}

\begin{document}
\maketitle
\fbox{\fbox{\parbox{15cm}{
Notera att om vi tar en graf $G=(V,E)$ antag vi bara att $\emptyset\neq V$.\\
S{\aa} det \"ar m\"ojligt att f{\aa} ett antal isolerade noder som en graf.
N\"ar vi vill inte ha ett antal isolerade noder som en graf d{\aa} s\"ager vi att  $\emptyset\neq E$.}}}

\vspace{.1in}

L\aa t $G=(V,E)$ vara en enkel graf med $V=\{v_1,...,v_n\}$ och $E=\{k_1,...,k_e\}$. Man kan bilda tv{\aa} matriser f\aa n grafen $G$.
\begin{itemize}
\item En $n\times e$ matrisen $A_G=(a_{ij})$ definerat som:
\[ a_{ij}=\left\{\begin{array}{cc}
1&\text{ om } k_i \text{ \"ar incident till }v_j\\
0& \text{ annars } \end{array} \right. \]
Denna matrisen kallas den {\bf incidensmatrisen}.
\item En $n\times n$ matris, den {\bf grannmatrisen}, $X_G=(x_{ij})$ d\"ar
\[ x_{ij}=\left\{\begin{array}{cc}
1&\text{ om det finns en kant mellan noder }v_i,v_j\\
0& \text{ annars } \end{array} \right. \]
\end{itemize}

\vspace{.1in}\noindent{\it Exempel}. Betrakta grafen $G$:
\hspace{.2in}\setlength{\unitlength}{1.5cm}
\begin{picture}(2.5,2.5)
\put(0,0){\circle*{0.1}}
\put(-.3,0){$v_1$}
\put(1,0){\circle*{0.1}}
\put(1,-.3){$v_2$}
\put(2,0){\circle*{0.1}}
\put(2.1,0){$v_3$}
\put(1,1){\circle*{0.1}}
\put(1.2,1){$v_4$}
\put(1,2){\circle*{0.1}}
\put(1.2,2){$v_5$}
\put(0,0){\line(1,0){1}}
\put(.5,.1){$k_1$}
\put(1,0){\line(1,0){1}}
\put(1.4,.1){$k_2$}
\put(2,0){\line(-1,1){1}}
\put(1.5,.6){$k_3$}
\put(1,1){\line(-1,-1){1}}
\put(.3,.6){$k_5$}
\put(1,1){\line(0,-1){1}}
\put(1.1,.4){$k_4$}
\put(1,1){\line(0,1){1}}
\put(1.1,1.5){$k_6$}
\end{picture}

\vspace{.1in}

\[ A_G=\left( \begin{array}{cccccc}
1&0&0&0&1&0\\
1&1&0&1&0&0\\
0&1&1&0&0&0\\
0&0&1&1&1&1\\
0&0&0&0&0&1
\end{array} \right)
\hspace{.2in} X_G= \left( \begin{array}{ccccc}
0&1&0&1&0\\
1&0&1&1&0\\
0&1&0&1&0\\
1&1&1&0&1\\
0&0&0&1&0
\end{array} \right)
\]

\vspace{.1in}

\noindent{\it Notera:}\begin{itemize}
\item Antalet ettor i en rad av incidensmatricen \"ar lika med graden av motsvarande nod.(Bevisa det)
\item Varje kolumn i incidensmatrisen inneh\aa ller precis tv{\aa} ettor. (Bevisa det)
\item En gannmatris \"ar alltid symmetrisk.
\item Permutation av rader och kolumner i gannmatrisen inneb\"ar bara omnumrering av noderna.
\item Permutation av rader och kolumner i incidenstrisen inneb\"ar bara omnumrering av noderna och kanter.
\end{itemize}

Betrakta grafer  
$G$:\hspace{.2in}\setlength{\unitlength}{1.5cm}
\begin{picture}(2.5,2.5)
\put(0,0){\circle*{0.1}}
\put(1,0){\circle*{0.1}}
\put(0,1){\circle*{0.1}}
\put(1,1){\circle*{0.1}}
\put(0,0){\line(1,0){1}}
\put(1,1){\line(-1,0){1}}
\put(1,1){\line(0,-1){1}}
\put(0,1){\line(-0,-1){1}}
\qbezier(0,0),(1.5,-1)(1,1)
\put(0,1){\line(1,-1){1}}
\end{picture}
$G'$:\hspace{.2in}\setlength{\unitlength}{1.5cm}
\begin{picture}(2.5,3.5)
\put(0,0){\circle*{0.1}}
\put(1,0){\circle*{0.1}}
\put(0,1){\circle*{0.1}}
\put(1,1){\circle*{0.1}}
\put(0,0){\line(1,0){1}}
\put(1,1){\line(-1,0){1}}
\put(1,1){\line(0,-1){1}}
\put(0,1){\line(0,-1){1}}
\put(0,0){\line(1,1){1}}
\put(0,1){\line(1,-1){1}}
\end{picture}

\vspace{.3in}

De ser olika ut med kan ritas p{\aa} samma s\"att. Vi s\"ager att de \"ar isomorfa grafer.

\begin{definition}
Tv{\aa} enkla grafer $G,G'$ \"ar isomorfa, $G\cong G'$, om och endast om matrisen $A_G$ kan f\aa s fr\aa n $A_{G'}$ genom att permutera raderna och kolumner. 
\end{definition}
Det betyder att $G\cong G'$ om och endast om  $A_G=A_{G'}$ efter , eventuellt, vi ger en annan ordning till noder och kanter i grafen $G'$.

Man kan definera en isomorfi mellan grafer $G=(V,E)$ och $G'=(V',E')$, $f: G\to G'$. Det best\aa r av en bijektiv funktion $f:V\to V'$ s{\aa} att:
$$\;\; \text{ f\"or alla }a,b\in V\;ab\in E\leftrightarrow f(a)f(b)\in E'$$

\noindent{\it Notera:}\begin{itemize}
\item Tv{\aa} isomorfa grafer har samma antalet komponenter.
\item Tv{\aa} isomorfa grafer har samma antalet kanter och samma antalet noder.
 \item Motsvarande noder i isomorfa grafer har samma graden!
\item Isomorfa grafer har samma antalet cykler.
\end{itemize}

\vspace{.1in}

\noindent{\it Exempel}. Rita alla icke isomorfa grafer med $4$ noder som finns.

Det finns 11 alternativ.

\setlength{\unitlength}{1.5cm}
\begin{picture}(2.5,2.5)
\put(0,0){\circle*{0.1}}
\put(1,0){\circle*{0.1}}
\put(0,1){\circle*{0.1}}
\put(1,1){\circle*{0.1}}
\end{picture}
\setlength{\unitlength}{1.5cm}
\begin{picture}(2.5,2.5)
\put(0,0){\circle*{0.1}}
\put(1,0){\circle*{0.1}}
\put(0,1){\circle*{0.1}}
\put(1,1){\circle*{0.1}}
\put(0,0){\line(1,0){1}}
%\put(1,1){\line(-1,0){1}}
%\put(1,1){\line(0,-1){1}}
%\put(0,1){\line(0,-1){1}}
%\put(0,0){\line(1,1){1}}
%\put(0,1){\line(1,-1){1}}
\end{picture}
\begin{picture}(2.5,2.5)
\put(0,0){\circle*{0.1}}
\put(1,0){\circle*{0.1}}
\put(0,1){\circle*{0.1}}
\put(1,1){\circle*{0.1}}
\put(0,0){\line(1,0){1}}
\put(1,1){\line(-1,0){1}}
%\put(1,1){\line(0,-1){1}}
%\put(0,1){\line(0,-1){1}}
%\put(0,0){\line(1,1){1}}
%\put(0,1){\line(1,-1){1}}
\end{picture}
\begin{picture}(2.5,2.5)
\put(0,0){\circle*{0.1}}
\put(1,0){\circle*{0.1}}
\put(0,1){\circle*{0.1}}
\put(1,1){\circle*{0.1}}
%\put(0,0){\line(1,0){1}}
\put(1,1){\line(-1,0){1}}
\put(1,1){\line(0,-1){1}}
%\put(0,1){\line(0,-1){1}}
%\put(0,0){\line(1,1){1}}
%\put(0,1){\line(1,-1){1}}
 \end{picture}
\begin{picture}(2.5,2.5)
\put(0,0){\circle*{0.1}}
\put(1,0){\circle*{0.1}}
\put(0,1){\circle*{0.1}}
\put(1,1){\circle*{0.1}}
\put(0,0){\line(1,0){1}}
\put(1,1){\line(-1,0){1}}
\put(1,1){\line(0,-1){1}}
%\put(0,1){\line(0,-1){1}}
%\put(0,0){\line(1,1){1}}
%\put(0,1){\line(1,-1){1}}
\end{picture}
\begin{picture}(2.5,2.5)
\put(0,0){\circle*{0.1}}
\put(1,0){\circle*{0.1}}
\put(0,1){\circle*{0.1}}
\put(1,1){\circle*{0.1}}
%\put(0,0){\line(1,0){1}}
\put(1,1){\line(-1,0){1}}
\put(1,1){\line(0,-1){1}}
%\put(0,1){\line(0,-1){1}}
%\put(0,0){\line(1,1){1}}
\put(0,1){\line(1,-1){1}}
\end{picture}
\begin{picture}(2.5,2.5)
\put(0,0){\circle*{0.1}}
\put(1,0){\circle*{0.1}}
\put(0,1){\circle*{0.1}}
\put(1,1){\circle*{0.1}}
%\put(0,0){\line(1,0){1}}
\put(1,1){\line(-1,0){1}}
%\put(1,1){\line(0,-1){1}}
\put(0,1){\line(0,-1){1}}
%\put(0,0){\line(1,1){1}}
\put(0,1){\line(1,-1){1}}
\end{picture}
\begin{picture}(2.5,2.5)
\put(0,0){\circle*{0.1}}
\put(1,0){\circle*{0.1}}
\put(0,1){\circle*{0.1}}
\put(1,1){\circle*{0.1}}
\put(0,0){\line(1,0){1}}
\put(1,1){\line(-1,0){1}}
\put(1,1){\line(0,-1){1}}
\put(0,1){\line(0,-1){1}}
%\put(0,0){\line(1,1){1}}
%\put(0,1){\line(1,-1){1}}
\end{picture}
\begin{picture}(2.5,2.5)
\put(0,0){\circle*{0.1}}
\put(1,0){\circle*{0.1}}
\put(0,1){\circle*{0.1}}
\put(1,1){\circle*{0.1}}
\put(0,0){\line(1,0){1}}
%\put(1,1){\line(-1,0){1}}
\put(1,1){\line(0,-1){1}}
\put(0,1){\line(0,-1){1}}
%\put(0,0){\line(1,1){1}}
\put(0,1){\line(1,-1){1}}
\end{picture}
\begin{picture}(2.5,2.5)
\put(0,0){\circle*{0.1}}
\put(1,0){\circle*{0.1}}
\put(0,1){\circle*{0.1}}
\put(1,1){\circle*{0.1}}
\put(0,0){\line(1,0){1}}
\put(1,1){\line(-1,0){1}}
\put(1,1){\line(0,-1){1}}
\put(0,1){\line(0,-1){1}}
%\put(0,0){\line(1,1){1}}
\put(0,1){\line(1,-1){1}}
\end{picture}
\begin{picture}(2.5,2.5)
\put(0,0){\circle*{0.1}}
\put(1,0){\circle*{0.1}}
\put(0,1){\circle*{0.1}}
\put(1,1){\circle*{0.1}}
\put(0,0){\line(1,0){1}}
\put(1,1){\line(-1,0){1}}
\put(1,1){\line(0,-1){1}}
\put(0,1){\line(0,-1){1}}
\put(0,0){\line(1,1){1}}
\put(0,1){\line(1,-1){1}}
\end{picture}

 

\begin{definition}\\

\begin{itemize}\\

\item En {\bf hamiltonstig} \"ar en stig some bes\"oker \underline{varje nod}
precis \underline{en g\aa ng}.
\item En hamiltonscykel \"ar en cykel som bes\"oker \underline{varje nod}
en g\aa ng.
\item En {\bf  eulersv\"ag} \"ar en v\"ag som passerar \underline{varje kant} precis \underline{en g\aa ng}.
\item En {\bf eulerkrets} \"ar en sluten v\"ag (en v\"ag som b\"orjar och sultar p\aa samma nod) som passerar \underline{varje kant} precis \underline{en g\aa ng}.
\item En graf kallas {\bf eulersk} om den har en Eulerkrets och kallas {hamiltonsk} om den kar en hamiltonscykel.
\end{itemize}

\end{definition}
Att avg\"ora om en graf \"ar hamiltonsk \"ar j\"attesv\aa rt.

\vspace{.1in}

\noindent{\it Exempel} Betrakta grafen:
\setlength{\unitlength}{1.5cm}
\begin{picture}(5,3)
\put(0,0){\circle*{0.1}}
\put(2,0){\circle*{0.1}}
\put(4,0){\circle*{0.1}}
\put(1,1){\circle*{0.1}}
\put(2,1){\circle*{0.1}}
\put(3,1){\circle*{0.1}}
\put(0,2){\circle*{0.1}}
\put(2,2){\circle*{0.1}}
\put(4,2){\circle*{0.1}}
\put(0,0){\line(1,1){1}}
\put(0,0){\line(0,1){2}}
\put(3,1){\line(1,1){1}}
\put(4,0){\line(0,1){2}}
\put(0,0){\vector(1,0){1.8}}
\put(2,0){\vector(1,0){1.8}}
\put(4,0){\vector(-1,1){0.8}}
\put(3,1){\vector(-1,0){0.8}}
\put(2,1){\vector(-1,0){0.8}}
\put(1,1){\vector(-1,1){0.8}}
\put(0,2){\vector(1,0){1.8}}
\put(2,2){\vector(1,0){1.8}}

\end{picture}

\vspace{.1in}

Den \"ar en emiltonsgraf, men det finns ingen emiltonscykel. F\"or att best\"amma det man m\aa ste f\"ors\"oka att bilda en emiltoncykel fr\aa n varje nod och visa att det \"ar om\"ojligt att g\"ora det.

Det \"ar mycket l\"attare att avg\"ora om en graf \"ar eulersk.

\vspace{.1in}

\noindent{\it STAS 1. En graf $G$ utan isolerade noder har en eulerkrets  om och endast om \"ar sammanh\"angande och har varje nod har j\"amn grad.}

\noindent{\it Bevis.} Antag att $G$ har en eulerkrets, d{\aa} \"ar $G$ sammarh\"angande. Om en graf best\aa r av tv{\aa} komponenter \"ar det om\"ojligt att bilda en sluten v\"ag som passerar varje kant. L\aa t $\gamma=v_0v_1...v_0$ vara en eulerstig i $G$. N\"ar vi g\aa r fr\aa n $a_0$ anv\"ander varje kant, till $v_i$ och fr\aa n $v_i$. Det ger bidraget $2$ varje g\aa ngen till $deg(v_i)$.

Antag nu att $G$ \"ar sammanh\"angande och har varje nod har j\"amn grad. b\"orja med en nod $s$. S\"akert kan man g\aa r vidare och bilda en stig $\gamma$ som slutar i $s$, eftersom $s$ har j\"amn grad. Om gamma inneh\aa ller alla kanter \"ar vi klara.
Antag att $\sigma$ inte inneh\aa ller alla kanter och bilda delgrafen $H\setminus \gamma$ genom att ta borta alla kanter i $\gamma$. Varje nod i $H$ har j\"amn grad och $H$ \"ar n\aa gon icke-isolerade  nod $v$,  eftersom $G$ \"ar sammanh\"angande. S{\aa} kan man konstruera en stig $\alpha$ fr\aa n $v$. Om stigen $\gamma\cup \alpha$ inte inneh\aa ller alla kanter i $G$ forts\"atter man med grafen
$G\setminus \gamma\cup \alpha$

\vspace{.1in}

\noindent{\it STAS 2} En graf utan isolerade noder har en eulerv\"ag  om och endast om \"ar sammanh\"angande och har h\"ogst tv{\aa} noder av udda grader.}

\noindent{\it Bevis.} Antag $G$ har en eulerv\"ag, d{\aa} \"ar $G$ sammanh\"angande och man kan visa at den har h\"ogst tv{\aa} noder av udda grader p{\aa} samma s\"att \"an i Sats 1.

Antag nu att $G$ \"ar sammanh\"angande och har h\"ogst tv{\aa} noder av udda grader. Om alla noder har j\"amn grad d{\aa} finns det en eulerstig och d\"arf\"or en eulerv\"ag.

Det kan inte vara att bara en nod har odd grad eftersom d{\aa} summan av grader m\aa ste vara j\"amn. S{\aa} vi kan antag att det finns exact tv{\aa] noder $a,b$ med odd grad. L\aa t $G'$ vara delgrafen genom att f\"orbinda $a$ och $b$ med en ny kan $e$. $G'$ \"ar sammanh\"angande och har varje nod har j\"amn grad. Enligt Sats 1 $G'$ har en eulerstig $\gamma$. Det f\"oljer att $\gamma-e$ \"ar en eulerv\"ag i $G$.

\vspace{.1in}

\noindent{\it Exempel}.

\begin{itemize}
\item Grafen  i f\"orre exempel har ingen eulrv\"ag eller eulerstig, eftersom det finns $6$ stycken noder med grad $3$. 
\item $K_n$ \"ar eulersk bara n\"ar $n$ \"ar udd.
\item $K_n$ har en Eulerv\"ag bara bara n\"ar $n$ \"ar udd eller $n=2$. 
\end{itemize}

\section*{\"Ovning}

\begin{enumerate}
\item L\aa t $G=(V,E)$ vara en en enkel graf. Best\"am $|V|$ om $G$ har $15$ kanter och alla noder har samma grad.
\item Rita grafen med incidensmatris:
\[ A_G=\left( \begin{array}{ccccccccc}
1&0&0&0&0&1&0&0&0\\
1&1&0&1&1&0&0&0&0\\
0&1&1&0&0&0&0&0&0\\
0&0&1&1&0&0&1&1&0\\
0&0&0&0&1&1&1&0&1\\
0&0&0&0&&0&0&1&1
\end{array} \right)

\noindent \"Ar grafen eulersk? \\
Har grafen en eulerv\"ag. Om svaret \"ar jag hitta den.
\end{enumerate}
\end{document}
