Question 1.1 : Algorithme de génération
Nous allons utiliser l'algorithme de Prüfer pour générer nos arbres uniformément. En effet, une suite de nombre P nous donnera un seul et unique arbre à chaque appel de la fonction, ce qui prouve le choix de cet algorithme. Donc si nous utilisons la même suite à chaque fois, nous aurons des arbres différents mais avec le même nombre de noeuds.
library(igraph)
set.seed(3)
generer_arbre <- function(n) {
# On commence par générer la suite de nombre jusqu'à n-2
suite_prufer <- c(n - 2)
suite_prufer <- sample(1:n, n - 2, replace = TRUE)
# On initialise notre graphe (arbre) non orienté
graph <- graph.empty(n, directed = FALSE)
# On initialise le tableau de degré qui nous servira pour la reconstruction
# de l'arbre
degrees <- c(n)
for (i in 1:n) {
degrees[i] <- 1
}
# Ensuite on incrément de 1 le degré de chaque noeud qui apparaît dans la
# suite de Prufer (suite_prufer)
for (i in 1:(n - 2)) {
degrees[suite_prufer[i]] <- degrees[suite_prufer[i]] + 1
}
# On restitue l'arbre de Prufer
for (i in 1:(n - 2)) {
for (j in 1:n) {
if (degrees[j] == 1) {
# On ajoute au graphe les sommets de degrés 1
graph <- add.edges(graph, c(suite_prufer[i], j))
degrees[suite_prufer[i]] <- degrees[suite_prufer[i]] - 1
degrees[j] <- degrees[j] - 1
break
}
}
}
# Il ne manque plus qu'à rajouter l'arête entre les deux sommets restants
x <- 0
y <- 0
for (i in 1:n) {
if (degrees[i] == 1) {
if (x == 0) {
x <- i
} else {
y <- i
}
}
}
# On l'ajoute au dessin
graph <- add.edges(graph, c(x, y))
degrees[x] <- degrees[x] - 1
degrees[y] <- degrees[y] - 1
plot(graph)
}
Il faut maintenant vérifier de façon plus formel que la génération se fait bien de façon uniforme.
Nous allons donc prouver que notre algorithme génère bien uniformément un arbre à n sommets.
Il faut d'abord prouver que pour chaque graphe il existe une seule et unique suite de Prufer le décrivant. Or pour générer la suite, nous utilisons une fonction (sample) qui nous donne une suite de nombre de manière uniforme pour chaque nombre.
Il faut ensuite prouver que pour la suite de Prufer que nous avons de longueur n-2, il existe un seul graphe numéroté (ses sommets) de 1 à n et c'est un arbre. D'après la fonction sample on sait que nos nombres sont générés uniformément dans la suite de Prufer. Sachant que la longueur de la suite de Prufer est de n-2 alors l'algorithme va générer du coup uniformément un arbre de nn-2 éléments.
Nous pensions appuyer cette preuve par une étude sur l'uniformité de la génération en générant 1000 arbres par exemple. Le problème est que nous n'avons pas trouvé de manière de vérifier que les graphes étaient équivalent …
Question 1.2 : Diamètre de l'arbre
Nous allons reprendre le code précédent en renvoyant le diamètre :
diametre_generer_arbre <- function(n) {
# On commence par générer la suite de nombre jusqu'à n-2
suite_prufer <- c(n - 2)
suite_prufer <- sample(1:n, n - 2, replace = TRUE)
# On initialise notre graphe (arbre) non orienté
graph <- graph.empty(n, directed = FALSE)
# On initialise le tableau de degré qui nous servira pour la reconstruction
# de l'arbre
degrees <- c(n)
for (i in 1:n) {
degrees[i] <- 1
}
# Ensuite on incrément de 1 le degré de chaque noeud qui apparaît dans la
# suite de Prufer (suite_prufer)
for (i in 1:(n - 2)) {
degrees[suite_prufer[i]] <- degrees[suite_prufer[i]] + 1
}
# On restitue l'arbre de Prufer
for (i in 1:(n - 2)) {
for (j in 1:n) {
if (degrees[j] == 1) {
# On ajoute au graphe les sommets de degrés 1
graph <- add.edges(graph, c(suite_prufer[i], j), attr = list(width = 1))
degrees[suite_prufer[i]] <- degrees[suite_prufer[i]] - 1
degrees[j] <- degrees[j] - 1
break
}
}
}
# Il ne manque plus qu'à rajouter l'arête entre les deux sommets restants
x <- 0
y <- 0
for (i in 1:n) {
if (degrees[i] == 1) {
if (x == 0) {
x <- i
} else {
y <- i
}
}
}
# On l'ajoute au dessin
graph <- add.edges(graph, c(x, y), attr = list(width = 1))
degrees[x] <- degrees[x] - 1
degrees[y] <- degrees[y] - 1
diametre <- diameter(graph)
}
Regardons donc le diamètre d'arbre de différentes taille, nous prendrons 1000 échantillons pour avoir une moyenne correcte.
nb_echantillons <- 1000
data10 <- c(nb_echantillons)
for (i in 1:nb_echantillons) {
data10[i] <- diametre_generer_arbre(10)
}
hist(data, main = "Histogramme des diamètres d'un arbre généré uniformément pour n = 10",
xlab = "Diametre de l'arbre", ylab = "Fréquence")
## Error: 'x' must be numeric
Essayons avec 10 000 échantillons pour voir si il y a une différence.
nb_echantillons <- 10000
data10 <- c(nb_echantillons)
for (i in 1:nb_echantillons) {
data10[i] <- diametre_generer_arbre(10)
}
hist(data10, main = "Histogramme des diamètres d'un arbre généré uniformément pour n = 10",
xlab = "Diametre de l'arbre", ylab = "Fréquence")
On peut voir que 1000 échantillons sont amplement suffisants.
Faisons la même étude pour une taille d'arbre de 100 puis 1000.
nb_echantillons <- 1000
data100 <- c(nb_echantillons)
for (i in 1:nb_echantillons) {
data100[i] <- diametre_generer_arbre(100)
}
hist(data100, main = "Histogramme des diamètres d'un arbre généré uniformément pour n = 100",
xlab = "Diametre de l'arbre", ylab = "Fréquence")
Le nombre d'échantillon pour n = 100 est peut être légèrement insuffisant car la courbe n'est pas “parfaite”. Faisons donc la même chose avec 5000 échantillons, ça sera bien plus clair.
nb_echantillons <- 5000
data100 <- c(nb_echantillons)
for (i in 1:nb_echantillons) {
data100[i] <- diametre_generer_arbre(100)
}
hist(data100, main = "Histogramme des diamètres d'un arbre généré uniformément pour n = 100",
xlab = "Diametre de l'arbre", ylab = "Fréquence")
On peut supposer que la même chose va se produire pour n = 100. Passons donc directement à 10000 échantillons.
nb_echantillons <- 10000
data1000 <- c(nb_echantillons)
for (i in 1:nb_echantillons) {
data1000[i] <- diametre_generer_arbre(1000)
}
hist(data1000, main = "Histogramme des diamètres d'un arbre généré uniformément pour n = 100",
xlab = "Diametre de l'arbre", ylab = "Fréquence")
On se rend compte que plus la taille de l'arbre est importante, plus l'écart entre le diamètre mini et le diamètre maxi est important.
Pour chaque n, nous allons tester avec la technique du khi-carré pour voir si le diamètre des arbres suivent une loi uniforme.
chisq.test(data10)
##
## Chi-squared test for given probabilities
##
## data: data10
## X-squared = 1744, df = 9999, p-value = 1
chisq.test(data100)
##
## Chi-squared test for given probabilities
##
## data: data100
## X-squared = 3743, df = 4999, p-value = 1
chisq.test(data1000)
##
## Chi-squared test for given probabilities
##
## data: data1000
## X-squared = 25158, df = 9999, p-value < 2.2e-16
On voit bien que la p-value est égal à 1 ou s'approche grandement de 1 ce qui nous prouve que les diamètres générés ont tendance à suivre une loi uniforme.
Question 1.3 : Diamètre moyen d'un arbre uniformément généré
nb_echantillons <- 100
moyenne <- c(nb_echantillons)
for (j in 10:100) {
datan <- c(nb_echantillons)
for (i in 1:nb_echantillons) {
datan[i] <- diametre_generer_arbre(j)
}
moyenne[j - 9] <- mean(datan)
}
plot(moyenne, xlab = "Nombre d'éléments par arbre")
On peut voir que le diamètre moyen en fonction du nombre d'éléments n par arbre à tendance à être linéaire, peut être logarithmique.
int.ech = function(vector, proba = 5) {
s = var(vector)
n = length(vector)
ddl = n - 1
proba = (100 - proba/2)/100
t_student = qt(proba, ddl)
intervalle = t_student * sqrt(s/n)
moyenne = mean(vector)
# minimum = moyenne-intervalle maximum = moyenne+intervalle mini_max <-
# c(minimum,maximum,intervalle) return(mini_max)
return(intervalle)
}
Cette fonction va nous permettre de calculer l'intervalle de confiance à 95 %.
Prenons un échantillon de 1000 arbres de taille 25 et calculons l'intervalle de confiance.
nb_echantillons <- 1000
data25 <- c(nb_echantillons)
for (i in 1:nb_echantillons) {
data25[i] <- diametre_generer_arbre(25)
}
hist(data25, main = "Histogramme des diamètres d'un arbre généré uniformément pour n = 25",
xlab = "Diametre de l'arbre", ylab = "Fréquence")
interv <- int.ech(data25)
interv
## [1] 0.1235
On a donc un intervalle de confiance de +- 0.12457 pour cet échantillonnage.
Peut-on faire un rapprochement avec la hauteur d'un arbre ? La hauteur d'un arbre de taille n est log(n).Ici ce serait donc de log(25) = 1.4 (environ). Nous ne voyons pas quel rapprochement l'on peut faire entre la hauteur moyenne d'un arbre et son diamètre.