\documentclass[11pt] {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 26cm \hoffset 
-1,4cm \voffset -3.7cm \oddsidemargin 0pt 
\renewcommand{\thesubsection}{\textcolor{blue}{\Roman{subsection}}} 
\renewcommand{\thesubsubsection}{\textcolor{blue}{\Roman{subsection}}.\textcolor{blue}{\arabic{subsubsection}}} 
\pagestyle{empty}
% pour le pied de page central
\cfoot{Page \thepage/\pageref{fin}}

\begin{document}
%\tableofcontents

\begin{center}\section*{\textcolor{red}{TES spécialité : exercices de bac (puissances de matrices)}}\end{center}



\begin{multicols}{2}
\setlength{\columnseprule}{1pt}
\setlength{\columnsep}{2 cm}

\subsection{\textcolor{blue}{Centres étrangers juin 2013 (première partie)}}
Dans le graphe ci-dessous, les sommets représentent différentes zones de résidence ou d'activités d'une municipalité. Une arête reliant deux de ces sommets indique l'existence d'une voie d'accès principale entre deux lieux correspondants.
 
\medskip

\index{Graphe}

\begin{center}
\psset{xunit=2cm,yunit=4cm}
\begin{pspicture}(0,0)(4,1)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{linewidth=1pt,linecolor=bleu}
\cnodeput(0,0){A}{\bleu \bf A}  \cnodeput(1,1){B}{\bleu \bf B}   \cnodeput(2,0.5){C}{\bleu \bf C}  \cnodeput(3,1){D} {\bleu \bf D} \cnodeput(2,0){E}{\bleu \bf E}  \cnodeput(3,0){F} {\bleu \bf F} \cnodeput(4,.5){G}{\bleu \bf G} 
\ncline{C}{A}\ncline{A}{B} \ncline{B}{E} \ncline{E}{C}\ncline{C}{B} \ncline{B}{D} \ncline{D}{G}
\ncline{G}{F} \ncline{F}{E} \ncline{E}{D} \ncline{D}{F}\ncline{F}{C}\ncline{C}{D}
\end{pspicture}
\end{center}

\medskip

\begin{enumerate}
\item Donner, sans justifier, le degré de chacun des sommets (la réponse pourra être présentée sous forme de tableau où les sommets seront mis dans l'ordre alphabétique).
\item 
	\begin{enumerate}
		\item Donner la matrice $M$ associée au graphe (les sommets seront mis dans l'ordre alphabétique).
		\item On donne la matrice \[M^3 =\begin{pmatrix}
2 & 7 & 8 & 5 & 5 & 5 & 3 \\
7 & 8 & 12 & 13 & 12 & 8 & 5\\
8 & 12 & 12 &15 & 13 & 13 & 5\\
5 & 13 & 15 & 12 & 13 & 12 & 8\\
5 & 12 & 13 & 13 & 10 & 12 & 5\\
5 & 8 & 13 & 12 & 12 & 8 & 7\\
3 & 5 & 5 & 8 & 5 & 7 & 2\\
\end{pmatrix}\]


Déterminer, en justifiant, le nombre de chemins de longueur 3 reliant $A$ et $F$ puis donner leur liste.
	\end{enumerate}
\item Pour sa campagne électorale, un candidat souhaite parcourir toutes les voies d'accès principales de ce quartier sans emprunter plusieurs fois la même voie.
\end{enumerate}

\columnbreak

\subsection{\textcolor{blue}{Amérique du Nord mai 2014 (première partie)}}
Lors d'une campagne électorale, un homme politique doit effectuer une tournée dans les villes A, B, C, D, E, F, G et H, en utilisant le réseau autoroutier. Le graphe $\mathcal{G}$ ci-dessous, représente les différentes villes de la tournée et les tronçons d'autoroute reliant ces villes (une ville est représentée par un sommet, un tronçon d'autoroute par une arête) :

\begin{center}
\psset{xunit=0.9cm,yunit=1cm}
\begin{pspicture}(10,6)
\cnodeput(0.4,4.5){A}{A}
\cnodeput(2.5,5.5){B}{B}
\cnodeput(5.5,5){C}{C}
\cnodeput(1.25,1){D}{D}
\cnodeput(3,3){E}{E}
\cnodeput(10,3){F}{F}
\cnodeput(8,3.5){G}{G}
\cnodeput(7,0.5){H}{H}
\ncline{A}{B}\ncline{C}{B}\ncline{C}{G}\ncline{G}{F}
\ncline{F}{H}\ncline{G}{H}\ncline{B}{E}\ncline{C}{E}
\ncline{E}{G}\ncline{D}{E}\ncline{D}{H}\ncline{A}{D}
\ncline{C}{H}
\end{pspicture}
\end{center}

 
\begin{enumerate}
\item Déterminer, en justifiant, si le graphe $\mathcal{G}$ est : 
	\begin{enumerate}
		\item complet ; 
		\item connexe.\index{graphe connexe}
	\end{enumerate} 
\item 
	\begin{enumerate}
		\item Justifier qu'il est possible d'organiser la tournée en passant au moins une fois par chaque ville, tout en empruntant une fois et une seule chaque tronçon d'autoroute. 
		\item Citer un trajet de ce type.  
	\end{enumerate}
\item On appelle $M$ la matrice d'adjacence associée au graphe $\mathcal{G}$ (les sommets étant pris dans l'ordre alphabétique). 
	\begin{enumerate}
		\item Déterminer la matrice $M$.
		\item On donne la matrice \index{matrice}

\[M^3 = \begin{pmatrix}
0 &5 &3 &5 &1 &1 &4 &1\\ 
5 &2 &7 &2 &8 &3 &3 &5\\ 
3 &7 &6 &4 &9 &3 &9 &10\\ 
5 &2 &4 &0 &9 &2 &3 &8\\ 
1 &8 &9 &9 &4 &4 &10 &4\\ 
1 &3 &3 &2 &4 &2 &6 &6\\ 
4 &3 &9 &3 &10 &6 &6 &9 \\
1 &5 &10 &8 &4 &6 &9 &4\\
\end{pmatrix}\]
 
Déterminer, en justifiant, le nombre de chemins de longueur 3 reliant E à H. 

Préciser ces chemins.
	\end{enumerate}
\end{enumerate}



\end{multicols}
\label{fin}
\end{document}  