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.
- 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(C \G)=\{C, D, E\}$
- $ CCF(I, \G)=\{F, G, I, J\}$
- $ 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(E, \G)=\{A, B, H\}$
$ CC(E, \G)=\{F, G, I, J\}$
$ CC(E, \G)=\{C, D, E\}$
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@{-}@/^1pc/[rr]\ar@{-}[d]\ar@{-}[rd] & *=0{} \ar@{-}[ld]\ar@{-}[d]\ar@{-}[rd] & *=0{} \ar@{-}[lld]\ar@{-}[ld]\ar@{-}[d] \\
*=0{} \ar@{-}[r]\ar@{-}@/_1pc/[rr] & *=0{} & *=0{}
}$$
Faux
Vrai
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$
Soit $ \G$ le graphe orienté suivant : $$\begin{array}{c||ccccc} & x_{1} & x_{2} & x_{3} & x_{4} & x_{5} \\\hline\hline x_{1} & 1 & 1 & 0 & 1 & 1\\ x_{2} & 1 & 1 & 0 & 0 & 0\\ x_{3} & 1 & 0 & 0 & 1 & 1\\ x_{4} & 1 & 1 & 1 & 0 & 1\\ x_{5} & 0 & 1 & 1 & 1 & 0\end{array}$$
$ d^{-1}(x_4, \G)=1$
$ d^{-1}(x_4, \G)=2$
$ d^{-1}(x_4, \G)=3$
Cliquer ici pour afficher la solution
- 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(C \G)=\{C, D, E\}$
- $ CCF(I, \G)=\{F, G, I, J\}$
- $ 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(E, \G)=\{A, B, H\}$
$ CC(E, \G)=\{F, G, I, J\}$
$ CC(E, \G)=\{C, D, E\}$
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@{-}@/^1pc/[rr]\ar@{-}[d]\ar@{-}[rd] & *=0{} \ar@{-}[ld]\ar@{-}[d]\ar@{-}[rd] & *=0{} \ar@{-}[lld]\ar@{-}[ld]\ar@{-}[d] \\
*=0{} \ar@{-}[r]\ar@{-}@/_1pc/[rr] & *=0{} & *=0{}
}$$
Faux
Vrai
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$
Soit $ \G$ le graphe orienté suivant : $$\begin{array}{c||ccccc} & x_{1} & x_{2} & x_{3} & x_{4} & x_{5} \\\hline\hline x_{1} & 1 & 1 & 0 & 1 & 1\\ x_{2} & 1 & 1 & 0 & 0 & 0\\ x_{3} & 1 & 0 & 0 & 1 & 1\\ x_{4} & 1 & 1 & 1 & 0 & 1\\ x_{5} & 0 & 1 & 1 & 1 & 0\end{array}$$
$ d^{-1}(x_4, \G)=1$
$ d^{-1}(x_4, \G)=2$
$ d^{-1}(x_4, \G)=3$