DM_MESNIER_HAMDANI
Mesnier Vincent Hamdani Youcef
PS : Sujet 4:Transmission de virus QUESTION 4.1 : Cas du graphe complet utilisation d’un tableau représentant les sommets: la valeur à l’indice i vaut 1 si le sommet i est contaminé 0 sinon On commence par initialiser la graine pour notre DM :
set.seed(12345)Dans ce premier cas, nous traitons les graphes complets (Kn). Cela equivaut à dire v que tous les sommets sont reliés entre eux (ils sont donc tous voisins). Donc nous pouvons les représenter sous forme de tableau à 1 dimension avec pour chaque case 1 sommet. Si la valeur est 1 cela veut dire que ce sommet est contaminé et dans le cas contraire la valeur vaut 0
Cette fonction vas initialiser le graphe (soit le tableau) puis nous générons 2 nombre aléatoirement afin de choisir quels couple de sommet sera infecté par le virus (en respectant les régles de l’énoncé). Il faut bien penser à faire le premier cas au départ.
question1 <- function(N= 5) {
graphe=graphe =rep(0,N)
nb = c(2)
tn=0
graphe[sample(1:N,1, replace = FALSE)]=1
while (mean(graphe)<1){
nb<-sample(1:N,2, replace = FALSE)
if (graphe[nb[1]]==1){
graphe[nb[2]]=1
tn=tn+1
}
else if (graphe[nb[2]]==1){
graphe[nb[1]]=1
tn=tn+1
}
else{
tn=tn+1
}
}
return(tn)
}
question1(500)## [1] 3587Nous allons maintenant tester notre fonction sur plusieurs cas pour observer comment évolue la valeur de Tn en fonction lorsque nous augmentons la population.
Premier cas avec une populations de 150 :
res=c()
for (i in 1:1000){
res[i]=question1(150)
}
hist(res)
plot(res)
mean(res)## [1] 839.3deuxiéme cas : avec des valeurs de population qui augmente:
res=c()
c=10
for (i in 1:50){
res[i]=question1(c)
c=c+10
}
plot(res)
mean(res)## [1] 1587On peut remarquer, grace notamment avec les 2 graphiques, qu’il y a un ecart type assez élévé (cela va de 600 a plus de 1400 achats de vignettes) et que dans un graphe Kn les virus se propage avec un temps proportionel à la taille de la population.
Sur 5 personnes, la temps de contamination peut aller de 4 à plus de 20
res=c()
for (i in 1:100){
res[i]=question1()
}
hist(res)
plot(res)
mean(res)## [1] 8.29QUESTION 4.2 : Graphe ligne 1D et grille 2D A) :ligne 1D Dans ce cas la, Nous avons crée une fonction ressemblant a la premiére mais puisque nous avons une chaine alors seulement les sommets voisin peuvent se contaminer.
question2A <- function(N=5){
graphe =rep(0,N)
nb = c(2)
tn=0
graphe[sample(1:N,1, replace = FALSE)]=1
while (mean(graphe)<1){
nb<-sample(1:N,2, replace = FALSE)
if (abs(nb[2]-nb[1])==1){
if (graphe[nb[1]]==1){
graphe[nb[2]]=1
tn=tn+1
}
else if (graphe[nb[2]]==1){
graphe[nb[1]]=1
tn=tn+1
}
else{
tn=tn+1
}
}
}
return(tn)
}
question2A(200)## [1] 43196res=c()
c=10
for (i in 1:25){
res[i]=question2A(c)
c=c+10
}
plot(res)
mean(res)## [1] 16998On peut ici voir que le temps pour infecter le graphe est bien supérieur qu’au premier cas. En effet on peut voir que la courbe courbe du temps en fonction de la taille du graphe augmente de facon exponentiel.
B) une grille 2D
Pour ce cas, on utilise une matrice carré de racineN*racineN, il y a différent cas à voir car certain sommet ont que 2 voisin ou 3 voisin (ceux qui sont sur les bord de la matrice carré)
question2B <- function(racineN = 5) {
graphe=matrix(numeric(),racineN,racineN)
tn=0
for(i in (1:racineN)) {
for(j in (1:racineN)) {
graphe[[i,j]] = 0 }
}
graphe[[sample(1:racineN,1),sample(1:racineN,1)]]=1
while (mean(graphe)<1){
cx=c()
cy=c()
x1<-sample(1:racineN,1)
y1<-sample(1:racineN,1)
if ((x1+1) <= racineN){
cx=c(cx,x1+1)
}
if ((x1-1)>=1){
cx=c(cx,x1-1)
}
if ((y1+1) <= racineN){
cy=c(cy,y1+1)
}
if ((y1-1)>=1){
cy=c(cy,y1-1)
}
x2=sample(cx,1)
y2=sample(cy,1)
if (graphe[[x1,y1]]==1){
graphe[[x2,y2]]= 1
tn=tn+1
}
else if (graphe[[x2,y2]]==1){
graphe[[x1,y1]]=1
tn=tn+1
}
else{
tn=tn+1
}
}
return(tn)
}
question2B(50)## [1] 40989res=c()
for (i in 1:100){
res[i]=question2B(10)
}
hist(res)
plot(res)
mean(res)## [1] 721.7Avant d“effectuer une simulation, on peut remarquer que le temps d’infection du graphe va dépendre premier sommet infecté car si on infecte sommet n’ayant un nombre de voisin inférieur à 4 alors le temps de convergence sera supérieur au cas ou nous commencons par un sommet qui a 4 voisins (cas ou la convergence se fait la plus rapidement.
Verifions :
question2Bbis <- function(racineN = 5) {
graphe=matrix(numeric(),racineN,racineN)
tn=0
for(i in (1:racineN)) {
for(j in (1:racineN)) {
graphe[[i,j]] = 0 }
}
graphe[[1,1]]=1 # car ce sommet n'a que deux aretes
while (mean(graphe)<1){
cx=c()
cy=c()
x1<-sample(1:racineN,1)
y1<-sample(1:racineN,1)
if ((x1+1) <= racineN){
cx=c(cx,x1+1)
}
if ((x1-1)>=1){
cx=c(cx,x1-1)
}
if ((y1+1) <= racineN){
cy=c(cy,y1+1)
}
if ((y1-1)>=1){
cy=c(cy,y1-1)
}
x2=sample(cx,1)
y2=sample(cy,1)
if (graphe[[x1,y1]]==1){
graphe[[x2,y2]]= 1
tn=tn+1
}
else if (graphe[[x2,y2]]==1){
graphe[[x1,y1]]=1
tn=tn+1
}
else{
tn=tn+1
}
}
return(tn)
}
res=c()
c=2
for (i in 1:40){
res[i]=question2Bbis(c)
c=c+2
}
plot(res)
mean(res)## [1] 40956Cas avec un sommet de debut avec 3 arêtes
question2Bbisbis <- function(racineN = 5) {
graphe=matrix(numeric(),racineN,racineN)
tn=0
for(i in (1:racineN)) {
for(j in (1:racineN)) {
graphe[[i,j]] = 0 }
}
graphe[[2,1]]=1 # car ce sommet n'a que 3 aretes
while (mean(graphe)<1){
cx=c()
cy=c()
x1<-sample(1:racineN,1)
y1<-sample(1:racineN,1)
if ((x1+1) <= racineN){
cx=c(cx,x1+1)
}
if ((x1-1)>=1){
cx=c(cx,x1-1)
}
if ((y1+1) <= racineN){
cy=c(cy,y1+1)
}
if ((y1-1)>=1){
cy=c(cy,y1-1)
}
x2=sample(cx,1)
y2=sample(cy,1)
if (graphe[[x1,y1]]==1){
graphe[[x2,y2]]= 1
tn=tn+1
}
else if (graphe[[x2,y2]]==1){
graphe[[x1,y1]]=1
tn=tn+1
}
else{
tn=tn+1
}
}
return(tn)
}
res=c()
c=2
for (i in 1:40){
res[i]=question2Bbisbis(c)
c=c+2
}
plot(res)
mean(res)## [1] 41539Les résultats obtenu verifie nos hypothéses, en effet nous pouvons voir en comparant les graphes précédent que le temps Tn est supérieur lorsque le sommet est choisi au milieu du graphe plutot que sur un bord ou dans un angle
Question 4.3 : Graphe de Erdös-Renyi