\documentclass[12pt] {article} \usepackage[T1]{fontenc} 
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,graphicx,multicol,mathrsfs, fancyhdr,enumerate,fourier,eurosym,alterqcm,enumerate,tabularx,variations,numprint}
\usepackage[dvips]{color}
\usepackage[tikz]{bclogo}
\usepackage{pst-plot,pst-tree,pstricks,pst-node,pstricks-add,pst-math,pst-xkey,pst-eucl}
\usepackage[francais]{babel} 
\everymath{\displaystyle}
\usepackage[colorlinks=true,pdfstartview=FitV,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref}
\textwidth 19cm \textheight 24cm \hoffset 
-1,4cm \voffset -3.7cm \oddsidemargin 0pt 
\renewcommand{\thesubsection}{\textcolor{red}{\Roman{subsection}}} 
\renewcommand{\thesubsubsection}{\textcolor{blue}{\Roman{subsection}}.\textcolor{blue}{\arabic{subsubsection}}} 
\pagestyle{fancy}
% pour le pied de page central
\cfoot{Page \thepage/\pageref{fin}}
\title{\textcolor{red}{Généralités sur les graphes}}
\date{}
\begin{document}
\maketitle

\tableofcontents


\subsection{\textcolor{red}{Vocabulaire de base}}
\begin{bclogo}[couleur = cyan!30, arrondi = 0.1,logo=\bcbook]{\textcolor{red}{Vocabulaire}}
\begin{enumerate}[$\bullet$]
\item Un \textbf{\textcolor{red}{graphe}} est un ensemble de points et de lignes reliant certains de ces points.

\item Un \textbf{\textcolor{red}{graphe orienté}} est un graphe dont les lignes sont fléchées ou orientées.

\item Un \textbf{\textcolor{red}{sommet}} est un point d'un graphe (orienté ou non).

\item \textbf{\textcolor{red}{L'ordre}} d'un graphe est le nombre de ses sommets.

\item Une \textbf{\textcolor{red}{arête}} est une ligne reliant deux sommets, appelés aussi extrémités de l'arête.

\item Une \textbf{\textcolor{red}{boucle}} est une arête dont les extrémités sont confondues.

\item Un graphe est \textbf{\textcolor{red}{simple}} si le graphe est sans boucle et, entre deux sommets, il y a au plus une arête.

\item Deux sommets sont \textbf{\textcolor{red}{adjacents}} s'ils sont reliés par une arête. 

\item Le \textbf{\textcolor{red}{degré d'un sommet}} est le nombre d'arêtes dont ce sommet est une extrémité ; attention, dans le cas d'une boucle, celles est compté deux fois.

\end{enumerate}
\end{bclogo}


\subsection{\textcolor{red}{Exemples}}

\textbf{\textcolor{blue}{Exemple 1 }}: graphes complets $K_n$ simples d'ordre $n\geqslant 1$ ($3\leqslant n\leqslant 5$)

\psset{unit=1cm}
\begin{pspicture}(0,-1)(3.5,3)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{dotstyle=*,dotscale=1.5,linewidth=0.75pt, linecolor=bleu}
\rput{0}(1.6,.57){\multido{\n=90+120,\i=1+1}{3}{\dotnode(1.54;\n){S\i}}
\rput(0,-1.2){$K_3$}}
\ncline{S1}{S2}  \ncline{S1}{S3}   \ncline{S2}{S3} 
\end{pspicture}
\hfill
\psset{unit=1cm}
\begin{pspicture}(0,-1)(6.5,3)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{dotstyle=*,dotscale=1.5,linewidth=0.75pt, linecolor=bleu}
\rput{0}(1.5,1){\multido{\n=45+90,\i=1+1}{4}{\dotnode(1.732;\n){S\i}}}
\rput{0}(5,.57){\multido{\n=90+120,\i=6+1}{3}{\dotnode(1.54;\n){S\i}}
\dotnode(0,0){S5}
\rput(-2,-1.2){Deux représentations du $K_4$}}
\ncline{S1}{S2}  \ncline{S1}{S3}  \ncline{S1}{S4}  \ncline{S2}{S3}  \ncline{S2}{S4}  \ncline{S3}{S4}  \ncline{S5}{S6}  \ncline{S5}{S7}  \ncline{S5}{S8}  \ncline{S6}{S7}  \ncline{S6}{S8}  \ncline{S7}{S8} 
\end{pspicture}
\hfill
\psset{unit=1cm}
\begin{pspicture}(0,-1)(3.5,3)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{dotstyle=*,dotscale=1.5,linewidth=0.75pt, linecolor=bleu}
\rput{0}(1.6,1){\multido{\n=18+72,\i=1+1}{5}{\dotnode(1.5;\n){S\i}}
\rput(0,-1.6){$K_5$}}
\ncline{S1}{S2}  \ncline{S1}{S3}  \ncline{S1}{S4}  \ncline{S1}{S5} \ncline{S2}{S3}  \ncline{S2}{S4}  \ncline{S2}{S5}  \ncline{S3}{S4}  \ncline{S3}{S5} \ncline{S4}{S5}
\end{pspicture}


\newpage


\textbf{\textcolor{blue}{Exemple 2}}

\parbox{11cm}{ 
Dans le graphe ci-contre, les degrés des sommets sont :

\medskip

\begin{tabularx}{\linewidth}{|l|*{7}{>{\centering \arraybackslash}X|}}	\hline
Sommets & $s_1$ & $s_2$ & $s_3$ & $s_4$ & $s_5$ & $s_6$ & $s_7$ \\ \hline
Degrés & 2 & 4 & 2 & 2 & 2 & 1 & 0 \\ \hline
 \end{tabularx}
}\hfill  \parbox{5cm}{\begin{flushright}
 \psset{unit=.8cm}
\begin{pspicture}(6,4)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{dotstyle=*,dotscale=1.5,linewidth=0.75pt, linecolor=bleu}
\dotnode(1,2.5){S1}  \dotnode(4,3){S2}  \dotnode(3,0){S3} \dotnode(0,1){S4} \dotnode(2,1.5){S5}  \dotnode(6,2){S6} \dotnode(5,1){S7}
\uput[ul](1,2.5){\prune{\footnotesize{$s_1$}}} \uput[dr](4,3){\prune{\footnotesize{$s_2$}}} \uput[d](3,0){\prune{\footnotesize{$s_3$}}} \uput[dl](0,1){\prune{\footnotesize{$s_4$}}}   \uput[ul](2,1.5){\prune{\footnotesize{$s_5$}}}  \uput[u](6,2){\prune{\footnotesize{$s_6$}}} \uput[d](5,1){\prune{\footnotesize{$s_7$}}}   
\ncline{S1}{S2}\ncline{S2}{S3}  \ncline{S3}{S4}  \ncline{S4}{S1}  \nccircle[nodesep=2pt]{S2}{.3cm} \ncline{S3}{S5}  \ncline{S5}{S6} 
\end{pspicture}
 \end{flushright}
 }



\textbf{\textcolor{blue}{Exemple 3}}
\bigskip

\begin{center}
\psmatrix[fillstyle=solid, fillcolor=yellow, mnode=circle]
 &  &  &  & $A_3$ \\ 
$A_1$ \\ 
 &  & $A_2$ &  &  &  & $A_4$ \\ 
 & $A_7$ &  &  &  & $A_5$ \\ 
$A_8$ &  &  & $A_6 $
\endpsmatrix
\psset{arrows=-}
\ncline{2,1}{3,3}
\ncline{3,3}{1,5}
\ncline{3,3}{4,6}
\ncline{3,3}{4,2}
\ncline{1,5}{3,7}
\ncline{3,7}{4,6}
\ncline{4,6}{5,4}
\ncline{5,4}{4,2}
\ncline{4,2}{5,1}
\end{center}

Ce graphe est d'ordre 8 ; le sommet $A_2$ est de degré 4. Les sommets $A_1$ et $A_3$ ne sont pas adjacents.


\newpage



\textbf{\textcolor{blue}{Exemple 4}}
\bigskip

\begin{center}
\psset{unit=0.4}\begin{pspicture}(0,0)(6,4)
\psframe(0,0)(6,4)
\psline(0,0)(6,4)
\psline(0,4)(6,0)
\psdots(0,0)(6,0)(6,4)(0,4)(3,2)
\end{pspicture}\
\end{center}
Ce graphe est complet car tous les sommets sont adjacents.


\bigskip



\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textcolor{red}{Théorème}}
La somme des degrés de tous les sommets d'un graphe est égale au double du nombre total d'arêtes.\\
C'est donc un nombre pair.
\end{bclogo}

\textbf{\textcolor{red}{Démonstration}} : 

Lorsqu'on additionne les degrés des sommets, une arête est comptée deux fois, une fois pour chaque extrémité.

\textbf{\textcolor{blue}{Exemple d'un réseau téléphonique :}}\\
Dans une \og toute petite ville\fg, il y a 15 appareils téléphoniques. Est-il possible de les relier par des fils téléphoniques pour que chaque appareil soit relié avec exactement 5 autres ?\\
\textbf{\textcolor{red}{Solution :}} On construit un graphe, ou du moins on imagine un graphe correspondant au problème : les sommets sont les appareils et les arêtes sont les fils ; les sommets ont
tous un degré impair et il y en a un nombre impair donc la somme de tous les degrés est impaire : c'est impossible.\\

\begin{bclogo}[couleur = cyan!30, arrondi = 0.1,logo=\bcbook]{\textbf{\textcolor{red}{Vocabulaire :}}}
\begin{enumerate}[$\bullet$]
\item Un graphe est dit \textbf{\textcolor{red}{complet}} lorsque toutes les paires de sommets sont des paires de sommets adjacents.

\item On appelle \textbf{\textcolor{red}{sous graphe}} le graphe composé de certains sommets et des arêtes qui relient ces sommets.

\item Deux sommets d'un graphe étant choisis, on appelle \textbf{\textcolor{red}{chaîne}} une suite d'arêtes mises bout à bout reliant ces deux sommets.\\
Si le graphe est orienté, la chaîne est orientée.

	\item Une chaîne dont tous les sommets (sauf  peut-être  les extrémités) sont distincts  est une \emph{chaîne élémentaire}. 

\item La \textbf{\textcolor{red}{longueur d'une chaîne}} est le nombre d'arêtes constituant la chaîne. (Cela n'a rien à voir avec une longueur réelle !)


\item Un \textcolor{red}{cycle} dans un graphe est une chaîne dont les extrémités coïncident, toutes les arêtes étant distinctes.

\item Un graphe est \textbf{\textcolor{red}{connexe}} s'il existe toujours une chaîne reliant deux sommets distincts du graphe.
\end{enumerate}
\end{bclogo}


\textbf{\textcolor{red}{Exemple}}

\parbox{10cm}{Dans le graphe ci-contre :
\begin{itemize}
	\item La chaîne $\left\{ s_0\, ; \,s_1\, ; \,s_0\, ; \,s_2\, ; \,s_0\, ; \,s_3\, ; \,s_0\, ; \,s_4\, ; \,s_0\, ; \,s_5\, ; \,s_0\right\}$ est une chaîne fermée de longueur 10.
	\item La chaîne $\left\{s_1\, ; \, s_2\, ; \,s_3\, ; \,s_0\, ; \,s_4\, ; \,s_5\right\}$ est une chaîne élémentaire de longueur 5.
		\item La chaîne $\left\{s_1\, ; \,s_2\, ; \,s_0\, ; \,s_3\, ; \,s_4\, ; \,s_0\, ; \,s_5\, ; \,s_1\right\}$  est un cycle de longueur 7.
\end{itemize}}\hfill
 \parbox{8cm}{
\psset{unit=1cm}
\begin{pspicture}(3,3)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{dotstyle=*,dotscale=1.2,linewidth=0.75pt, linecolor=bleu}
\rput{0}(1.5,1.5){\multido{\n=18+72,\i=1+1}{5}{\dotnode(1.5;\n){S\i} \rput(1.8;\n){\footnotesize{\prune{$s_\i$}}}}}
\dotnode(1.5,1.5){S0} \uput[d](1.5,1.5){\footnotesize{\prune{$s_0$}}}
\ncline{S1}{S2}  \ncline{S2}{S3}  \ncline{S3}{S4}  \ncline{S4}{S5} \ncline{S5}{S1}  
\multido{\n=1+1}{5}{\ncline{S0}{S\n}}
\end{pspicture} }

\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textcolor{red}{Théorème d'Euler}}
$G$ étant un graphe connexe (d'un seul tenant), les deux propriétés suivantes sont équivalentes : 
\begin{enumerate}[$\bullet$]
\item Tous les sommets de $G$ sont de degré pair

\item $G$ admet un cycle eulérien.
\end{enumerate}
\end{bclogo}

\bigskip
\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{}
$G$ étant un graphe connexe (d'un seul tenant), les deux propriétés suivantes sont équivalentes : 
\begin{enumerate}[$\bullet$]
\item Deux sommets et deux seulement $A$ et $B$ de $G$ sont de degré impair.

\item $G$ admet une chaîne eulérienne d'extrémités $A$ et $B$.
\end{enumerate}
\end{bclogo}




\textbf{\textcolor{blue}{Exemple 3}}\\
Le problème des ponts de K\"onigsberg se dessine par le graphe suivant :\\
\begin{center}
\psmatrix[fillstyle=solid, fillcolor=yellow, mnode=circle]
&a \\
b&d&c \\
\endpsmatrix
\psset{linecolor=red,arrows=-}
\ncline{1,2}{2,1}
\ncline{1,2}{2,2}
\ncline{1,2}{2,3}
\ncarc{2,1}{2,2}
\ncarc{2,2}{2,1}
\ncarc{2,2}{2,3}
\ncarc{2,3}{2,2}
\end{center}
Ce graphe n'est pas simple.\\
Le degré de a est 3 ; celui de b est 3 comme celui de c ; celui de d est 4.

\begin{tabular}{|*{5}{c|}}\hline
sommet&a&b&c&d\\
\hline
degré&3&3&3&4\\
\hline
\end{tabular}

Il y a des sommets de degré impair , donc il n'y aucun cycle eulérien ; aucun trajet ne permet de revenir à son point de départ en ne passant qu'une fois pas chaque pont.\\
Remarque : il n'y a pas non plus de chaîne eulérienne.

\subsection{\textcolor{red}{Matrices d'adjacence}}
\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textcolor{red}{Définition}}
On appelle matrice de dimensions $(i~;~j)$ un tableau de nombres de $i$ lignes et $j$ colonnes.\\
On note $a_{ij}$ le terme à l'intersection de la ligne $i$ et de la colonne $j$.
\end{bclogo}


\bigskip

\textbf{\textcolor{red}{Exemples}} : 

\begin{enumerate}
\item $A=\begin{pmatrix}1&2&-3\\5&-4&6\end{pmatrix}$ est une matrice de de deux lignes et trois colonnes.

\item $A=\begin{pmatrix}5&7&45&2&3\end{pmatrix}$ est une matrice d'une seule ligne ; on dit que c'est une matrice ligne.

\item $A=\begin{pmatrix}4\\5\\1\\7\end{pmatrix}$ est une matrice colonne.
\end{enumerate}

\begin{bclogo}[couleur = yellow!30, arrondi = 0.1,logo=\bcbook]{\textcolor{red}{Définition}}
On considère un graphe ; on note $a_{ij}$ le nombre d'arêtes reliant le sommet $i$ au sommet $j$.
\end{bclogo}

\bigskip

\textbf{\textcolor{red}{Exemple}} :
\begin{center}
\psset{unit=2}
\begin{pspicture}(-1,-1)(4,3)
\psset{arrowsize=2.5pt 3} \psset{arcangle=0}
\cnodeput(0,0){A}{5}
\cnodeput(2,0){B}{4} 
\cnodeput(3,1){C}{3} 
\cnodeput(1.6,1.5){D}{1} 
\cnodeput(3.5,2){E}{2} 
\ncarc{A}{B}
\ncarc{B}{C}
\ncarc{B}{D}
\ncarc{C}{D}
\ncarc{D}{E}
\end{pspicture}
\end{center}

La matrice associée à ce graphe est : \\
\begin{center}
$M=\begin{pmatrix}0&1&1&1&0\\
1&0&0&0&0\\
1&0&0&1&0\\
1&0&1&0&1\\
0&0&0&1&0
\end{pmatrix}$
\end{center}

\bigskip
 On remarque que cette matrice est symétrique (la ligne $i$ est égale à la colonne $i$) car une arête allant de $i$ à $j$ est aussi une arête allant de $j$ à $i$.
\label{fin}
\end{document}  