Complexité algorithmiaue

Question 1.1 On a adopté l'algorithme Prüfer pour constuire un arbre en etant donné la séquence de Prüfer aléatoirement par la fonction sample(n,m,replace=TRUE) qui engendre une séquence de longueur m entre 1 a n aléatoirement. Prouver:

Pour n sommets qui ont les valeurs différentes pour chaque sommets correspondant aux (n-2)! d'arbres différents. Pour chaque arbre, on peut y obtenir une séquence de sommets par l'algo Prüfer et cette séquence est unique. Evétament, on ne peut y reconstruire qu'un arbre unique correspandant à la séquence selon laquelle cet arbre est construit.

library(igraph)

routage <- function(n = 100) {
    # sequence de l'ordre engendre par l'algorithme de Pufer
    pa <- n - 2
    pp <- n
    seq <- c(pa)
    seq <- sample(pp, size = pa, replace = TRUE)
    degree <- c(pp)
    g <- graph.empty(pp, directed = FALSE)

    # initialiser la tableau de degree
    for (i in 1:pp) {
        degree[i] <- 1
    }


    # faire additionner 1 au degré a chaque node apparaissant dans la sequence
    # d'ordre
    for (i in 1:pa) {
        degree[seq[i]] <- degree[seq[i]] + 1
    }


    # restituer l'arbre par l'algorithme Prufer

    for (i in 1:pa) {
        for (j in 1:pp) {
            if (degree[j] == 1) {
                m <- seq[i]
                g <- add.edges(g, c(j, m), attr = list(width = 1))
                degree[seq[i]] <- degree[seq[i]] - 1
                degree[j] <- degree[j] - 1
                break
            }
        }
    }

    # trouver les deux nodes qui ont le degree de 1
    u <- 0
    v <- 0
    for (i in 1:pp) {
        if (degree[i] == 1) {
            if (u == 0) {
                u <- i
            } else {
                v <- i
                break
            }
        }
    }
    g <- add.edges(g, c(u, v), attr = list(width = 1))
    degree[u] <- degree[u] - 1
    degree[v] <- degree[v] - 1
    plot(g)


}
routage(30)

question 1.2 Diametre de l'arbre

Etudier en fonction de n la distribution de probabilité associée au diametre(plus long chemin élémentaire d'un arbre de taille n généré uniformement;On prendra n=10,100,1000 et on justifiera la taille des échantillons générés pour estimer cette distribution)

library(igraph)



routage <- function(n = 100) {
    # sequence de l'ordre engendre par l'algorithme de Pufer
    pa <- n - 2
    pp <- n
    seq <- c(pa)
    seq <- sample(pp, size = pa, replace = TRUE)
    degree <- c(pp)
    g <- graph.empty(pp, directed = FALSE)

    # initialiser la tableau de degree
    for (i in 1:pp) {
        degree[i] <- 1
    }


    # faire additionner 1 au degré a chaque node apparaissant dans la sequence
    # d'ordre
    for (i in 1:pa) {
        degree[seq[i]] <- degree[seq[i]] + 1
    }


    # restituer l'arbre par l'algorithme Prufer

    for (i in 1:pa) {
        for (j in 1:pp) {
            if (degree[j] == 1) {
                m <- seq[i]
                g <- add.edges(g, c(j, m), attr = list(width = 1))
                degree[seq[i]] <- degree[seq[i]] - 1
                degree[j] <- degree[j] - 1
                break
            }
        }
    }

    # trouver les deux nodes qui ont le degree de 1
    u <- 0
    v <- 0
    for (i in 1:pp) {
        if (degree[i] == 1) {
            if (u == 0) {
                u <- i
            } else {
                v <- i
                break
            }
        }
    }
    g <- add.edges(g, c(u, v), attr = list(width = 1))
    degree[u] <- degree[u] - 1
    degree[v] <- degree[v] - 1
    l <- diameter(g)
    print("La dimetre est:")
    print(l)
    plot(g, xlab = paste("diametre = ", l), main = "L'arbre engendré par l'algo Prüfer")
}
par(mfrow = c(3, 1), mar = c(4, 4, 2, 2))
routage(10)

## [1] "La dimetre est:"
## [1] 8

routage(100)

## [1] "La dimetre est:"
## [1] 32

routage(1000)

## [1] "La dimetre est:"
## [1] 106

Quetion 1.3:Diametre moyen d'un arbre uniformement généré

Tracer en fontion de n le diametre moyen d'un arbre uniformement généré ainsi que l'intervalle de confiance associé.Qu'en concluez-vous?Peut-on comparer ce résultal ? celui de la hauteur moyenne d'un arbre binaire uniformement?

library(igraph)


routage <- function(n = 100) {
    # sequence de l'ordre engendre par l'algorithme de Pufer
    pa <- n - 2
    pp <- n
    seq <- c(pa)
    seq <- sample(pp, size = pa, replace = TRUE)
    degree <- c(pp)
    g <- graph.empty(pp, directed = FALSE)

    # initialiser la tableau de degree
    for (i in 1:pp) {
        degree[i] <- 1
    }


    # faire additionner 1 au degré a chaque node apparaissant dans la sequence
    # d'ordre
    for (i in 1:pa) {
        degree[seq[i]] <- degree[seq[i]] + 1
    }


    # restituer l'arbre par l'algorithme Prufer

    for (i in 1:pa) {
        for (j in 1:pp) {
            if (degree[j] == 1) {
                m <- seq[i]
                g <- add.edges(g, c(j, m), attr = list(width = 1))
                degree[seq[i]] <- degree[seq[i]] - 1
                degree[j] <- degree[j] - 1
                break
            }
        }
    }

    # trouver les deux nodes qui ont le degree de 1
    u <- 0
    v <- 0
    for (i in 1:pp) {
        if (degree[i] == 1) {
            if (u == 0) {
                u <- i
            } else {
                v <- i
                break
            }
        }
    }
    g <- add.edges(g, c(u, v), attr = list(width = 1))
    degree[u] <- degree[u] - 1
    degree[v] <- degree[v] - 1
    l <- diameter(g)
}
n = 20
ensemble <- c(500)
x <- 0
for (i in 1:500) {
    x <- x + routage(n)
    ensemble[i] <- routage(n)
}
d <- x/500
ss <- n - d
print("l'intervalle de confiance est:")

## [1] "l'intervalle de confiance est:"

print(paste("[", ss, ",", d, "]"))

## [1] "[ 9.708 , 10.292 ]"

hist(ensemble, breaks = 20, col = "red", xlim = c(0, n), ylim = c(0, 150), xlab = "diamétre", 
    ylab = "Fréquence", main = "Diamèter séquence", sub = d - n/2)

On a testé 500 fois de générations d'arbre de taille 20 en pratiquant l'algo Prufer et a obtenu le résultal 10.49 approximitif à l'espérence de cette séauence 10 qui nous montrerait que la distribution suit probablement une distribution uniformement identique. On a l'intervalle de confiance [9.51,10.49]. On sai que la hauteur moyenne d'un arbre est logN, ceci est log20=5.Si on prend un point approximitif au millieu de l'arbre de Prüfer,et on a obtenu un arbre de hauteur 5.Et ce sont similaire.