---
lang: fr
tags: theorie des graphs, S6, ING1
title: Theorie des graphs 3
date: 01/03/2019
---

# Theorie des graphs 3

++Probleme:++ Connaitre le nombre de possibilité pour un algo qui résoud un rubik's cube:

A chaque fois on a 12 possibilités de rotations car pour chaque face on a 2 rotations possibles (left/right) et il y a 6 faces.

digraph G {
rankdir = LR
init->{1,2,3,"...",12}
1->{_1,_2,_3, "....", _12}
}

Donc quel le nombre minimal de rotation nécessaire pour résoudre n'importe quel rubik's cube ?

++Spoiler++: Il en faut 26. Donc 26 steps dans l'arbre. (12 si on autorise les demi tours)

Si on considère "left" l'operation tourner a gauche et "right" l'op tourner a droite, on se retrouve avec des états communs.
Par exemple: left, left = right right

Du coup pour analyser ça, on va utiliser un parcour largeur.

### Parcours largeur (breadth first search)

<img src="https://docs.google.com/drawings/d/e/2PACX-1vRsewHBHdIUxUlo2mm-Z-R-GfW1U-ud-Qz5V1emzkxGrUo3o_MONZ0-hipkr1-JOCWdTy1p7z91SwmQ/pub?w=960&amp;h=720">

Dans ce cas là, on part de S.

- enqueue(1,2)
- Dequeue 1
- Enqueue 3,4
- dequeue 2
- On a déjà enqueue 1,4
- dequeue 3
- on a déjà enqueue 4, mais pas 5 donc enqueue 5.
- ainsi de suite

# On suppose qu'on est en list d'adjacence (tableau de tableau quoi)
adj = [[1,2][]0,2,3,4][0,1,4]] # Pas complet mais on devine la suite

def BFS(adj, s):
    queue = [s] # teta(1)
    seen = [False] * len(adj) # teta(1)
    seen[s] = True # teta (1)
    while queue: # O(|V|)
        x = queue.pop(0)
        for y in adj[x]: # Sigma deg(x) = 2 |E| = teta(|E|). Donc O(|E|)
            if not seen[y]: # O(|E|)
                seen[y] = True # O(|v|)
                queue.append(y) # O(|v|)
                
    # = O(|V| + |E|)

Si le graph est connexe, on a du téta à la place des O.

### Propriété des graphs

:warning: Au partiel

exc(x) = max (dist(x,y))
rayon(G) = min (exec(x))
diametre(G) = max (exc(x))

++Version avec l'excentricité++:

# On suppose qu'on est en list d'adjacence (tableau de tableau quoi)
adj = [[1,2][]0,2,3,4][0,1,4]] # Pas complet mais on devine la suite

def BFS(adj, s):
    queue = [s] # teta(1)
    seen = [False] * len(adj) # teta(1)
    seen[s] = True # teta (1)
    dist = [0] * len(adj)
    while queue: # O(|V|)
        x = queue.pop(0)
        for y in adj[x]:
            if not seen[y]: # O(|E|)
                seen[y] = True # O(|v|)
                queue.append(y) # O(|v|)
                dist[y] = dist[x]
    return max(dist)                

++BFS par vagues++:

def exc(adj, s):
    seen = [False] * len(adj)
    seen[s] = True
    cur_level = [s]
    next_level = []
    depth = 0
    while cur_level:
            for x in cur_level:
                for y in adj[x]:
                    if not seen[y]:
                        seen[y] = True
                        next_level.append(y)
            cur_level = next_level
            next_level = []
            depth += 1
    return depth - 1