\documentclass[11pt]{article}

 \usepackage{ifthen}

  \usepackage[utf8]{inputenc}
 % \usepackage{fourier}

  \usepackage[svgnames]{xcolor}
 \usepackage{variations}
  \usepackage{geometry}
  \geometry{a4paper,hmargin=1cm,vmargin=1cm}

  \setlength{\parindent}{0pt}

  \usepackage{graphicx}
  \usepackage{ifpdf}
   \ifpdf
     \DeclareGraphicsRule{*}{mps}{*}{}
   \fi

  \usepackage{multicol}
  \setlength{\multicolsep}{12pt}
  \setlength{\columnsep}{40pt}
  \setlength{\columnseprule}{0pt}

  \usepackage{enumitem}
 % \setenumerate{align=left,leftmargin=*,noitemsep}
\setenumerate{align=left,leftmargin=*}
  \setenumerate[2]{label=\alph*),widest=a,ref=\theenumi.\alph*}
  \setitemize{nolistsep}

  \usepackage{amsmath,mathrsfs}
  \usepackage[np]{numprint}

  \usepackage[official,right]{eurosym}
  \usepackage[frenchb]{babel}
  \frenchbsetup{CompactItemize=false}
  \DecimalMathComma

\newcounter{exercice}
\newcounter{refex}
\renewcommand{\therefex}{\arabic{exercice}}
\newcounter{partie}[exercice]
\newcounter{refpart}
\renewcommand{\thepartie}{\Alph{partie}}
\renewcommand{\therefpart}{\Alph{partie}}

\makeatletter
\newenvironment{exercice}[1][]{%
		     \stepcounter{exercice}
		     \refstepcounter{refex}
		     \vspace{0.5em}
		     \par
                     \def\@svsechd{\large \color{white} \colorbox{purple}{\bfseries\arabic{exercice}}}%
                     \@xsect{-1em}%
                     \ifthenelse{\equal{#1}{}}{}{\textbf{#1}\par}%
                     }{\par\vspace{1.5em}}
\makeatother

\newenvironment{partie}[1][]{%
                     \stepcounter{partie}
                     \refstepcounter{refpart}
		      \par \vspace{0.5ex}\noindent
		     \textbf{Partie \thepartie \ifthenelse{\equal{#1}{}}{}{\quad -\quad#1}%
		     }\nopagebreak\par%
                     }{\par\vspace{1em}}



%%%%%%%%%%% Ensembles %%%%%%%%%%%%
\newcommand{\D}{\mathbb{D}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Z}{\mathbb{Z}}

%%%%%%%%%%% Intervalles %%%%%%%%%%%%
\newcommand{\intervalleOO}[2]{\left]{#1}\,{;}\,{#2}\right[}
\newcommand{\intervalleOF}[2]{\left]{#1}\,{;}\,{#2}\right]}
\newcommand{\intervalleFO}[2]{\left[{#1}\,{;}\,{#2}\right[}
\newcommand{\intervalleFF}[2]{\left[{#1}\,{;}\,{#2}\right]}

\newcommand{\couple}[2]{\left(#1\,{;}\,{#2}\right)}


\newcommand{\calc}{\mathscr{C}}
\newcommand{\cald}{\mathscr{D}}

%%%%%%%%%%%% Vecteurs %%%%%%%%%%%%%%%
\usepackage[e]{esvect}
\newcommand{\vect}[1]{\vv{#1}}
\newcommand{\repere}[3]{\left(#1\,{;}\,\vect{#2}{,}\,\vect{#3} \right)}
\newcommand{\oij}{\repere{O}{\imath}{\jmath}}
\newcommand{\barre}[1]{\overline{#1\rule{0.1em}{0ex}}}

%%%%%%%%%%%% Systèmes %%%%%%%%%%%%%%%
\newcommand{\sysd}[2]{%
       \left\{
       \begin{aligned}
          #1\\
          #2\\
       \end{aligned}
       \right.%
       }

\newcommand{\syst}[3]{%
       \left\{
       \begin{aligned}
          #1\\
          #2\\
	  #3
       \end{aligned}
       \right.%
       }

\newcommand{\sysq}[4]{%
       \left\{
       \begin{aligned}
          #1\\
          #2\\
	  #3
       \end{aligned}
       \right.%
       }




%%%%%%%%%%%% Divers %%%%%%%%%%%%%%%
\DeclareMathOperator{\card}{Card}


% perso nico

\newcommand{\orth}{\bot} % Pour faire le symbole perpendiculaire
\newcommand{\cm}{\,\mathrm{cm}} 
\newcommand{\pI}{{\ensuremath{+\infty}}} 
\newcommand{\mI}{{\ensuremath{-\infty}}} 

\newcommand{\cala}{\mathscr{A}}
\newcommand{\calb}{\mathscr{B}}
\newcommand{\calp}{\mathscr{P}}
\newcommand{\cale}{\mathscr{E}}
\newcommand{\calf}{\mathscr{F}}
\newcommand{\cals}{\mathscr{S}}
\newcommand{\calh}{\mathscr{H}}


\renewcommand{\i}{\mathrm{i}}

% pour écrire des limites
\newcommand{\limite}[2]{\displaystyle\lim_{#1\rightarrow #2}}

\newcommand{\ssi}{\Longleftrightarrow} % Pour faire le symbole equivalent
\newcommand{\implique}{\Longrightarrow} % Pour faire le symbole implique

\usepackage{enumitem}
\usepackage{xypic}

  \usepackage{amsmath}
  \usepackage{amssymb}
  \usepackage{amsfonts}
  \usepackage{mathrsfs}
%  \usepackage{shortlst}


\usepackage{pstricks,pst-plot,pst-text,pst-tree,pst-eps,pst-fill,pst-node,pst-math}

\newtheorem{remarque}{Remarque}
\newtheorem{remarque*}{Remarque}
\newtheorem{theorem*}{Théorème}
\newtheorem{definition*}{Définition}


% --------------------------------------------------------------------------------------------------

%devoir surveillé personalisé
% #1 titre principal, #2 titre milieu haut en petit, #3 titre haut
% gauche, #4 titre haut droit 
\newcommand{\devpers}[4]{
                         %\pagestyle{empty} 
                         \noindent 
                         \begin{minipage}[t]{\linewidth}
                         \textit{#3 } \hfill \textit{ #2} \hfill \textit{#4}
                         \end{minipage}
                         \begin{center}{{\Large\bf #1 }} \end{center} 
                         \vspace{-0.3cm}
                         \rule{\linewidth}{0.5mm} 
                         }

\newcommand{\cp}[2]{%
        \begin{pmatrix}
        #1\\
        #2
        \end{pmatrix}%
        }



\newenvironment{exnormal}[1]{
                             \addtocounter{exercice}{1}
                             \vspace{1em} \par \noindent
                              {\bf Exercice \arabic{exercice}{\bf #1 } :}
                            }{\vspace{0.25em}}

\newcommand{\ds}{\displaystyle}
\usepackage{calc}

%-------------- extension professor desiree :
%\usepackage[xcas]{pro-tablor}

\newcommand{\exo}[2]{\begin{exnormal}{~#2}}
\newcommand{\finexo}{\end{exnormal}}


\RequirePackage{enumitem}
\setenumerate{align=left,leftmargin=*,noitemsep}
\setenumerate[2]{label=\alph*),widest=a,ref=\theenumi.\alph*}
\setitemize{nolistsep}

\newenvironment{colenumerate}[2][]%
               {\let\olditem\item
                \let\item\myitem
                \setcounter{c@lonne}{0}
                \setcounter{colg@uche}{1}
                \setcounter{ligh@ut}{1}
                \setcounter{nbc@l}{#2}
               \newcommand{\c@lenumfinitem}{\par\vspace{0.5\parsep}
                            \setcounter{c@litem}{\value{\@enumctr}}
                            \end{enumerate}\strut
                             \end{minipage}%
                             }
                \newcommand{\c@lenumdebitem}{\begin{minipage}[c]{\l@rgcol}
                             \addtocounter{c@litem}{1}
                             \strut\begin{enumerate}[#1,start=\value{c@litem}]
                            }
               \par
               \vspace{-\baselineskip}
               \setlength{\l@rgcol}{(\linewidth-\parindent)/#2}
               \noindent\begin{minipage}[c]{\l@rgcol}
               \strut\begin{enumerate}[#1]
               }%
               {\vspace{0.5\parsep}\end{enumerate}\strut
               \end{minipage}
               \par\vspace{-\baselineskip}
               }


%inserer une figure à droite du texte 
%\textfig{largeur en %}{echelle}figure}+
\newsavebox{\maboite}
\newenvironment{textfig}[3]%
{\savebox{\maboite}{\begin{minipage}{\linewidth-#1\linewidth}
\begin{center}
\includegraphics[scale=#2]{#3}
\end{center}
\end{minipage}}
\begin{minipage}{#1\linewidth}}%
{\end{minipage} \usebox{\maboite}}

% \input{tabvar}
\pagestyle{empty} 

\begin{document}


\begin{center} \textbf{\large{Devoir nº9 - Matrices et Graphes - T maths exp}}  \end{center}
\begin{center}  \large{15 mai 2025 - 1h}  \end{center}



\exo{}{(4 pts)} On considère la matrice $A=\begin{pmatrix} -1 & 1 & 1  \\ 1 & -1 & 1 \\ 1 & 1 & -1 \end{pmatrix}$
\begin{enumerate}
\item Montrer que $A^2=2I_3-A$.
\medskip
\item En déduire que $A$ est inversible ; donner alors $A^{-1}$. 
\end{enumerate}
\finexo


\exo{}{(7 pts)} On considère les matrices $A=\begin{pmatrix} 1 & 2  \\ 3 & 2 \end{pmatrix}$ et $P=\begin{pmatrix} 1 & 2 \\ -1 & 3 \end{pmatrix}$.
\begin{enumerate}
\item Justifier que $P$ est inversible et calculer son inverse.
\medskip
\item Calculer le produit $D=P^{-1} \times A \times P$.
\medskip
\item \begin{enumerate}
    \item Pour tout entier naturel non nul $n$, conjecturer une expression de $D^n$.
    \smallskip
    \item Démontrer cette conjecture par récurrence.
    \end{enumerate}
\medskip
\item Exprimer alors $A^n$ en fonction de $n$, et des matrices $D$, $P$ et $P^{-1}$.
\end{enumerate}
\finexo

\newpage
\exo{}{(9 pts)} Un restaurateur se fournit auprès de 5 producteurs locaux. Le graphe ci-dessous représente la situation géographique du restaurateur et de ses fournisseurs, les arêtes correspondant au réseau routier et les sommets aux producteurs :

\begin{minipage}{8cm}
\begin{center}
{\psset{unit=1cm}
\begin{pspicture}(-1,0)(5,5)
\psdots(2,4.5)(2,0.5)(0.5,2)(3,3)(4.5,4.5)(3.75,1.25)%EFMPRV
\pspolygon(2,4.5)(0.5,2)(2,0.5)(3.75,1.25)(4.5,4.5)(3,3)
\psline(4.5,4.5)(2,4.5)(2,0.5)(3,3)(3.75,1.25)
\uput[u](2,4.5){E} \uput[d](2,0.5){F} \uput[l](0.5,2){M} 
\uput[u](3,3){P} \uput[u](4.5,4.5){R} \uput[d](3.75,1.25){V} 
\end{pspicture}}\end{center}
\end{minipage}
\begin{minipage}{6cm}
Légende :\par
E : éleveur\par
F : fromager\par
M : maraîcher\par
P : pisciculteur\par
R : \textbf{restaurateur}\par
V: vigneron 
\end{minipage}
   

\begin{enumerate}
\item Quel est l'ordre de ce graphe ?
\medskip
\item Citer deux sommets adjacents et deux sommets non adjacents.
\medskip
\item Le graphe est-il complet ?  Le graphe est-il connexe ?
\medskip
\item Est-il possible pour le restaurateur d'organiser une visite de tous ses producteurs en partant de son restaurant et en empruntant une fois et une seule chaque route ?\par Si oui, préciser le point d'arrivée et proposer un tel parcours.
\medskip
\item On appelle $N$ la matrice d'adjacence associée à ce graphe, les sommets étant  pris dans l'ordre alphabétique.             
	\begin{enumerate}
		\item Déterminer la matrice $N$. \par
		\smallskip
		\begin{minipage}{9cm}
        \item On donne la matrice $N^3 = \begin{pmatrix}
6   &10   &6   &10   &9   &5\\   
10   &6   &6  & 10   &5  & 9 \\
6&  6&2   &4   &4  & 4\\   
10   &10&4   &8  & 8  & 8\\   
9  & 5   &4   &8   &4   &8\\   
5  & 9   &4   &8   &8   &4
\end{pmatrix}$
		\end{minipage}
\begin{minipage}{6cm}
Déterminer, en justifiant la réponse, le nombre de chemins de longueur 3 reliant l'éleveur au vigneron. 
\end{minipage}
	\end{enumerate}
\medskip
\begin{minipage}{11cm}
\item Les arêtes du graphe sont pondérées par les distances, exprimées en kilomètre, entre les différents lieux.\par 
\medskip
 Le restaurateur doit se rendre chez le maraîcher en partant de chez lui. Quel est le plus court chemin pour effectuer ce trajet?\par 
 Justifier la réponse à l'aide d'un algorithme.
\end{minipage}
\begin{minipage}{5cm}
\begin{center}
\psset{unit=1cm}
\begin{pspicture}(5,5)
%\psgrid
\psdots(2,4.5)(2,0.5)(0.5,2)(3,3)(4.5,4.5)(3.75,1.25)%EFMPRV
\pspolygon(2,4.5)(0.5,2)(2,0.5)(3.75,1.25)(4.5,4.5)(3,3)
\psline(4.5,4.5)(2,4.5)(2,0.5)(3,3)(3.75,1.25)
\uput[u](2,4.5){E} \uput[d](2,0.5){F} \uput[l](0.5,2){M} 
\uput[u](3,3){P} \uput[u](4.5,4.5){R} \uput[d](3.75,1.25){V} 
\rput(1,3.4){8} \rput(1.2,1){2} \rput(2.9,1.1){1} \rput(1.8,2.6){6} 
\rput(2.4,3.4){3} \rput(3.2,4.7){5} \rput(3.8,3.4){4} \rput(4.3,2.7){10} 
\rput(3.2,2.2){5} \rput(2.8,1.9){7} 
\end{pspicture}
\end{center}
\end{minipage}
\end{enumerate}
\finexo





\end{document}
