---
title: Théorie des graphes
date: 01/03/19
author: Robin 'Pachichi' Boucher
tags: cours, theorie des graphes, graphes
---
> 01/03/19
# Théorie des graphes
Nb de coups minimum pour résoudre n'importe quelle configuration minimum d'un Rubik's Cube: [20](http://cube20.org/)

Use a Breadth First Search (BFS) to compute the number above.

graph graphname {
    rankdir=LR;
    s -- { a b }
    a -- { b c d }
    b -- { c g }
    c -- { d g e }
    d -- e
    e -- f
    f -- g
}

On part du sommet **s** et on applique l'algo suivant:

adj=[{a,b}, {s,b,c,d}, {s,a,c,g}, ...] #liste d'adjacence
def BFS(adj, s):
    queue = [s]
    seen = {s}
    while queue: # 
        x = queue.pop(0)
        for y in adj[x]:
            if (y not in seen):
                seen.add(y)
                queue.append(y)
# si graphe connexe: |V| = O(E)

==excentricité d'un sommet s:== plus grande distance qu'on peut parcourir à partir de s

graph excentricite {
rankdir=LR
    1 -- { 2, 3} #exc(1) = 2
    2 -- {1, 4} # exc(2) = 3
    3 -- {4, 5} # exc(3) = 2
    4 # exc(4) = 2
    5 # exc(5) = 3
}

==rayon d'un graphe:== plus petite excentricité d'un graphe
Le rayon du graphe ci-dessus est 2.
==diamètre d'un graphe:== plus grande excentricité d'un graphe.
Le diamètre du graphe ci-dessus est 3.

#fonction pour calculer l'excentricité
def exc(adj, s):
    cur_level = [s]
    nxt_level = []
    seen = [False] * len(adj)
    seen[s] = True
    depth = 0
    while cur_level:
        for x in cur_level:
            for y in adj[x]:
                if (not seen[y]):
                    nxt_level.append(y)
                    seen[y] = True
        cur_level = nxt_level
        nxt_level = []
        depth += 1
    return depth - 1