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
- 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\}\)
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(H, \G)=\{A, B, H\}\)
\( CC(H, \G)=\{F, G, I, J\}\)
\( CC(H, \G)=\{C, D, E\}\)
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@{-}[r]\ar@{-}[rd]\ar@{-}[rrd] & *=0{} \ar@{-}[r]\ar@{-}[ld] & *=0{} \\
*=0{} \ar@{-}@/_1pc/[rr] & *=0{} \ar@{-}[r] & *=0{}
}\]
Faux
Vrai
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 & 1 & 1\\ x_{2} & 0 & 0 & 1 & 1 & 0\\ x_{3} & 0 & 0 & 0 & 1 & 0\\ x_{4} & 1 & 1 & 0 & 1 & 1\\ x_{5} & 0 & 1 & 0 & 0 & 0\end{array}\]
\( d^{-1}(x_2, \G)=3\)
\( d^{-1}(x_2, \G)=4\)
\( d^{-1}(x_2, \G)=1\)
Cliquer ici pour afficher la solution
Exercice
- 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\}\)
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(H, \G)=\{A, B, H\}\)
\( CC(H, \G)=\{F, G, I, J\}\)
\( CC(H, \G)=\{C, D, E\}\)
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@{-}[r]\ar@{-}[rd]\ar@{-}[rrd] & *=0{} \ar@{-}[r]\ar@{-}[ld] & *=0{} \\
*=0{} \ar@{-}@/_1pc/[rr] & *=0{} \ar@{-}[r] & *=0{}
}\]
Faux
Vrai
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 & 1 & 1\\ x_{2} & 0 & 0 & 1 & 1 & 0\\ x_{3} & 0 & 0 & 0 & 1 & 0\\ x_{4} & 1 & 1 & 0 & 1 & 1\\ x_{5} & 0 & 1 & 0 & 0 & 0\end{array}\]
\( d^{-1}(x_2, \G)=3\)
\( d^{-1}(x_2, \G)=4\)
\( d^{-1}(x_2, \G)=1\)