\documentclass[12pt,a4paper]{article}
\usepackage{pst-plot,color} 
\usepackage{graphicx} 
\usepackage{multicol}
\usepackage[french]{babel}
\newfont{\mini}{cmssi10 scaled 480}
\font\goth=cmfrak
\def\perm{\mbox{\goth S}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\def\euro{\mbox{\textsf{C}\kern -2.33em{\raise0.24ex\vbox{\small\it =}}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\fin{\nolinebreak \raise-0.1em\hbox{$\Box$}}
\def\stackunder#1#2{\mathrel{\mathop{#2}\limits_{#1}}}
\def\dual{ ^{\rm v}}
\def\bidual{ ^{\rm vv}}
\def\primedual{ ^{\prime \rm v}}
\def\ideal{{\cal J}}
\def\LL{{\cal L}}
\def\max{{\cal M}}
\def\quot#1#2{\mbox{\raise 0.1cm\hbox{$#1$}{\big /}\raise -0.1cm\hbox{$#2$}}}
\def\danger{{\Large \bf
    $\bigtriangleup$}\kern-0.32cm\raise0.05cm\hbox{\small
    !}\kern0.32cm\lower0.05cm\hbox{}}
%%%%%%%
\newlength{\largeurtmp}
\def\rela{\settoheight{\largeurtmp}{Z}{\rm Z} \kern -0.6\largeurtmp
  \raise 0.05cm\hbox{\tiny{\it /}}\kern 0.6\largeurtmp}
\def\petitrela{\settoheight{\largeurtmp}{Z}{\rm Z} \kern -0.4\largeurtmp
  \raise 0.05cm\hbox{\tiny{\it /}}\kern 0.4\largeurtmp}
\def\petitcomplex{{
    \settoheight{\largeurtmp}{$_C$}{\rm C}\kern -\largeurtmp
    \rule{0.25pt}{1.3\largeurtmp}\kern \largeurtmp}}
\def\complex{{
    \settoheight{\largeurtmp}{Q}{\rm C}\kern -0.66\largeurtmp
    \rule{0.25pt}{0.9\largeurtmp}\kern 0.66\largeurtmp}}
\def\ratio{{
    \settoheight{\largeurtmp}{C}{\rm Q}\kern -0.75\largeurtmp
    \rule{0.25pt}{0.9\largeurtmp}\kern 0.75\largeurtmp}}
\def\petitratio{{
    \settoheight{\largeurtmp}{C}{\rm Q}\kern -0.6\largeurtmp
    \rule{0.25pt}{0.6\largeurtmp}\kern 0.6\largeurtmp}}
\newcommand{\proj}{{\rm I} \! {\rm P}}
\newcommand{\reel}{{\rm I} \! {\rm R}}
\newcommand{\Fp}{{\rm I} \! {\rm F}_p}
\newcommand{\nat}{{\rm I} \! {\rm N}}
%%%%%%%%%%%%%%%Debut de macros de fiches d'exos
%%les macros sont \exo, \qu, \quskip \squ \qusqu \qusquskip
\newcounter{exo}
\newcounter{question}
\newlength{\lng}
\newcounter{sousquestion}
\setcounter{exo}{1}
\def\exo{

  \bigskip
  \noindent{\bf Exercice
    \Roman{exo}:}\addtocounter{exo}{1}\setcounter{question}{0}\nopagebreak 

  }
\def\exotitre#1{

  \bigskip
  \noindent{\bf Exercice
    \Roman{exo}: #1}\addtocounter{exo}{1}\setcounter{question}{0}\nopagebreak 

  }
\def\qu{

  \addtocounter{question}{1}\arabic{question})
  \setcounter{sousquestion}{1} }
\def\quskip{

  \bigskip
  \qu}
\def\squ{

  \settowidth{\lng}{\arabic{question})
  }\hspace{\the\lng}\alph{sousquestion}) \addtocounter{sousquestion}{1}} 
\def\qusqu{\qu\nopagebreak \vskip -1\baselineskip \squ}
\def\qusquskip{\quskip\nopagebreak \vskip -1\baselineskip \squ}

%%reference pour exos,squ {\`a} placer avant la question, qu est a placer apres
\def\labelexo#1{\expandafter\edef\csname refexo#1\endcsname {\Roman{exo}}}
\def\refexo#1{\csname refexo#1\endcsname}
\def\labelqu#1{\expandafter\edef\csname refqu#1\endcsname {\arabic{question})}}
\def\refqu#1{\csname refqu#1\endcsname}
\def\labelsqu#1{\expandafter\edef\csname refsqu#1\endcsname
  {\arabic{question}\alph{sousquestion})}} 
\def\refsqu#1{\csname refsqu#1\endcsname}  

%%%%%%%%%%fin de macros fiche d'exos
%%macros taille page
\newlength{\elargir}
\setlength{\elargir}{2.5cm}
\addtolength{\leftmargin}{-\elargir}
%%\addtolength{\hoffset}{-\elargir}
\addtolength{\oddsidemargin}{-\elargir}
\addtolength{\evensidemargin}{-\elargir}
\addtolength{\elargir}{\elargir}
\addtolength{\textwidth}{\elargir}
\addtolength{\textheight}{14\baselineskip}
\topmargin=-5\baselineskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%        
\newtheorem{theorem}{Th{\'e}or{\`e}me}[section]
\newtheorem{corollary}[theorem]{Corollaire}
\newtheorem{lemma}[theorem]{Lemme}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remarque}
\newtheorem{definition}[theorem]{D{\'e}finition}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\everymath={\displaystyle}
\begin{document}
\noindent{\bf Universit{\'e} de Paris 7 \hfill \framebox{\Large \bf
    \hspace{ 1cm} TP Texte Graphes \hspace{1cm}}\hfill   agreg 2009 (F.Han\footnote{http://www.math.jussieu.fr/$\sim$han/agreg})}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{center}
  {\it Pr{\'e}paration: maison+jeudi 18: 2h, puis exposes}
\end{center}
\def\code#1{{\tt #1}}
%% 
\columnsep 0.7cm
% restart;maple_mode(1);cas_setup(0,0,0,1,0,1e-10,10,[1,50,0,25],0,0,0);#radians,pas de cmplx, pas de  Sqrt
\section{D{\'e}finitions}
\begin{definition}
Un graphe $\Gamma$ est la donn{\'e}e de 3 ensembles: l'ensemble $S_\Gamma$
de ses sommets, l'ensemble $A_\Gamma$ de ses cot{\'e}s (ou ar{\^e}tes), et d'un
sous-ensemble $I_\Gamma$ de $S_\Gamma \times A_\Gamma$ appel{\'e} relation
d'incidence tel que chaque c{\^o}t{\'e} contienne au moins 1 et au plus 2
sommets. (On dit,  pour $(s,a)\in S_\Gamma \times A_\Gamma$,  que $a$
contient $s$ si et seulement si $(s,a)\in I$).

Si toute ar{\^e}te contient exactement 2 sommets, et que 2 sommets sont
dans au plus une ar{\^e}te, on dit que le graphe est simple.
  
\end{definition}
\begin{definition}
Soit $n\in\nat^*$. Un chemin de longueur $n$ et d'extr{\'e}mit{\'e}s $s_0,s_n$ est un graphe de
sommets $(s_0,\dots,s_{n})$ de $S_\Gamma$, de
cot{\'e}s $(a_1,\dots,a_n)$ de $A_\Gamma$, et d'incidence
$I=\bigcup_{i=1}^n (s_{i-1},a_i)\cup(s_{i},a_i)$. Si
$s_0,\dots,s_{n-1}$ sont distincts et que $s_n=s_0$, on dit que le
chemin est un cycle.

Si $n=1$ et $s_1=s_0$, on dit que le chemin est
une boucle.
\end{definition}
\begin{definition}
Un graphe est connexe si toute paire de  points distincts
peut {\^e}tre r{\'e}alis{\'e}e comme les extr{\'e}mit{\'e}es d'un chemin.
\end{definition}
\begin{definition}
La valence d'un sommet $s$ dans un graphe est le nombre de c{\^o}t{\'e}s
orient{\'e}s qui  contiennent ce sommet comme d{\'e}part\footnote{Par exemple
  une boucle compte pour 2 dans la valence}. 

Un graphe sera dit r{\'e}gulier si ses sommets ont
m{\^e}me valence.
\end{definition}
Les graphes ont des applications dans des domaines tr{\`e}s vari{\'e}s. Par
exemple pour mod{\'e}liser un r{\'e}seau. Dans ce cas, la valence ne peut pas
{\^e}tre tr{\`e}s grande pour des raisons de co{\^u}t. De plus, pour minimiser les
retours d'informations il est int{\'e}ressant de ne pas avoir de petits
cycles.
\begin{definition}
  Le tour de taille d'un graphe simple est le minimum des longueurs
  de ses cycles. (Si le graphe n'a pas de cycles,  son tour de taille
  sera $+\infty$)  
\end{definition}
%% 
\section{Exemples}
\subsection{ Graphes de Petersen g{\'e}n{\'e}ralis{\'e}s}
Pour $m\wedge n=1$, on consid{\`e}re la famille de graphes $G(n,m)$ {\`a} $2n$ sommets:
$\{u_0,\dots,u_{n-1},v_0,\dots,v_{n-1}\}$ et $3n$  c{\^o}t{\'e}s:
$\{\{u_i,u_{i+1}\}_{i\in\petitrela/n\petitrela}, \{u_i,v_{i}\}_{i\in\petitrela/n\petitrela},
\{v_i,v_{i+m}\}_{i\in\petitrela/n\petitrela}\}$. On peut par exemple les
repr{\'e}senter en prenant pour $(u_i)$ et $(v_i)$ les points d'affixes
$2.e^{2iI\pi/n}$ et $ e^{2iI\pi/n}$. Ce qui donne pour $G(5,2)$ et $G(5,1)$: 
\begin{center}
%%Charger:
%% \usepackage{pst-plot,color} 
%%\usepackage{graphicx} 
\begin{pspicture}(-2.5,-2.5)(2.5,2.5)
\psset{unit=1.cm}
\psset{xunit=1.0cm}
\psset{yunit=1.0cm}
\psset{linewidth=.5pt}
\psline(0.3090,0.9511)(-0.8090,-0.5878)
\psline(-0.8090,0.5878)(0.3090,-0.9511)
\psline(-0.8090,-0.5878)(1.0000,0.0000)
\psline(0.3090,-0.9511)(0.3090,0.9511)
\psline(1.0000,0.0000)(-0.8090,0.5878)
\psline(0.6180,1.9021)(-1.6180,1.1756)
\psline(-1.6180,1.1756)(-1.6180,-1.1756)
\psline(-1.6180,-1.1756)(0.6180,-1.9021)
\psline(0.6180,-1.9021)(2.0000,0.0000)
\psline(2.0000,0.0000)(0.6180,1.9021)
\psline(0.3090,0.9511)(0.6180,1.9021)
\psline(-0.8090,0.5878)(-1.6180,1.1756)
\psline(-0.8090,-0.5878)(-1.6180,-1.1756)
\psline(0.3090,-0.9511)(0.6180,-1.9021)
\psline(1.0000,0.0000)(2.0000,0.0000)
\psset{linecolor=black}
\psset{linewidth=1.5pt}
\psdots[dotstyle=*](0.3090,0.9511)
\psdots[dotstyle=*](-0.8090,0.5878)
\psdots[dotstyle=*](-0.8090,-0.5878)
\psdots[dotstyle=*](0.3090,-0.9511)
\psdots[dotstyle=*](1.0000,0.0000)
\psdots[dotstyle=*](0.6180,1.9021)
\psdots[dotstyle=*](-1.6180,1.1756)
\psdots[dotstyle=*](-1.6180,-1.1756)
\psdots[dotstyle=*](0.6180,-1.9021)
\psdots[dotstyle=*](2.0000,0.0000)
\end{pspicture} 
\hspace{2cm}
\begin{pspicture}(-2.5,-2.5)(2.5,2.5)
\psset{unit=1.cm}
\psset{xunit=1.0cm}
\psset{yunit=1.0cm}
\psset{linewidth=.5pt}
\psline(0.3090,0.9511)(-0.8090,0.5878)
\psline(-0.8090,-0.5878)(0.3090,-0.9511)
\psline(-0.8090,-0.5878)(-0.8090,0.5878)
\psline(0.3090,-0.9511)(1.0000,0.0000)
\psline(1.0000,0.0000)(0.3090,0.9511)
\psline(0.6180,1.9021)(-1.6180,1.1756)
\psline(-1.6180,1.1756)(-1.6180,-1.1756)
\psline(-1.6180,-1.1756)(0.6180,-1.9021)
\psline(0.6180,-1.9021)(2.0000,0.0000)
\psline(2.0000,0.0000)(0.6180,1.9021)
\psline(0.3090,0.9511)(0.6180,1.9021)
\psline(-0.8090,0.5878)(-1.6180,1.1756)
\psline(-0.8090,-0.5878)(-1.6180,-1.1756)
\psline(0.3090,-0.9511)(0.6180,-1.9021)
\psline(1.0000,0.0000)(2.0000,0.0000)
\psset{linecolor=black}
\psset{linewidth=1.5pt}
\psdots[dotstyle=*](0.3090,0.9511)
\psdots[dotstyle=*](-0.8090,0.5878)
\psdots[dotstyle=*](-0.8090,-0.5878)
\psdots[dotstyle=*](0.3090,-0.9511)
\psdots[dotstyle=*](1.0000,0.0000)
\psdots[dotstyle=*](0.6180,1.9021)
\psdots[dotstyle=*](-1.6180,1.1756)
\psdots[dotstyle=*](-1.6180,-1.1756)
\psdots[dotstyle=*](0.6180,-1.9021)
\psdots[dotstyle=*](2.0000,0.0000)
\end{pspicture} 
\end{center}
Ces graphes sont r{\'e}guliers, connexes, de valence $3$, mais ne sont pas toujours
$2$-coloriables. (un graphe est $k$-coloriable si avec $k$ couleurs,
il existe une fa\c con de colorier les sommets telle que deux sommets d'un
m{\^e}me c{\^o}t{\'e} soient de couleur diff{\'e}rente). 
% !s!<c>
% G(n,m) est biparti ssi n pair et m impair
%!s!
%% G(n,m) is a Cayley graph if and only if m^2 \equiv 1 \pmod n.
\subsection{Graphes de Cayley}
Soit $G$ un groupe, et $L$ une partie finie de $G$ ne contenant pas le
neutre, et stable par passage {\`a} l'inverse. Le graphe de Cayley
$\Gamma(G,L)$ est le graphe dont les sommets sont les {\'e}l{\'e}ments de $G$
et les ar{\^e}tes les paires $\{x,y\}$ d'{\'e}l{\'e}ments de $G$ tels que
$x^{-1}.y\in L$

Par exemple, avec $(\rela/6\rela,+)$ on peut cr{\'e}er  $7$ graphes de
Cayley, dont 5 connexes.
\begin{remark}
  Un graphe de Cayley $\Gamma(G,L)$ est un graphe simple r{\'e}gulier de
  valence le cardinal de $L$. Il est connexe si et seulement si $L$
  engendre le groupe $G$. 
\end{remark}
Tous les graphes r{\'e}guliers ne sont pas forc{\'e}ment de Cayley. Par
exemple, le graphe de Petersen $G(5,2)$ ne l'est pas alors que
$G(5,1)$ si\footnote{pourquoi?}.
% !s!<c>
% G(5,1) est de Cayley pour (Z/10Z,+),{-2,2,5}. Avec valence 3, L  contient un
% element egal a son inverse et pas le neutre donc G=Z/10Z  et L contient
% 5. Dans le cas de G(5,2), L doit aussi contenir un  element d'ordre 5, ce qui
% donne en fait G(5,1).  
% !s!
%% G(n,m) is a Cayley graph if and only if m^2 \equiv 1 \pmod n.
\section{Matrice d'adjacence}
\begin{definition}
On appelle matrice d'adjacence d'un graphe $\Gamma$ {\`a} $n$ sommets, une
matrice $M$, carr{\'e}e de taille $n$, telle qu'il existe une indexation
$s_1,\dots,s_n$ des sommmets de $\Gamma$ telle que  $M_{i,j}$ soit le nombre
de c{\^o}t{\'e} de $\Gamma$ d'extr{\'e}mit{\'e}s $s_i,s_j$.
\end{definition}
Par exemple, la matrice d'adjacence d'un triangle est $
\left(\begin{array}{ccc}
  0&1&1\\
  1&0&1\\
  1&1&0
\end{array}\right)$, celle d'un $n$-cycle est $^tC_n+C_n$ o{\`u}
$C_n$ est une matrice de permutation circulaire des $n$ vecteurs de base.
\begin{center}
{\sc Dans toute la suite $\Gamma$ sera un graphe simple.}  
\end{center}
La matrice d'adjacence permet de trouver de nombreuses propri{\'e}t{\'e}s du
graphe. Par exemple:
\begin{remark}\label{facile1}
Le nombre de chemins de longueur $l$ d'extr{\'e}mit{\'e} les sommets d'incides
$i$ et $j$ est $(M^l)_{i,j}$, la valence du  sommet d'indice $i$ est
$(M^2)_{i,i}$   
\end{remark}

On note $x^n+\sum_{i=1}^n c_i.x^{n-i}=\det(x.I-M)$ son polyn{\^o}me
caract{\'e}ristique. En exprimant les coefficients $c_i$  en fonction
des mineurs diagonaux d'ordre $i$, on montre la proposition suivante:
\begin{proposition}\label{polcar1}
$c_1=0$, $-c_2$ est le nombre de c{\^o}t{\'e}s, $-c_3$ est  deux fois le nombre de
triangles.  
\end{proposition}
% !s!<c>
% c_i est au signe pres la somme des mineurs diagonaux de taille  i. (On derive
% i fois le polynome caracteristique). Pour c2, ils sont soit nuls, soit
% [[0,1],[1,0]] selon que (s_i,s_j) est un cote, ou pas. Cette somme est donc le
% nombre de cote. De meme, pour c_3, la seule matrice symetrique inversible de
% diagonale  nulle que l'on peut faire avec des 0 et 1 est
% [[0,1,1],[1,0,1],[1,1,0]]. Ce mineur correspond au cas ou le triangle
% correspondant {\`a} ces 3 sommets est dans le graphe. Comme ce determinant vaut 2,
% c3 vaut au signe pres 2 fois le nombre de triangle. 
%!s!
On peut d{\'e}j{\`a} d{\'e}duire de ce r{\'e}sultat et de l'in{\'e}galit{\'e} de
Cauchy-Schwarz que la plus grande valeur propre d'un graphe simple {\`a}
$n$ sommets et $m$ c{\^o}t{\'e}s est major{\'e}e par
$\sqrt{\frac{2m(n-1)}{n}}$. Mais pour un graphe r{\'e}gulier, on a de plus:
\begin{proposition}\label{facile2}
Si $\Gamma$ est un graphe r{\'e}gulier de valence $k$, alors $k$ est une
valeur propre de $\Gamma$, et toutes les autres ont une valeur absolue
inf{\'e}rieure ou {\'e}gale {\`a} $k$. Si de plus $\Gamma$ est connexe, alors $k$
est de multiplicit{\'e} $1$.  
\end{proposition}
Nous allons maintenant obtenir des informations g{\'e}om{\'e}triques plus
pr{\'e}cises en fonction de la matrice d'incidence. Il nous faut pour cel{\`a}
d{\'e}finir la notion de graphe sesquivalent:
\begin{definition}
Un graphe sera dit sesquivalent si ses composantes connexes sont des
graphes r{\'e}guliers de valence 1 ou 2. 
\end{definition}
\begin{minipage}[c]{0.6\linewidth}
Autrement dit les composantes connexes d'un graphe sesquivalent  sont
des cycles ou des ar{\^e}tes. Par exemple le graphe ci-contre est
sesquivalent, il poss{\`e}de un cycle et 3 composantes connexes.

\noindent{\bf Notations:} {\it Pour un graphe simple $\Gamma$ on notera
$Sesq_i(\Gamma)$ l'ensemble des  graphes  sesquivalents {\`a} $i$ sommets,
dont les c{\^o}t{\'e}s sont des {\'e}l{\'e}ments de $A_\Gamma$ et les sommets sont tous les
sommets de $\Gamma$ qui sont sur au moins un de ces c{\^o}t{\'e}s.}
\end{minipage}
\begin{minipage}[c]{0.4\linewidth}
\begin{pspicture}(-4.0000,-2.5)(3.0000,2.5)
\psset{unit=2cm}
\psset{xunit=2cm}
\psset{yunit=2cm}
\psset{linecolor=black}
\psset{linewidth=1.5000pt}
\psdots[dotstyle=*](0.5000,0.5000)
\psdots[dotstyle=*](-0.5000,0.5000)
\psdots[dotstyle=*](-0.5000,-0.5000)
\psdots[dotstyle=*](0.5000,-0.5000)
\psdots[dotstyle=*](1.0000,0.0000)
\psdots[dotstyle=*](-1.0000,0.0000)
\psdots[dotstyle=*](0.0000,-1.0000)
\psdots[dotstyle=*](0.0000,1.0000)
\psset{linecolor=black}
\psset{linewidth=0.5000pt}
\psline(-1.0000,0.0000)(1.0000,0.0000)
\psline(0.0000,-1.0000)(0.0000,1.0000)
\psline(0.5000,0.5000)(-0.5000,0.5000)
\psline(-0.5000,0.5000)(-0.5000,-0.5000)
\psline(-0.5000,-0.5000)(0.5000,-0.5000)
\psline(0.5000,-0.5000)(0.5000,0.5000)
\end{pspicture} 
\end{minipage}
\begin{proposition}
Le d{\'e}terminant de la matrice d'adjacence d'un graphe simple {\`a} $n$
sommets est
$$\sum_{\Lambda \in Sesq_n(\Gamma)}(-1)^{r(\Lambda)}2^{s(\Lambda)}$$  o{\`u}
$r(\Lambda)$ est le nombre de sommets moins le nombre de composantes
connexes, et $s(\Lambda)$ est le nombre de cycles\footnote{On a limit{\'e}
  cette   d{\'e}finition de $s(\Lambda)$ au cas sesquivalent }. 
\end{proposition}
En effet, si $M$ est la matrice d'adjacence d'un graphe simple
$\Gamma$ de sommets $\{s_1,\dots,s_n\}$, et $\sigma\in\perm_n$, alors
pour que le terme 
$(-1)^{\epsilon(\sigma)}\prod_{i=1}^n M_{i,\sigma(i)}$ soit non nul, il faut d{\'e}ja
que $\sigma$ n'ait pas de points fixes. Le cardinal de l'orbite de $i$ sous
l'action de $\sigma$ vaut donc au moins $2$; notons le $l$. Dire que le produit est
non nul implique de plus que les nombres
$\{M_{i,\sigma(i)},\dots,M_{\sigma^{k-1}(i),\sigma^k(i)},\dots,M_{\sigma^{l-1}(i),\sigma^l(i)}\}$
vallent $1$, ce qui  {\'e}quivaut {\`a} dire qu'il existe des ar{\^e}tes de
$\Gamma$ formant le cycle $\{s_{i},\dots,s_{\sigma^l(i)} \}$.
La permutation $\sigma$ nous donne donc un graphe $\Lambda_\sigma$ sesquivalent
constitut{\'e} d'ar{\^e}tes de $\Gamma$. On aura
$\Lambda_\sigma=\Lambda_{\sigma'}$ si et seulement si les
d{\'e}compositions de $\sigma$ et $\sigma'$ en produit de permutations
circulaires {\`a} support disjoints ont des facteurs {\'e}gaux ou
inverses. Autrement dit $\Lambda_{\sigma}$ est obtenu $2^{s(\Lambda_\sigma)}$
fois. Pour conclure il faut encore remarquer que $r(\Lambda_\sigma)$ a m{\^e}me
parit{\'e} que le nombre d'orbites de cardinal pair.
% !s!<c>
% Si c  est le nombre de composantes connexes d'un graphe sesquivalent, alors
% une permutation associee a ce graphe se decompose en c  cycles. notons c0, c1
% le nombre de cycles de longueur pair et impair. Comme un cycle de longueur
% impair a un support de taille impair, le produit des cycles de longueur impair
% a un support de parite c1. Donc n-c1 est pair car il a meme parite que le
% support du produit des cycles pairs. donc n-c=n-c1-c0 a meme parite que c0 
%!s!
En appliquant ce r{\'e}sultat aux mineurs diagonaux, on obtient:
\begin{corollary}\label{polcar2}
Si $\Gamma$ est un graphe simple de polyn{\^o}me caract{\'e}ristique
$x^n+\sum_{i=1}^n c_i.x^{n-i}$, alors on a:
$$(-1)^i.c_i=\sum_{\Lambda\in Sesq_i(\Gamma)} (-1)^{r(\Lambda)}2^{s(\Lambda)}$$
\end{corollary}
\section{Graphes {\`a} grand tour de taille.}
Cette partie est  issue de l'article d'Alain Valette:
``Graphes {\`a} grand tour de taille'' CNRS, image des math{\'e}matiques 2004.

\bigskip
On rappelle sans d{\'e}monstration le th{\'e}or{\`e}me des 4 carr{\'e}s dans le cas d'un nombre premier
impair $p$:
\begin{theorem}
L'ensemble $\{(x_0,x_1,x_2,x_3)\in\rela^4,
x_0^2+x_1^2+x_2^2+x_3^2=p\}$ a pour cardinal $8(p+1)$  
\end{theorem}
On peut alors en d{\'e}duire assez facilement que si $p\equiv 1 [4]$
alors:
$$\#\{(x_0,x_1,x_2,x_3)\in\rela^4,x_0^2+x_1^2+x_2^2+x_3^2=p, x_0
\mbox{ impair }, x_0>0\}=p+1$$
% !s!<c>
% En passant modulo 4, un seul des x_i est impair. Donc choisir x_0  impair
% positif divise par 8 le nombre de solutions 
% !s!
\begin{center}
  {\sc Dans la suite $p$ sera un nombre premier impair congru {\`a} 1
    modulo 4.}
\end{center}
Pour un anneau commutatif unitaire $R$ on notera $H(R)$ l'anneau des
quaternions:
$$H(R)=\{a_0+a_1 i + a_2 j +a_3 k|\ a_0,a_1,a_2,a_3 \in R\}$$
o{\`u} $i,j,k$ sont des symboles soumis aux relations: $i^2=j^2=k^2=-1$,
$ij=-ji=k$, $jk=-kj=i$, $ki=-ik=j$. On $\alpha=a_0+a_1 i + a_2 j +a_3
k$, on notera $\bar{\alpha}=a_0-a_1 i - a_2 j -a_3 k$ son conjugu{\'e}. On
notera:
$$L_p=\{a_0+a_1i+a_2j+a_3k \in H(\rela) | a_0^2+a_1^2+a_2^2+a_3^2=p, a_0
\mbox{ impair }, a_0>0\}$$
\begin{center}
{\sc Dans toute la suite $q$ d{\'e}signera un nombre premier impair diff{\'e}rent de $p$}  
\end{center}
Un simple calcul de cardinal permet de montrer qu'il existe $x$,
et $y$ dans  $\rela/q\rela$ tels que $x^2+y^2+1=0$. Choisissons ces
{\'e}l{\'e}ments une fois pour toute. On a alors le lemme suivant:
\begin{lemma}\label{quater}
  L'application
  $\Psi_q:\begin{array}[t]{clc}
    H(\rela/q\rela)& \to & {\cal M}_2(\rela/q\rela)\\
    a_0+a_1 i+a_2 j+a_3 k & \mapsto &
    \left(\begin{array}[c]{cc}
        a_0+a_1x+a_3y & -a_1y+a_2+a_3x\\
        -a_1y-a_2+a_3x & a_0-a_1x-a_3y
    \end{array}\right)
  \end{array}$ est un isomorphisme d'anneaux.
\end{lemma}
On remarque de plus que $\det(\Psi_q(a_0+a_1 i+a_2 j+a_3 k
)) = a_0^2+a_1^2+a_2^2+a_3^2$ et que $\Psi_q(\alpha.\bar{\alpha})$ est un
multiple de l'identit{\'e}. Comme $p$ est inversible modulo $q$, ceci
montre que pour tout $\alpha$ de $L_p$, $\Psi_q(\alpha)$ est
inversible. On notera $L_{p,q}$ les classes dans $PGL_2(\rela/q\rela)$
des $\Psi_q(\alpha)$ pour $\alpha\in\L_p$. Si l'on prend $q>2\sqrt{p}$
alors on est s{\^u}r que $L_{p,q}$ a pour cardinal $p+1$. D'autre part
comme $L_p$ est invariant par conjugaison, $L_{p,q}$ est sym{\'e}trique.
\begin{proposition}
Si $p$ n'est pas un carr{\'e} modulo $q$, et $q>2\sqrt{p}$, alors $L_{p,q}$ ne recontre pas
$PSL_2(\rela/q\rela)$, et le graphe de Cayley
$\Gamma(PGL_2(\rela/q\rela),L_{p,q})$ est $p+1$ r{\'e}gulier {\`a} $q(q^2-1)$ sommets.  
\end{proposition}
Lubotzky-Phillips-Sarnak et Margulis ont montr{\'e} la connexit{\'e} de ces
graphes pour $q>2\sqrt{p}$. Nous l'admettrons ici.

Autrement dit, nous avons admis que $L_{p,q}$ engendrait  le groupe
$PGL_2(\rela/q\rela)$. Pour comprendre le tour de taille du graphe
$\Gamma(PGL_2(\rela/q\rela),L_{p,q})$, notons
$\{\alpha_1,\dots,\alpha_{\frac{p+1}{2}},\bar{\alpha}_1, \dots,
\bar{\alpha}_{\frac{p+1}{2}}\}$ les {\'e}l{\'e}ments de $L_{p,q}$, de telle
sorte que $\alpha_k.\bar{\alpha}_k=1$.

il faut comprendre quel est le plus petit $g$ tel qu'il existe un
produit non trivial (sans facteurs $\alpha_k.\bar{\alpha}_k)$) de $g$
{\'e}l{\'e}ments de $L_{p,q}$ qui donne l'{\'e}l{\'e}ment neutre de
$PGL_2(\rela/q\rela)$. En remontant ces {\'e}l{\'e}ments dans $L_p$ et en
passant aux normes, on obtient: $p^g=a_0^2+a_1^2+a_2^2+a_3^2$ avec
$a_0$ impair positif, au moins un des {\'e}l{\'e}ments $a_1,a_2,a_3$ non nul, et
$a_1$, $a_2$, $a_3$ multiples de $q$. Le dernier point que nous
admettrons est que tout {\'e}l{\'e}ment de $H(\rela)$ v{\'e}rifiant ces propri{\'e}t{\'e}s
peut se d{\'e}composer comme $\pm p^k$ fois un produit d'{\'e}l{\'e}ments de
$L_p$. Nous avons donc:
\begin{proposition}
  Si $p$ n'est pas un carr{\'e} modulo $q$ et $q>2\sqrt{p}$, le tour de taille du graphe
  $\Gamma(PGL_2(\rela/q\rela),L_{p,q})$ 
  est le plus petit $g$ tel que: $p^g=a_0^2+a_1^2+a_2^2+a_3^2$ ait une
  solution avec $a_0$ impair positif, o{\`u} moins un des {\'e}l{\'e}ments
  $a_1,a_2,a_3$ est  non nul  et o{\`u} $a_1$, $a_2$, $a_3$ sont multiples de $q$.
\end{proposition}
A titre d'information on a en fait:
\begin{theorem}
 Si $p$ n'est pas un carr{\'e} modulo $q$ et $q>2\sqrt{p}$, le tour de taille du graphe
  $\Gamma(PGL_2(\rela/q\rela),L_{p,q})$est minor{\'e} par $(4/3+O(1))\log_p(|\Gamma(PGL_2(\rela/q\rela),L_{p,q})|)$  
\end{theorem}
\section{Suggestions}
On pourra {\'e}ventuellement s'aider des d{\'e}veloppements suivants: 
\subsection{Graphes de Petersen; Matrice d'adjacence}
\setcounter{question}{0}
\qu On pourra dessiner diff{\'e}rents graphes de Petersen.
% !s!<m>
%switch_axes(0):
% dessinG:=proc(n,m)
%local a,L;
%a:=exp(2.0*I*Pi/n);
%L:='affichage=(point_width_2+hidden_name+bleu)';
%#On separe par des , car la procedure ne retourne que la derniere instruction
%seq(segment(a^k,a^(k+m)),k=1..n),seq(segment(2*a^k,2*a^(k+1)),k=1..n),seq(segment(a^k,2*a^(k)),k=1..n),seq(point(a^(k),L),k=1..n),seq(point(2*a^k,L),k=1..n);
%end_proc;
%!s!
%dessinG(5,2);
%dessinG(8,3)
%n:=8;m:=3;
\qusqu On pourra cr{\'e}er la matrice d'incidence des graphes de Petersen.
% !s!<c>
% On cree d'abord une matrice de permutation circulaire que l'on symetrise
% !s!
% purge(i,j):f:=(i,j)-> if (i-j) mod n = 1 then  1 else 0 fi:
% A:=matrix(n,n,f)+transpose(matrix(n,n,f)
% !s!<c>
%En suite on cree la permutation avec pas de m que l'on symetrise:
% !s!
%g:=(i,j)-> if (i-j) mod n = m then 1 else 0 fi:
%B:=matrix(n,n,g)+transpose(matrix(n,n,g));
%!s!<c>
%Ensuite on cree une matrice par blocs en rajoutant le  fait que les sommets de
%meme indice sont lies. (le bloc identite) 
%!s!
%G:=blockmatrix(2,2,[A,identity(n),identity(n),B]);
\squ Illustrer/prouver les propri{\'e}t{\'e}s \ref{facile1} et \ref{facile2}.
% G^2;#le graphe est de valence 3 cf termes diago
% !s!<c>
%3 est bien la plus grande valeur propre, et elle est de multiplicite 1, le
%graphe peut etre connexe. on passe en flottants pour aller plus vite. 
%!s!
%sort(eigenvals(G*1.0));
\qusqu On pourra {\'e}tudier les coefficients du polyn{\^o}me caract{\'e}ristique,
justifier les propositions \ref{polcar1} et peut {\^e}tre m{\^e}me \ref{polcar2}
%!s!<c>
%c_i est au signe pres la somme des mineurs diagonaux de taille i. Pour c2, ils
%sont soit nuls, soit [[0,1],[1,0]] selon que (s_i,s_j) est un cote, ou
%pas. Cette somme est donc le nombre de cote. De meme, pour c_3, la seule
%matrice symetrique inversible de diagonale nulle que l'on peut faire avec des 0
%et 1 est [[0,1,1],[1,0,1],[1,1,0]]. Ce mineur correspond au cas ou le triangle
%correspondant {\`a} ces 3 sommets est dans le graphe. Comme ce determinant vaut 2,
%c3 vaut au signe pres 2 fois le nombre de triangle. 
%!s!
\squ Utiliser les propositions \ref{polcar1} et \ref{polcar2} pour
montrer que certains graphes de Petersen n'ont pas de $3$ cycles, et
peut {\^e}tre m{\^e}me trouver  un exemple de tour de taille $6$, puis
prouver que son tour de taille vaut $6$.
%charpoly(G)
%!s!<c>
%On voit deja qu'il n'y a pas de triangles a cause du coeff c3=0, et qu'il y a
%3n=c3 aretes. D'autre part, d'un sommet part 6 chemins de longuer 2 puisque le
%graphe est 3 regulier. V{\'e}rification: 
%!s!
%[seq(1,i=1..2*n)]*(G^2-3*identity(2*n));
% !s!<c>
%Donc le nombre de paires de cotes disjoints est:
%!s!
%nbpairesdisj:=(3*n)*(3*n-1)/2-(2*n*6)/2
%!s!<c>
%Le nombre de 4 cycles est: (nombre de paires d'aretes disjointtes -c4)/2
%!s!
%(nbpairesdisj-charpoly(G)[5])/2;
%!s!<c>
%On n'a donc pas de 4 cycles dans G(8,3), et comme c5=0, il a tour de taille
%6,(on montre un chemin de longueur 6 sur le dessin). En revanche G(4,1) possede
%6 4-cycles: 
%!s!<g>
%switch_axes(0):
%n:=6;m:=1;
%f:=(i,j)-> if (i-j) mod n = 1 then  1 else 0 fi;
% A:=matrix(n,n,f)+transpose(matrix(n,n,f));
%g:=(i,j)-> if (i-j) mod n = m then 1 else 0 fi;
%B:=matrix(n,n,g)+transpose(matrix(n,n,g));
%G:=blockmatrix(2,2,[A,identity(n),identity(n),B]);
%nbpairesdisj:=(3*n)*(3*n-1)/2-(2*n*6)/2;
%nb4cycles:=(nbpairesdisj-charpoly(G)[5])/2;
%dessinG(4,1);
%!s!
\subsection{Graphes {\`a} grand tour de taille}
\setcounter{question}{0}
\danger Bien que les matrices d'adjacence des graphes consid{\'e}r{\'e}s
soient creuses, on n'essayera pas de travailler avec des matrices de
taille 1000. D'autre part, la valence des graphes {\'e}tant de $p+1$, le
nombre $p$ restera petit alors que $q$ pourra grandir.
\qu D{\'e}montrer/ Illustrer \ref{quater}
% II:=matrix([[x,-y],[-y,-x]]);#manque un x dans l'enonce
% KK:=matrix([[y,x],[x,-y]]);
% JJ:=matrix([[0,1],[-1,0]]);
% II^2;JJ^2;KK^2;II*JJ-KK;JJ*II+KK;KK*JJ+II;JJ*KK-II;KK*II-JJ;II*KK+JJ;
% !s!<c>
% Ce qui donne bien les memes relations vu que x et y sont solutions
% de x^2+y^2=-1. 
%!s!
\qu Donner {\`a} $p$ et $q$ les plus petites valeurs possibles, et trouver $x,y$.
\qu Programmer la rechercher des $p+1$ solutions de $L_p$ lorsque $p$ est donn{\'e}.
% !s!<c>
%pour eviter les doublons, et les cas avec +0=-0 on utilise des ensembles et no
%des suites. D'autre part, pour creer une suite a partir de 2 suites: 
%!s!
% augment([1,2],[2,3,4]);
% !s!<p>
% makeS:=proc(p)
% S:={};
% for a from 0 to p do 
% L:={};
%% j:=normal(sqrt(p-a));
% for i from 0 to (sqrt(p-a)) do 
% j:=normal(sqrt(p-a-i^2));
% if floor(j)=j then L:= L union {[i,j],[-i,j],[i,-j],[-i,-j]} ;#NB: les ensembles simplifient les doublons
% fi  
% od
% if L<> {} then
%  for i from 1 to sqrt(a) by 2 do 
%  j:=normal(sqrt(a-i^2));
%   if floor(j)=j then S:=S union {seq(augment([i,j],l),l=L),seq(augment([i,-j],l),l=L)}
%   fi
%  od
% fi
% od
% S;
% end_proc:
% !s!<c>
% danger avec floor d'un entier de gauss! il faut donc faire attention  dans nos
% boucles a ne pas avoir de racines de negatifs
%!s!<c>
%On teste un peu la procedure. lorsque le nombre n'est pas premier, on doit
%trouver somme des diviseurs.  
%!s!
%makeS(5);
%dim(makeS(37));#on trouve bien p+1
%dim(makeS(5^4));1+5+5^2+5^3+5^4;
\qu Cr{\'e}er un programme testant s'il existe une solution
$(a_0,a_1,a_2,a_3)\in\rela^4$ {\`a} l'{\'e}quation
$p^g=a_0^2+a_1^2+a_2^2+a_3^2$ avec $a_0$ impair positif,
$(a_1,a_2,a_3)\neq (0,0,0)$, $(a_1,a_2,a_3)\equiv (0,0,0)\ [q]$ 
% !s!<p>
% chercheg:=proc(p,q)
%% qq:=q;#je ne sais pas pourquoi, le by q ne marche pas sans ca!%%maintenant repare?
% S:={};
% for a from 0 to p do 
% L:={};
%% for i from 0 to (sqrt(p-a)) by evala(qq) do
% for i from 0 to (sqrt(p-a)) by q do 
% j:=normal(sqrt(p-a-i^2));
% if floor(j)==j and floor(j) mod q ==0 then L:= L union {[i,j],[-i,j],[i,-j],[-i,-j]} ;#NB: les ensembles simplifient les doublons
% fi  
% od
% if L<> {} then
%  for i from 1 to sqrt(a) by 2 do 
%  j:=normal(sqrt(a-i^2));
%   if floor(j)==j and floor(j) mod q == 0 then S:=S union {seq(augment([i,j],l),l=L),seq(augment([i,-j],l),l=L)}
%   fi;
%  od;
% fi;
% od;
% S;
% end:
% !s!
% chercheg(5,1); chercheg(5,2); transpose(chercheg(25,2));#on teste un peu
%chercheg(25,3); chercheg(5,11); chercheg(5^2,11); chercheg(5^3,11); chercheg(5^4,11);
% chercheg(5^5,11);
% chercheg(5^6,11);#Donc le tour de taille est 6?
% 44^2+117^2-5^6;
%!s!<c>
% (1+2*I)^6 voici un cycle de longueur 6. car 117+44*I donne une  homothetie
% dans PGL_2(ZZ/11/ZZ) 
% !s!
%(117+44*I)-(1+2*I)^6;
\end{document}
