L'exercice suivant est automatiquement et aléatoirement généré par ataraXy.
Si vous regénérez la page (F5) les valeurs seront changées.
La correction se trouve en bas de page.
Exercice
- Quelle propriété un graphe connexe \( \G\) doit vérifier pour être un arbre ?
- \( \Card(\Ar(\G))=\Card(\Som(\G))-1\)
- \( \Card(\Ar(\G))=\Card(\Som(\G))\)
- \( \Card(\Ar(\G))=\Card(\Som(\G))+1\)
Il est possible de reproduire ce dessin sans passer deux fois par la même arête et sans levé le crayon du papier. \[\xymatrix{
*=0{} \ar@{-}@/^1pc/[rr]\ar@{-}[d]\ar@{-}[rd]\ar@{-}[rrd] & *=0{} \ar@{-}[r]\ar@{-}[ld]\ar@{-}[d]\ar@{-}[rd] & *=0{} \ar@{-}[d] \\
*=0{} \ar@{-}[r] & *=0{} & *=0{}
}\]
Faux
Vrai
Soit \( \G\) le graphe orienté suivant : \[
\xymatrix{
A\ar[r]&B\ar@/^0.5pc/[rd]&C\ar[r]&D\ar[r]&E\\
J\ar[r]&I&H\ar@/^0.5pc/[lu]\ar@/^0.5pc/[llu]&G\ar@/^0.5pc/[r]&F\ar@/^0.5pc/[l]\ar@/^1.19pc/[lll]
}
\]
\( CC(G, \G)=\{F, G, I, J\}\)
\( CC(G, \G)=\{A, B, H\}\)
\( CC(G, \G)=\{C, D, E\}\)
Soit \( \G\) le graphe orienté suivant : \[\begin{array}{c||ccccc} & x_{1} & x_{2} & x_{3} & x_{4} & x_{5} \\\hline\hline x_{1} & 0 & 1 & 1 & 0 & 0\\ x_{2} & 1 & 1 & 0 & 0 & 1\\ x_{3} & 0 & 0 & 1 & 0 & 1\\ x_{4} & 0 & 0 & 0 & 1 & 1\\ x_{5} & 1 & 1 & 0 & 0 & 1\end{array}\]
\( d^{-1}(x_4, \G)=4\)
\( d^{-1}(x_4, \G)=1\)
\( d^{-1}(x_4, \G)=2\)
Soit \( \G\) le graphe orienté suivant : \[
\xymatrix{
A\ar[r]&B\ar@/^0.5pc/[rd]&C\ar[r]&D\ar[r]&E\\
J\ar[r]&I&H\ar@/^0.5pc/[lu]\ar@/^0.5pc/[llu]&G\ar@/^0.5pc/[r]&F\ar@/^0.5pc/[l]\ar@/^1.19pc/[lll]
}
\]
\( CCF(I, \G)=\{F, G, I, J\}\)
\( CCF(C \G)=\{C, D, E\}\)
\( CCF(F, \G)=\{F, G\}\)
Cliquer ici pour afficher la solution
Exercice
- Quelle propriété un graphe connexe \( \G\) doit vérifier pour être un arbre ?
- \( \Card(\Ar(\G))=\Card(\Som(\G))-1\)
- \( \Card(\Ar(\G))=\Card(\Som(\G))\)
- \( \Card(\Ar(\G))=\Card(\Som(\G))+1\)
Il est possible de reproduire ce dessin sans passer deux fois par la même arête et sans levé le crayon du papier. \[\xymatrix{
*=0{} \ar@{-}@/^1pc/[rr]\ar@{-}[d]\ar@{-}[rd]\ar@{-}[rrd] & *=0{} \ar@{-}[r]\ar@{-}[ld]\ar@{-}[d]\ar@{-}[rd] & *=0{} \ar@{-}[d] \\
*=0{} \ar@{-}[r] & *=0{} & *=0{}
}\]
Faux
Vrai
Soit \( \G\) le graphe orienté suivant : \[
\xymatrix{
A\ar[r]&B\ar@/^0.5pc/[rd]&C\ar[r]&D\ar[r]&E\\
J\ar[r]&I&H\ar@/^0.5pc/[lu]\ar@/^0.5pc/[llu]&G\ar@/^0.5pc/[r]&F\ar@/^0.5pc/[l]\ar@/^1.19pc/[lll]
}
\]
\( CC(G, \G)=\{F, G, I, J\}\)
\( CC(G, \G)=\{A, B, H\}\)
\( CC(G, \G)=\{C, D, E\}\)
Soit \( \G\) le graphe orienté suivant : \[\begin{array}{c||ccccc} & x_{1} & x_{2} & x_{3} & x_{4} & x_{5} \\\hline\hline x_{1} & 0 & 1 & 1 & 0 & 0\\ x_{2} & 1 & 1 & 0 & 0 & 1\\ x_{3} & 0 & 0 & 1 & 0 & 1\\ x_{4} & 0 & 0 & 0 & 1 & 1\\ x_{5} & 1 & 1 & 0 & 0 & 1\end{array}\]
\( d^{-1}(x_4, \G)=4\)
\( d^{-1}(x_4, \G)=1\)
\( d^{-1}(x_4, \G)=2\)
Soit \( \G\) le graphe orienté suivant : \[
\xymatrix{
A\ar[r]&B\ar@/^0.5pc/[rd]&C\ar[r]&D\ar[r]&E\\
J\ar[r]&I&H\ar@/^0.5pc/[lu]\ar@/^0.5pc/[llu]&G\ar@/^0.5pc/[r]&F\ar@/^0.5pc/[l]\ar@/^1.19pc/[lll]
}
\]
\( CCF(I, \G)=\{F, G, I, J\}\)
\( CCF(C \G)=\{C, D, E\}\)
\( CCF(F, \G)=\{F, G\}\)