Inscription / Connexion Nouveau Sujet
Niveau école ingénieur
Partager :

croisement

Posté par
solidad01
29-05-21 à 13:44

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

Posté par
verdurin
re : croisement 29-05-21 à 17:45

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.

Posté par
solidad01
re : croisement 29-05-21 à 18:19

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'

Posté par
verdurin
re : croisement 29-05-21 à 18:28

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.

Posté par
solidad01
re : croisement 29-05-21 à 18:38

okay donc la loi de Z est une binomiale de paramètre p² ?

Posté par
verdurin
re : croisement 29-05-21 à 18:58

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.

Posté par
solidad01
re : croisement 29-05-21 à 19:00

Merci beaucoup ! Pour la dernière inégalité avez vous une piste à suggérer ?

Posté par
verdurin
re : croisement 29-05-21 à 19:15

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.

Posté par
solidad01
re : croisement 29-05-21 à 19:25

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 ?

Posté par
verdurin
re : croisement 29-05-21 à 19:28

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 3p53p4 avec égalité si p=1.

Posté par
solidad01
re : croisement 29-05-21 à 19:37

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 ,

Posté par
verdurin
re : croisement 29-05-21 à 19:38

Citation :
le nombre de croisement, noté Cr (G), est le nombre minimal de croisement nécessaire pour dessiner G dans le plan.

Posté par
solidad01
re : croisement 29-05-21 à 19:44

Oui donc

Posté par
verdurin
re : croisement 29-05-21 à 19:47

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.

Posté par
solidad01
re : croisement 29-05-21 à 20:37

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 ?

Posté par
verdurin
re : croisement 29-05-21 à 20:48

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.

Posté par
solidad01
re : croisement 29-05-21 à 20:49

Ahh d'accord , je vois merci beaucoup!

Posté par
verdurin
re : croisement 29-05-21 à 21:18

Service

Posté par
solidad01
re : croisement 30-05-21 à 16:10

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

Posté par
verdurin
re : croisement 30-05-21 à 18:42

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.

Posté par
solidad01
re : croisement 30-05-21 à 18:59

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"

Posté par
verdurin
re : croisement 30-05-21 à 19:22

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).

Posté par
solidad01
re : croisement 30-05-21 à 21:49

Ahh d'accord , c'est plus clair pour moi je vous remercie !



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1689 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !