DM2 : Mini projet
Auteurs : El Hadji Malick FALL & Adam TIAMIOU
Question 1.1 : algorithme de génération
library(igraph)
set.seed(11)
prufer <- function(valeur) {
n = valeur
a = n - 2
T <- graph.empty(n, directed = FALSE) #initialisation: T est un stable (avec n sommets isolés allant de 1 à n)
sp <- sample(1:n, a, replace = TRUE) #creation d'une suite de prufer de façon uniforme avec n-2 valeurs
degre = c(n) #creation d'un tableau de degré de taille n
for (i in 1:n) {
degre[i] = 1
} #initialisation du tableau des degrés avec toutes les valeurs à 1
for (i in 1:a) {
degre[sp[i]] = degre[sp[i]] + 1
} # le degré de chaque sommet est le nombre de fois où il apparait dans la séquence sp
# pour chaque noeud i dans a, on cherche le 1er noeud j de degré 1 et
# ajouter l'arête (i,j) au graphe
for (i in 1:a) {
for (j in 1:n) {
if (degre[j] == 1) {
T <- add.edges(T, c(sp[i], j))
degre[sp[i]] = degre[sp[i]] - 1
degre[j] = degre[j] - 1
break
}
}
}
# Ala fin de cette boucle, il restera deux noeuds de degré 1 qu'il faudra
# relier par une arête qui sera ajouté à l'arbre
u = 0
v = 0
for (i in 1:n) {
if (degre[i] == 1) {
if (u == 0) {
u = i
} else v = i
}
}
T <- add.edges(T, c(u, v))
degre[u] <- degre[u] - 1
degre[v] <- degre[v] - 1
plot(T)
} #fin fonction
prufer(20)
Tout d'abord, nous avons créé une liste sp de n-2 sommets à valeurs uniforme dans [1..n]. Pour former les arêtes, on choisit le premier sommet de sp et on l'associe au plus petit sommet j de degré 1 et on décrémente de 1 les degrés des deux sommets. Le sommet de sp ayant été choisi uniformèment et le degré de j atteignant la valeurs 0 et donc ne devenant plus selectionnable, on en déduit qu'on a choisit uniformèment un sous-ensemble de n-1 arètes parmi les n(n-1)/2 possibles. Donc notre algorithme qui est celui de prufer génère bien un arbre selon la loi uniforme.
Question 1.2 : Diametre de l'arbre
Sachant qu'on a nn-2 arbres différents, nous avons choisi de travailler sur une taille d'échantillons niter=150. Cette taille est suffisament assez grande pour observer la répartion des diamètres, et permet de limiter dans une moindre mesure la compléxité des temps de calcul sur R.
set.seed(11)
diam <- function(param) {
n = param
a = n - 2
T <- graph.empty(n, directed = FALSE) #initialisation: T est un stable (avec n sommets isolés allant de 1 à n)
sp <- sample(1:n, a, replace = TRUE) #creation d'une suite de prufer de façon uniforme avec n-2 valeurs
degre = c(n) #creation d'un tableau de degré de taille n
for (i in 1:n) {
degre[i] = 1
} #initialisation du tableau des degrés avec toutes les valeurs à 1
for (i in 1:a) {
degre[sp[i]] = degre[sp[i]] + 1
} # le degré de chaque sommet est le nombre de fois où il apparait dans la séquence sp
# pour chaque noeud i dans a, on cherche le 1er noeud j de degré 1 et
# ajouter l'arête (i,j) au graphe
for (i in 1:a) {
for (j in 1:n) {
if (degre[j] == 1) {
T <- add.edges(T, c(sp[i], j))
degre[sp[i]] = degre[sp[i]] - 1
degre[j] = degre[j] - 1
break
}
}
}
# Ala fin de cette boucle, il restera deux noeuds de degré 1 qu'il faudra
# relier par une arête qui sera ajouté à l'arbre
u = 0
v = 0
for (i in 1:n) {
if (degre[i] == 1) {
if (u == 0) {
u = i
} else v = i
}
}
T <- add.edges(T, c(u, v))
degre[u] <- degre[u] - 1
degre[v] <- degre[v] - 1
x = diameter(T) #retourne le diamètre
} # fin fonction
distribdiam <- function(n, niter) {
ValeursDiametre <- c()
for (i in 1:niter) {
ValeursDiametre[i] <- diam(n)
}
ValeursDiametre
}
set.seed(11)
res1 = distribdiam(10, 150)
hist(res1, breaks = seq(0, 10, 1), col = "blue")
set.seed(11)
res2 = distribdiam(100, 150)
hist(res2, breaks = seq(0, 100, 10), col = "red")
set.seed(11)
res3 = distribdiam(1000, 150)
hist(res3, breaks = seq(0, 1000, 50), col = "green")
Les résultats obtenus sont restrictifs. Pour avoir une meilleure perception, il faudrait avoir un nombre d'échantillons très grand, supérieur au nombre d'arbres possibles. Nous constatons néanmoins avec les résultats dont nous disposons que le diamètre est compris dans une petite portion d'intervalle (entre 3 et9 pour n=10,entre 10 et 50 pour n=100 et entre 50 et 150 pour n=1000)
Question 1.3 : Diametre moyen
set.seed(11)
niter <- 100
proba <- 0.975
valn <- c(10, 25, 50, 75, 100)
moyenne <- c()
interval <- c()
for (i in 1:5) {
res <- distribdiam(valn[i], niter)
variance <- var(res)
ddl <- niter - 1 #degré de liberté
t_student <- qt(proba, ddl)
moyenne[i] <- mean(res)
interval[i] <- t_student * sqrt(variance/niter)
}
plot(valn, moyenne, type = "l", col = "blue", ylim = c(5, 35))
lines(valn, (moyenne - interval), col = "red")
lines(valn, (moyenne + interval), col = "red")
La courbe bleu correspond au diamètre moyen. Elle est délimitée par les courbes rouges qui correspondent à l'intervalle de confiance.
On constate que lorsque n augmente, la moyenne ainsi que l'intervalle de confiance augmentent. En effet l'écart entre les deux courbes rouges s'élargit. Cela s'explique par le fait que le nombre d'échantillons reste constant mais le nombre d'arbres réalisables lui augmente.
Pour n=10,on a un diamètre moyen de 6. Pour n=100, nous avons obtenu 28. Dans le cas d'un arbre binaire, le diamètre moyen est en O((√n)). Pour les mêmes valeurs de n, nous obtenons respectivement 3 et 10. Par comparaison, il convient qu'il est moins intéressant de générer uniforfement un arbre binaire car le diamètre moyen est moins important, donc le routage est plus facile à casser.