[THEG] Theorie des graphes (1)

Problematiques sur les graphes

Complexites

P : Le probleme peut etre resolu par une machine de Turing deterministe en un temps polynomial

NP : Le probleme peut etre resolu par une machine de Turing non-deterministe en un temps polynomial

Algo Complexite
Coloration de graphe NP-Complet
Plus court chemin P
Vendeur de commerce NP-Hard
Tri topologique Lineaire
Probleme de flots max P
Connexite P
Arbres couvrants P
Chemin / cycle eulerien Lineaire
Cycle Hamiltonien NP-Complet
Graphe planaire Lineaire
Isomorphisme de graphe NP
Epaisseur de graphe NP-Hard
Couplage maximum Lineaire
Clique maximale NP-Complet
Couverture des sommets par les aretes Lineaire
Couverture des aretes par les sommets NP-Complet
Denombrer les arbres couvrants P

Definitions

Graphe oriente

Graphe non-oriente

Graphe pondere
Il y a des poids sur les aretes ou les arcs

Connexe
Il existe un chemin entre toute paire de sommet

Arbre
Graphe acyclique connexe

DAG
Directed acyclic graph

DAG arbre

Degre d’un sommet
Nombre d’aretes incidentes
nombre d’aretes

Sur graphe oriente : On a degre entrant et sortant

for x in V:
    for y in succ(x):
        // execute 2x nombre d'aretes

Graphe simple
Graphe sans aretes en double et sans boucles

Graphe multiple
On autorise aretes doubles et boucles

Plan

6 seances

  1. Culture et vocabulaire
  2. Cycles euleriens et DFS
  3. BFS, Rubik’s cube, Plus court chemin
  4. BFS, Rubik’s cube, Plus court chemin
  5. Couplages, connexite
  6. Couplages, connexite