Inscription / Connexion Nouveau Sujet
croisement
Bonjour , j'espère que vous allez bien. Je bloque à l'exercice suivant :
Soit G = (S, A) un graphe simple, le nombre de croisement, noté Cr (G), est le nombre minimal de croisement necessaire pour dessiner ´G dans le plan.
1-Montrer par recurrence sur le nombre d'arêtes que Cr ˆ(G) ≥ |A| − 3|S|.
2-Soit G = (S, A) un graphe, on note |S| = s et |A| = a. Soit p ∈ [0, 1]. On choisit de maniere independante des sommet avec une probabilite p pour constituer un ensemble S' ⊂ S. On note X la variable aleatoire ´ du nombre de croisement du graphe induit par S'. On note Y la variable aleatoire correspondant au nombre de sommet et Z la variable aleatoire correspondant au nombre d'aretes.
Montrer que E(Y) = ps, E(Z) = p²a et E(X) ≤ p^4*Cr(G).
J'ai fait la première question , ainsi que E(Y)=ps , cependant j'arrive pas à montrer les deux dernières propriétés. Merci
Bonsoir,
la probabilité pour qu'une arête de A soit dans le sous-graphe induit par S' est égale à la probabilité que ses deux sommets soit dans S'.
On a quelque chose du même genre pour les croisements, mais il est possible que le croisement ne soit pas obligatoire dans le sous-graphe.
Oui j'ai vu ça , mais je sais pas comment la calculer , au début je me suis dis ça va être égal à p² , mais après j'ai vu que p² c'est la probabilité que deux sommets quelconques soient dans le graphe induit , alors que nous on cherche la probabilité pour que deux sommets adjacents soient dans S'
Disons que tu prend une arête du graphe.
La probabilité pour qu'elle soit dans le graphe induit est égale à la probabilité pour que ses deux sommets y soient.
Et tu fais ça pour chaque arête.
On ne peut pas dire que c'est une loi binomiale ( a priori les arêtes sont pas indépendantes ), mais pour chaque arête l'espérance d'être dans le graphe induit est p2.
On utilise ensuite la linéarité de l'espérance.
On fait le même raisonnement : on prend le graphe tracé avec un nombre minimum de croisements.
La probabilité d'avoir deux arêtes qui se croisent sur le schéma de départ est p4 mais il est possible que l'on puisse tracer le sous-graphe en éliminant ce croisement.
La probabilité pour qu'un croisement soit conservé est donc inférieur à p4.
Donc dans notre raisonnement on a supposé que notre graphe initial est dessiné avec le nombre minimal de croisement , cette supposition est elle correcte ? vu qu'on travaille d'abord avec un graphe G de representation quelconque non ?
Pour donner un exemple si G est le graphe complet à 5 sommets on a deux cas possibles :
soit S'=S ( proba p5 ) et il y a 3 croisements dans le graphe induit
soit S'
S et il n'y a aucun croisement dans le graphe induit.
On a donc E(X)=3p5 et il est vrai que 3p5
3p4 avec égalité si p=1.
Pourquoi il y'a 3 croisement si S'=S ? Enfaite ça dépend de la representation du graphe , mais la représentation minimale donne un nombre de croisement égal à 1 . Et je ne vois pas pourquoi quand S' différent de S il n'y a aucun croisement ,
le nombre de croisement, noté Cr (G), est le nombre minimal de croisement nécessaire pour dessiner G dans le plan.
Je me suis trompé sur le nombre minimal de croisements pour le graphe complet à 5 sommets. 
Mais ça n'a guère d'importance pour ce qui nous intéresse ici.
Si S'S alors S' a au plus 4 sommets et un graphe à 4 sommets peut toujours être tracé sans croisement dans le plan.
Donc quand on prend le graphe induit , on garde pas forcément la même distribution des sommets ? Je pensais que si je prenais les 4 sommets des deux arêtes qui se croisent , alors dans le graphe induit je vais poser les 4 sommets au meme endroit où ils étaient donc ça va donner deux arêtes croisés non ?
Non.
On cherche constamment la représentation plane qui comporte le minimum de croisements.
C'est le sens de la citation de ton énoncé que j'ai posté un peu plus haut.
Je reviens vers vous , en voulant écrire la démonstration de la dernière inégalité je me suis bloqué encore 
, enfaite j'ai voulu écrire X comme somme de variable aléatoire Xi avec Xi égal à 1 si le croisement i du graphe G est dans le graphe induit , et i varie de 1 à Cr(G) mais ça ne mène à rien
Tu as bien commencé.
Si on ne modifie pas le dessin du graphe la probabilité pour que le croisement soit dans le graphe induit est p4.
Mais il est possible que l'on puisse modifier le dessin pour supprimer ce croisement ( sans en ajouter de nouveaux ).
La probabilité pour que ce croisement soit obligatoire dans le graphe induit est donc inférieure à p4.
Quelque soit i dans [[1 ; Cr(G)]] l'espérance de Xi est donc inférieure à p4.
Comme l'espérance de X est la somme des espérances des Xi la conclusion est facile.
Mais la probabilité pour que l'évenement Xi=1 se réalise n'est pas inférieur à la somme de p^k pour k allant de 5 à s non ? car il faut prendre au moins 5 sommets pour avoir un croisement , mais je n'arrive toujours pas à voir commencer ça donne directement inférieur à 4 , notamment la phrase "La probabilité pour que ce croisement soit obligatoire dans le graphe induit est donc inférieure à p4." Je n'ai pas compris le "donc"
J'ai l'impression de ne pas comprendre ton problème.
En particulier je ne vois pas ce que vient faire ici la somme de p^k pour k allant de 5 à s.
Je vois la situation de la façon suivante.
On regarde un croisement dans le dessin ( avec un nombre de croisement minimal ) du graphe, il a a priori une probabilité p4 d'être dans le graphe induit.
Si on ne modifie pas le dessin du graphe on a alors E(X)=p4Cr(G).
Mais il est possible qu'une modification du dessin pour le graphe induit permette de supprimer ce croisement sans en rajouter un autre.
On a donc E(X)p4Cr(G).
Annuler
connectez vous
probabilités en post-bac
Le site a rencontré un problème temporaire.
Merci de retenter l'opération plus tard
