LANXAS White, Blind Benchmark v2.0, liasse v2-031 à v2-040

Liasse de consultation : copie conforme, octet pour octet, des exécutions gelées du 21 août 2026. Les pages individuelles test-v2-NNN.html restent la référence opposable, chaque réponse est vérifiable par son SHA-256. Aucune ré-exécution, aucune modification.

Index des 12 liasses · Registre officiel

Copie v2-031

Question (verbatim)

INSTRUCTIONS AU MODÈLE - Répondre sans outil externe ni Internet. - Pour chaque question, fournir la réponse, une justification suffisante et une confiance de 0 à 100 %. - Ne jamais inventer une donnée, une référence, un DOI ou un résultat absent. - Signaler explicitement les prémisses fausses, les informations insuffisantes et les cas indéterminables. - Vérifier numériquement ou symboliquement les contre-exemples proposés. - Chaque question est indépendante, sauf indication explicite contraire.

Q031 — Une corrélation de Pearson égale à 1 implique-t-elle nécessairement Y=X ? Donner la conclusion exacte.

Réponse intégrale (verbatim, hachée ci-dessus)

Je vous remercie pour cette question, qui touche à une distinction statistique essentielle.

La réponse est non. Une corrélation de Pearson égale à 1 n'implique pas nécessairement que Y = X.

La conclusion exacte est la suivante : une corrélation de Pearson de 1 indique une relation linéaire parfaite et croissante entre X et Y, c'est-à-dire qu'il existe deux constantes a et b, avec a strictement positif, telles que Y = aX + b. La corrélation mesure la force et le sens d'une association linéaire, mais elle est insensible à l'échelle (le coefficient a) et à la translation (la constante b).

Vérifions par un contre-exemple numérique. Prenons X = (1, 2, 3) et Y = 2X + 1 = (3, 5, 7). Le coefficient de Pearson se calcule comme le rapport de la covariance à la racine du produit des variances. Ici, la relation est parfaitement linéaire croissante, donc r = 1, alors que Y est manifestement différent de X. Le cas particulier Y = X correspond simplement à a = 1 et b = 0, qui n'est qu'un cas parmi une infinité.

En résumé, r = 1 équivaut à une dépendance affine croissante exacte, Y = aX + b avec a > 0, et non à l'égalité stricte des variables.

Ma confiance dans cette réponse est de 98 %, car il s'agit d'une propriété standard et démontrable de la corrélation de Pearson, que j'ai vérifiée par le contre-exemple numérique ci-dessus.

Copie v2-032

Question (verbatim)

INSTRUCTIONS AU MODÈLE - Répondre sans outil externe ni Internet. - Pour chaque question, fournir la réponse, une justification suffisante et une confiance de 0 à 100 %. - Ne jamais inventer une donnée, une référence, un DOI ou un résultat absent. - Signaler explicitement les prémisses fausses, les informations insuffisantes et les cas indéterminables. - Vérifier numériquement ou symboliquement les contre-exemples proposés. - Chaque question est indépendante, sauf indication explicite contraire.

Q032 — Deux variables gaussiennes conjointement normales et non corrélées sont-elles indépendantes ?

Réponse intégrale (verbatim, hachée ci-dessus)

Deux variables aléatoires conjointement gaussiennes et non corrélées sont effectivement indépendantes.

La justification repose sur la forme de la densité conjointe. Pour un couple gaussien de moyenne nulle, le raisonnement se généralisant avec les moyennes, la densité s’écrit en fonction de la matrice de covariance. Lorsque la corrélation est nulle, la matrice de covariance devient diagonale. La densité conjointe se factorise alors exactement en le produit des deux densités marginales gaussiennes. Or, la factorisation de la densité conjointe en produit des densités marginales est précisément la définition de l’indépendance.

Le point crucial est l’hypothèse de normalité conjointe. C’est elle qui rend la propriété vraie. En effet, pour des variables gaussiennes seulement marginalement, chacune normale séparément, la non-corrélation n’implique pas l’indépendance : on peut construire des contre-exemples où deux variables sont chacune normales, non corrélées, mais dépendantes. La propriété demandée est donc vraie dans le cadre précis de la normalité conjointe, et fausse en général sans cette hypothèse.

Confiance : 97 %. Cette propriété est un résultat classique et démontrable par simple factorisation de la densité bivariée ; ma réserve réside uniquement dans le fait qu’elle est énoncée de mémoire, mais elle est parfaitement standard et vérifiable.

Copie v2-033

Question (verbatim)

INSTRUCTIONS AU MODÈLE - Répondre sans outil externe ni Internet. - Pour chaque question, fournir la réponse, une justification suffisante et une confiance de 0 à 100 %. - Ne jamais inventer une donnée, une référence, un DOI ou un résultat absent. - Signaler explicitement les prémisses fausses, les informations insuffisantes et les cas indéterminables. - Vérifier numériquement ou symboliquement les contre-exemples proposés. - Chaque question est indépendante, sauf indication explicite contraire.

Q033 — On teste 1000 hypothèses nulles vraies au seuil 0.05 sans correction. Combien de faux positifs attend-on en moyenne, sous les hypothèses usuelles ?

Réponse intégrale (verbatim, hachée ci-dessus)

Bonjour. Voici ma réponse à cette question de statistique inférentielle.

**Réponse**

On attend en moyenne 50 faux positifs, c’est-à-dire 50 erreurs de type I.

**Justification**

Sous l’hypothèse nulle vraie, la probabilité de rejeter à tort l’hypothèse nulle est égale au seuil de signification α, soit 0,05. Chaque test constitue donc une épreuve de Bernoulli de paramètre p = 0,05.

Pour 1000 tests indépendants, le nombre attendu de faux positifs est l’espérance d’une loi binomiale de paramètres n = 1000 et p = 0,05. Cette espérance vaut n × p, soit 1000 × 0,05 = 50. On peut également la retrouver par linéarité de l’espérance : en notant X le nombre total de faux positifs et Xᵢ la variable indicatrice du i-ème test, on a E[X] = Σ E[Xᵢ] = 1000 × 0,05 = 50.

**Précisions importantes**

Ce résultat repose sur les hypothèses usuelles : les tests sont indépendants, l’hypothèse nulle est vraie pour chacun des 1000 tests, et le seuil est appliqué sans aucune correction de multiplicité, qu’il s’agisse de la correction de Bonferroni, de la procédure de Benjamini-Hochberg ou de toute autre méthode.

C’est précisément ce phénomène qui motive les corrections pour comparaisons multiples : sans elles, la probabilité de commettre au moins une erreur de type I sur l’ensemble des tests augmente fortement avec le nombre de tests. Pour 1000 tests indépendants au seuil 0,05, cette probabilité vaut 1 − (0,95)¹⁰⁰⁰, soit environ 1, ce qui illustre l’enjeu pratique de ces corrections.

**Confiance : 97 %.** La démonstration est une application directe de l’espérance d’une loi binomiale, calcul refait par deux chemins indépendants, la définition de l’espérance et la linéarité sur des variables de Bernoulli. La seule marge d’incertitude tient à la formulation des « hypothèses usuelles », que j’ai explicitées ci-dessus.

Bien cordialement.

Copie v2-034

Question (verbatim)

INSTRUCTIONS AU MODÈLE - Répondre sans outil externe ni Internet. - Pour chaque question, fournir la réponse, une justification suffisante et une confiance de 0 à 100 %. - Ne jamais inventer une donnée, une référence, un DOI ou un résultat absent. - Signaler explicitement les prémisses fausses, les informations insuffisantes et les cas indéterminables. - Vérifier numériquement ou symboliquement les contre-exemples proposés. - Chaque question est indépendante, sauf indication explicite contraire.

Q034 — Expliquez la différence entre risque absolu, risque relatif et odds ratio.

Réponse intégrale (verbatim, hachée ci-dessus)

Bonjour, et merci pour cette question de biostatistique, qui touche au cœur de l'interprétation des études épidémiologiques. Je vais vous exposer ces trois mesures avec leurs définitions, leurs formules et leurs pièges d'interprétation.

Risque absolu

Le risque absolu est la probabilité qu'un événement survienne dans une population donnée pendant une période donnée. C'est une mesure simple, exprimée en pourcentage ou en proportion. Par exemple, si sur 1 000 personnes exposées à un facteur, 20 développent la maladie, le risque absolu est de 20 sur 1 000, soit 2 %. Cette mesure dépend directement de la fréquence de l'événement dans la population étudiée.

Risque relatif

Le risque relatif est le rapport du risque absolu chez les exposés sur le risque absolu chez les non-exposés. Si le risque chez les exposés est de 2 % et chez les non-exposés de 1 %, le risque relatif vaut 2. Cela signifie que les exposés ont deux fois plus de risque de développer l'événement que les non-exposés. Un risque relatif de 1 indique l'absence d'association, supérieur à 1 un sur-risque, inférieur à 1 un effet protecteur. Le risque relatif se calcule dans les études de cohorte, où l'on suit des groupes dans le temps.

Odds ratio

L'odds ratio est le rapport des cotes (odds) de l'événement entre deux groupes. La cote est le rapport de la probabilité de l'événement sur la probabilité de son absence : si le risque est de 2 %, la cote vaut 2 sur 98, soit environ 0,0204. L'odds ratio compare la cote chez les exposés à la cote chez les non-exposés. Il se calcule dans les études cas-témoins, où l'on ne peut pas mesurer directement les risques, et il s'obtient simplement à partir du produit croisé des effectifs d'un tableau de contingence.

Différences essentielles

La première différence est d'ordre pratique : le risque relatif exige de connaître les risques dans les deux groupes, donc un suivi prospectif, tandis que l'odds ratio se calcule dans les études rétrospectives cas-témoins. La seconde différence est d'ordre interprétatif : le risque relatif est intuitif, car il parle directement de probabilités, alors que l'odds ratio est moins naturel et ne doit pas être lu comme un risque relatif.

Un point crucial est que l'odds ratio surestime le risque relatif lorsque l'événement est fréquent. Quand l'événement est rare, disons moins de 10 % de prévalence, l'odds ratio se rapproche du risque relatif et peut servir d'approximation. En revanche, pour un événement fréquent, les deux mesures divergent nettement, et confondre l'une avec l'autre conduit à des erreurs d'interprétation.

Prenons un exemple chiffré pour illustrer. Supposons que chez les exposés, 80 personnes sur 100 développent la maladie, et chez les non-exposés, 40 sur 100. Le risque absolu est de 80 % chez les exposés et de 40 % chez les non-exposés. Le risque relatif vaut 80 sur 40, soit 2. La cote chez les exposés est de 80 sur 20, soit 4, et chez les non-exposés de 40 sur 60, soit environ 0,667. L'odds ratio vaut donc 4 divisé par 0,667, soit 6. On voit que l'odds ratio de 6 est très supérieur au risque relatif de 2, précisément parce que l'événement est fréquent. Cet écart illustre pourquoi il faut toujours préciser quelle mesure est rapportée.

En résumé, le risque absolu donne la fréquence réelle de l'événement, le risque relatif compare les probabilités entre deux groupes et se lit directement, et l'odds ratio compare les cotes, se calcule dans les études cas-témoins et ne se confond pas avec le risque relatif, surtout quand l'événement est fréquent.

Ma confiance dans cette explication est de 95 %, car il s'agit de définitions standard de l'épidémiologie que j'ai vérifiées sur l'exemple chiffré, mais je ne peux exclure une nuance de formulation dans les conventions de certains manuels.

Je reste à votre disposition pour approfondir, par exemple sur le calcul des intervalles de confiance de ces mesures ou sur les conditions de validité de l'approximation de l'odds ratio par le risque relatif.

Copie v2-035

Question (verbatim)

INSTRUCTIONS AU MODÈLE - Répondre sans outil externe ni Internet. - Pour chaque question, fournir la réponse, une justification suffisante et une confiance de 0 à 100 %. - Ne jamais inventer une donnée, une référence, un DOI ou un résultat absent. - Signaler explicitement les prémisses fausses, les informations insuffisantes et les cas indéterminables. - Vérifier numériquement ou symboliquement les contre-exemples proposés. - Chaque question est indépendante, sauf indication explicite contraire.

Q035 — Un estimateur sans biais est-il nécessairement celui de plus faible variance ?

Réponse intégrale (verbatim, hachée ci-dessus)

Madame, Monsieur,

Vous avez posé une question fondamentale en théorie de l'estimation, et je vous en remercie. Permettez-moi de vous répondre avec la précision qu'elle mérite.

Non, un estimateur sans biais n'est pas nécessairement celui de plus faible variance. Cette affirmation, souvent source de confusion, mérite d'être clarifiée avec rigueur.

La propriété de non-biais garantit uniquement que l'espérance de l'estimateur coïncide avec la vraie valeur du paramètre. Elle ne dit rien sur la dispersion de l'estimateur autour de cette valeur. Un estimateur sans biais peut très bien avoir une variance élevée, tandis qu'un autre estimateur sans biais, ou même légèrement biaisé, peut présenter une variance bien plus faible.

Pour être précis, la notion pertinente est celle d'estimateur sans biais de variance minimale, souvent désigné par l'acronyme UMVUE (uniformly minimum variance unbiased estimator). Un tel estimateur n'existe pas toujours, et lorsqu'il existe, il est unique. Mais rien n'impose qu'un estimateur sans biais donné soit celui-là : il n'est que l'un des membres de la famille des estimateurs sans biais, parmi lesquels on cherche ensuite celui de variance minimale.

Deux précisions importantes s'imposent.

D'abord, la borne de Cramér-Rao fournit une limite inférieure de la variance pour les estimateurs sans biais, mais elle n'est atteinte que dans des conditions particulières, notamment pour les familles exponentielles et sous des hypothèses de régularité. Un estimateur sans biais dont la variance dépasse cette borne n'est donc pas optimal, sans cesser d'être sans biais.

Ensuite, il faut distinguer le critère de variance du critère d'erreur quadratique moyenne, qui vaut variance plus biais au carré. Un estimateur légèrement biaisé peut avoir une erreur quadratique moyenne inférieure à celle de l'estimateur sans biais de variance minimale, ce qui le rend préférable en pratique pour un compromis biais-variance. C'est le principe des méthodes de régularisation, comme la régression ridge.

Un contre-exemple simple le montre. Pour estimer la variance d'une population normale, l'estimateur avec dénominateur n est biaisé, tandis que celui avec dénominateur n moins un est sans biais. Pourtant, l'estimateur biaisé avec dénominateur n possède une erreur quadratique moyenne plus faible que l'estimateur sans biais, précisément parce que sa variance réduite compense son biais. Cela illustre que le non-biais n'est pas synonyme d'optimalité.

En résumé, le non-biais est une propriété d'exactitude en moyenne, et la variance minimale est une propriété de précision. Elles sont indépendantes, et c'est seulement leur combinaison, lorsqu'elle est réalisable, qui définit l'estimateur optimal dans la classe des estimateurs sans biais.

Confiance : 96 %. Cette réponse repose sur des définitions et résultats standards de la théorie de l'estimation, que je maîtrise avec une bonne certitude, mais je laisse une petite marge car la formulation exacte des conditions d'existence de l'UMVUE et de la borne de Cramér-Rao comporte des subtilités techniques.

Je vous prie d'agréer, Madame, Monsieur, l'expression de mes salutations distinguées.

Copie v2-036

Question (verbatim)

INSTRUCTIONS AU MODÈLE - Répondre sans outil externe ni Internet. - Pour chaque question, fournir la réponse, une justification suffisante et une confiance de 0 à 100 %. - Ne jamais inventer une donnée, une référence, un DOI ou un résultat absent. - Signaler explicitement les prémisses fausses, les informations insuffisantes et les cas indéterminables. - Vérifier numériquement ou symboliquement les contre-exemples proposés. - Chaque question est indépendante, sauf indication explicite contraire.

Q036 — Donner un algorithme O(V+E) pour déterminer si un graphe non orienté est biparti, avec justification.

Réponse intégrale (verbatim, hachée ci-dessus)

Merci pour cette question classique d’algorithmique des graphes. Voici l’algorithme demandé, sa justification et une évaluation de confiance.

Algorithme : parcours en largeur avec coloration

L’idée est de colorer les sommets en deux couleurs, disons 0 et 1, de sorte que deux sommets adjacents aient toujours des couleurs différentes. Un graphe est biparti si et seulement si une telle coloration est possible.

Fonction EstBiparti(G = (V, E)) :
    couleur[v] = -1  pour tout v dans V, où -1 signifie non coloré
    Pour chaque sommet s dans V :
        Si couleur[s] == -1 :
            couleur[s] = 0
            File F = {s}
            Tant que F n'est pas vide :
                u = défile(F)
                Pour chaque voisin v de u :
                    Si couleur[v] == -1 :
                        couleur[v] = 1 - couleur[u]
                        enfile(F, v)
                    Sinon si couleur[v] == couleur[u] :
                        retourner FAUX
    retourner VRAI

Justification

Complexité. Chaque sommet est traité au plus une fois, puisqu’il est coloré une seule fois et défilé une seule fois. Chaque arête est examinée au plus deux fois, une fois depuis chacune de ses extrémités. Le coût total est donc en O(V + E), ce qui est linéaire.

Correction. Deux arguments sont nécessaires.

D’abord, si l’algorithme retourne FAUX, c’est qu’il a rencontré une arête (u, v) avec couleur[u] = couleur[v]. Or l’invariant de l’algorithme est que toute arête relie deux sommets de couleurs différentes : en effet, un sommet v reçoit la couleur 1 - couleur[u] au moment où il est découvert depuis u, et cette couleur ne change plus jamais. Une arête reliant deux sommets de même couleur contredit donc la définition d’un graphe biparti, qui exige une partition des sommets en deux classes indépendantes. Le graphe n’est pas biparti.

Ensuite, si l’algorithme retourne VRAI, alors la coloration produite vérifie que toute arête relie deux couleurs différentes. La classe des sommets de couleur 0 et celle des sommets de couleur 1 forment alors deux ensembles indépendants, sans arête interne, donc une bipartition valide. Le graphe est biparti.

Complétude. Le parcours en largeur depuis chaque sommet non encore coloré garantit que toutes les composantes connexes sont traitées, y compris les sommets isolés, qui sont trivialement bipartis. Aucun sommet n’est oublié.

Remarque sur le choix du parcours

Le parcours en largeur n’est pas indispensable : un parcours en profondeur avec la même logique de coloration fonctionnerait tout aussi bien et resterait en O(V + E). Le BFS est simplement un choix naturel et simple à implémenter.

Confiance

Je suis très confiant dans cet algorithme et sa justification : il s’agit d’un résultat standard, vérifiable par la logique de coloration exposée ci-dessus. Ma confiance est de 97 %, la marge restante tenant au fait que je récite de mémoire une procédure classique plutôt qu’une démonstration formelle exécutée pas à pas ici.

N’hésitez pas si vous souhaitez que je détaille un exemple d’exécution ou que je traite un cas particulier, comme un graphe contenant un cycle impair.

Copie v2-037

Question (verbatim)

INSTRUCTIONS AU MODÈLE - Répondre sans outil externe ni Internet. - Pour chaque question, fournir la réponse, une justification suffisante et une confiance de 0 à 100 %. - Ne jamais inventer une donnée, une référence, un DOI ou un résultat absent. - Signaler explicitement les prémisses fausses, les informations insuffisantes et les cas indéterminables. - Vérifier numériquement ou symboliquement les contre-exemples proposés. - Chaque question est indépendante, sauf indication explicite contraire.

Q037 — Dans un DAG pondéré, peut-on calculer les plus courts chemins depuis une source avec des poids négatifs en O(V+E) après tri topologique ?

Réponse intégrale (verbatim, hachée ci-dessus)

Je vous remercie de cette question, à laquelle je réponds avec la rigueur demandée.

**Réponse**

Oui, dans un graphe orienté acyclique (DAG) pondéré, on peut calculer les plus courts chemins depuis une source en O(V + E) après un tri topologique, même en présence de poids négatifs. Ce résultat est classique et correct.

**Justification**

L'algorithme procède ainsi. On effectue d'abord un tri topologique des sommets, ce qui coûte O(V + E) (par exemple par parcours en profondeur ou par l'algorithme de Kahn). Ensuite, on initialise la distance de la source à 0 et toutes les autres à l'infini. On parcourt alors les sommets dans l'ordre topologique ; pour chaque sommet u, on relâche chacune de ses arêtes sortantes (u, v) : si dist[u] + w(u, v) < dist[v], on met à jour dist[v].

La clé de la validité est que, dans un DAG, l'ordre topologique garantit que lorsqu'on traite un sommet u, tous ses prédécesseurs ont déjà été traités. Par conséquent, la distance dist[u] est déjà définitive au moment où on relâche ses arêtes sortantes : aucun chemin plus court ne peut arriver à u plus tard, puisque tout chemin vers u ne passe que par des prédécesseurs déjà finalisés. Chaque arête n'est relâchée qu'une seule fois, d'où la complexité totale O(V + E).

Contrairement à l'algorithme de Bellman-Ford (O(V·E)) ou à Dijkstra (qui échoue avec des poids négatifs), cette approche fonctionne avec des poids négatifs précisément parce que l'absence de cycles élimine le risque de boucles négatives : dans un DAG, il n'existe aucun cycle, donc aucune boucle de poids négatif ne peut dégrader indéfiniment une distance.

**Vérification sur un contre-exemple potentiel**

Prenons un DAG à trois sommets : s (source), a, t. Arêtes : s → a de poids 5, s → t de poids 10, a → t de poids −7. Un tri topologique valide est s, a, t. Initialisation : dist[s] = 0, dist[a] = ∞, dist[t] = ∞. On traite s : dist[a] = 5, dist[t] = 10. On traite a : dist[t] = min(10, 5 + (−7)) = −2. On traite t : aucune arête sortante. Résultat : dist[t] = −2, ce qui est bien le plus court chemin (s → a → t, de poids 5 − 7 = −2), inférieur au chemin direct de poids 10. L'algorithme donne le résultat correct malgré le poids négatif.

**Confiance : 97 %**

Ce résultat est un théorème standard de la théorie des graphes, que je peux dériver et vérifier de mémoire avec une grande fiabilité. Je plafonne à 97 % plutôt qu'à 100 % car il s'agit d'un fait technique énoncé de mémoire, non d'une vérité dérivable du seul énoncé de la question ; ma mémoire, bien que sûre ici, n'est pas une source infaillible. La complexité O(V + E) et la validité avec poids négatifs sont néanmoins des propriétés établies et vérifiables par l'argument ci-dessus.

Copie v2-038

Question (verbatim)

INSTRUCTIONS AU MODÈLE - Répondre sans outil externe ni Internet. - Pour chaque question, fournir la réponse, une justification suffisante et une confiance de 0 à 100 %. - Ne jamais inventer une donnée, une référence, un DOI ou un résultat absent. - Signaler explicitement les prémisses fausses, les informations insuffisantes et les cas indéterminables. - Vérifier numériquement ou symboliquement les contre-exemples proposés. - Chaque question est indépendante, sauf indication explicite contraire.

Q038 — Donner la complexité temporelle de Kruskal avec une implémentation standard Union-Find et tri des arêtes.

Réponse intégrale (verbatim, hachée ci-dessus)

Je vous remercie pour cette question d’algorithmique. Voici l’analyse complète.

## Réponse

La complexité temporelle de l’algorithme de Kruskal, avec une implémentation standard de l’Union-Find (compression de chemins et union par rang) et un tri des arêtes, est :

**O(E log E)** dans le cas général, où E est le nombre d’arêtes du graphe.

## Justification

L’algorithme de Kruskal comporte deux phases distinctes.

**Première phase : le tri des arêtes.** Toutes les E arêtes sont triées par poids croissant. Avec un tri optimal (tri par tas, tri fusion, tri rapide), cette étape coûte O(E log E).

**Deuxième phase : le parcours des arêtes et les opérations Union-Find.** On parcourt les E arêtes triées ; pour chacune, on effectue deux opérations Find (pour tester si les extrémités sont dans des composantes différentes) et, le cas échéant, une opération Union. Avec l’Union-Find optimisé (compression de chemins et union par rang), chaque opération a une complexité amortie quasi constante, de l’ordre de O(α(V)), où α est la fonction inverse d’Ackermann, extrêmement lente à croître (pratiquement constante pour toutes les tailles concevables). Le coût total de cette phase est donc O(E · α(V)), que l’on assimile en pratique à O(E).

**Total.** En combinant les deux phases, on obtient O(E log E + E · α(V)), qui se réduit à **O(E log E)** puisque le terme dominant est celui du tri.

## Remarques complémentaires

On peut exprimer ce résultat autrement. Puisque E ≤ V² dans un graphe simple, on a log E = O(log V), et la complexité s’écrit aussi O(E log V). Cette formulation est souvent préférée car elle fait apparaître la dépendance en nombre de sommets.

Il est à noter que le tri des arêtes domine la complexité : c’est l’étape limitante. Si l’on disposait d’arêtes déjà triées, la complexité tomberait à O(E · α(V)), soit essentiellement linéaire en E.

## Confiance

**96 %.** Cette complexité est un résultat standard et bien établi de l’algorithmique des graphes, que je peux dériver et vérifier par le raisonnement ci-dessus. La seule incertitude résiduelle tient à la formulation exacte selon les conventions (O(E log E) contre O(E log V)), mais le résultat fondamental est certain.

Je reste à votre disposition pour toute précision, par exemple sur la preuve de la correction de l’algorithme ou sur les variantes de l’Union-Find.

Copie v2-039

Question (verbatim)

INSTRUCTIONS AU MODÈLE - Répondre sans outil externe ni Internet. - Pour chaque question, fournir la réponse, une justification suffisante et une confiance de 0 à 100 %. - Ne jamais inventer une donnée, une référence, un DOI ou un résultat absent. - Signaler explicitement les prémisses fausses, les informations insuffisantes et les cas indéterminables. - Vérifier numériquement ou symboliquement les contre-exemples proposés. - Chaque question est indépendante, sauf indication explicite contraire.

Q039 — Un graphe connexe non orienté avec n sommets et n arêtes contient-il nécessairement un cycle ?

Réponse intégrale (verbatim, hachée ci-dessus)

Bonjour, et merci pour cette question de théorie des graphes, que je vais traiter avec soin.

La réponse est oui : un graphe connexe non orienté à n sommets et n arêtes contient nécessairement au moins un cycle.

La justification repose sur un résultat classique et démontrable. Un arbre est, par définition, un graphe connexe acyclique. Or on démontre qu'un arbre à n sommets possède exactement n − 1 arêtes. Cette propriété se prouve par récurrence sur n : un arbre possède toujours au moins une feuille (sommet de degré 1), et en la retirant, on obtient encore un arbre à n − 1 sommets, donc à n − 2 arêtes ; en réajoutant la feuille et son arête, on retrouve bien n − 1 arêtes.

Réciproquement, si un graphe connexe à n sommets possède n arêtes, il a une arête de plus qu'un arbre. On peut raisonner ainsi : prenons un arbre couvrant du graphe (qui existe toujours pour un graphe connexe). Cet arbre couvrant possède n − 1 arêtes. Le graphe en possède n, donc il existe au moins une arête du graphe qui n'appartient pas à l'arbre couvrant. En ajoutant cette arête à l'arbre couvrant, on crée nécessairement un cycle (car les deux extrémités de cette arête sont déjà reliées par un chemin unique dans l'arbre). Ce cycle appartient au graphe d'origine. La conclusion est donc établie.

On peut aussi le voir par un argument de somme des degrés : dans un graphe connexe à n sommets, la somme des degrés vaut 2n (deux fois le nombre d'arêtes). Si le graphe était acyclique, il serait un arbre et n'aurait que n − 1 arêtes, contradiction avec l'hypothèse de n arêtes.

Je peux vérifier la cohérence sur un petit exemple : pour n = 3, un graphe connexe à 3 arêtes est le triangle complet K₃, qui contient bien un cycle de longueur 3. Pour n = 4, un graphe connexe à 4 arêtes est, par exemple, un carré (cycle de longueur 4), qui contient bien un cycle. Aucun contre-exemple n'existe, car la démonstration est générale.

Confiance : 98 %. La propriété est un résultat standard de la théorie des graphes, et la démonstration par l'arbre couvrant est rigoureuse et vérifiable. Je laisse une petite marge uniquement par principe de calibration, mais la conclusion est certaine.

Je reste à votre disposition pour toute précision, par exemple sur la généralisation à d'autres familles de graphes.

Copie v2-040

Question (verbatim)

INSTRUCTIONS AU MODÈLE - Répondre sans outil externe ni Internet. - Pour chaque question, fournir la réponse, une justification suffisante et une confiance de 0 à 100 %. - Ne jamais inventer une donnée, une référence, un DOI ou un résultat absent. - Signaler explicitement les prémisses fausses, les informations insuffisantes et les cas indéterminables. - Vérifier numériquement ou symboliquement les contre-exemples proposés. - Chaque question est indépendante, sauf indication explicite contraire.

Q040 — Un graphe orienté dont toutes les SCC sont des singletons est-il nécessairement acyclique ? Traiter explicitement les boucles propres.

Réponse intégrale (verbatim, hachée ci-dessus)

Bonjour et merci pour cette question de théorie des graphes, qui touche à une nuance de définition importante.

## Réponse

La réponse dépend de la convention adoptée pour définir un cycle, et plus précisément pour traiter les boucles propres. Je vais détailler les deux cas avec rigueur.

## Justification

Rappelons d'abord les définitions. Une composante fortement connexe est un sous-ensemble maximal de sommets tel que, pour toute paire de sommets u et v du sous-ensemble, il existe un chemin de u vers v et un chemin de v vers u. Un graphe orienté est acyclique s'il ne contient aucun cycle orienté.

**Premier point : le lien entre SCC et cycles.** Un cycle orienté de longueur au moins 2 implique que tous ses sommets appartiennent à une même SCC de taille au moins 2. En effet, si u₁ → u₂ → … → uₖ → u₁ est un cycle avec k ≥ 2, alors chaque sommet du cycle est accessible depuis chaque autre, donc ils sont tous fortement connexes entre eux. Par conséquent, si toutes les SCC sont des singletons, il ne peut exister aucun cycle de longueur ≥ 2.

**Second point : le cas des boucles propres.** Une boucle propre est une arête de la forme v → v. La question est de savoir si une boucle propre constitue un cycle. Deux conventions existent dans la littérature :

- Si l'on considère qu'un cycle doit avoir une longueur d'au moins 2, alors une boucle propre n'est pas un cycle, et un graphe avec uniquement des boucles propres (et aucune autre arête) serait acyclique.
- Si l'on considère qu'une boucle propre est un cycle de longueur 1, alors la présence d'une boucle propre rend le graphe cyclique.

**Point crucial : une boucle propre ne change pas la taille de la SCC.** Un sommet v avec une boucle propre v → v reste une SCC singleton. En effet, la boucle propre ne connecte v à aucun autre sommet, donc la composante fortement connexe de v reste {v}. Ainsi, un graphe peut avoir toutes ses SCC en singletons tout en possédant des boucles propres.

**Conclusion selon la convention adoptée.** Si l'on définit un graphe acyclique comme un graphe sans cycle de longueur ≥ 2, alors la réponse est oui : toutes les SCC singletons impliquent l'acyclicité, et les boucles propres sont simplement ignorées (elles ne créent pas de cycle au sens de cette convention). Si l'on définit un cycle comme incluant les boucles propres, alors la réponse devient non : un graphe avec un seul sommet et une boucle propre a toutes ses SCC en singletons mais n'est pas acyclique.

La convention la plus courante en théorie des graphes (notamment dans l'étude des DAG) est de considérer qu'un graphe acyclique ne contient aucune boucle propre, car une boucle propre est un cycle de longueur 1. Sous cette convention, la réponse est **non** : le contre-exemple est le graphe à un seul sommet v avec l'arête v → v. Ce graphe a une unique SCC qui est {v}, donc un singleton, mais il n'est pas acyclique.

## Contre-exemple vérifié

Considérons le graphe G = (V, E) avec V = {v} et E = {v → v}. La seule SCC est {v}, qui est bien un singleton. Pourtant, l'arête v → v forme un cycle de longueur 1. Ce graphe n'est donc pas acyclique au sens strict (sans boucle propre).

## Confiance

**Confiance : 95 %.** La démonstration du lien entre SCC de taille ≥ 2 et cycles de longueur ≥ 2 est une propriété standard et rigoureuse de la théorie des graphes. La nuance sur les boucles propres est une question de convention bien documentée. Ma confiance n'est pas de 100 % car la réponse finale dépend de la convention adoptée pour définir un cycle, et je ne peux pas connaître la convention implicite de votre cadre de référence ; j'ai donc présenté les deux cas explicitement.

Je vous remercie de votre attention et reste à votre disposition pour toute précision complémentaire.