Créer un graphe et calculer la clique maximale

**ahmad_bassam** · 30/12/2006, 00h53

Je suis demandé de faire une application c ou c++ qui crée un graphe et calcule la clique maximale. C URGENT!!!!!!

**Matthieu Brucher** · 30/12/2006, 01h32

Regarde dans Boost.Graph.

**Luc Hermitte** · 30/12/2006, 01h38

1- On ne fait pas les exos des autres, ni leur boulot
Corrolaire, il ne sert à rien de dire "urgent". Répondent ceux qui peuvent, et qui veulent, et quand ils le peuvent. Des fois les autres ici.
2- C'est quoi une "clique" d'un graphe ?

**dj.motte** · 30/12/2006, 02h25

Salut,

Je suis demandé de faire une application c ou c++ qui crée un graphe et calcule la clique maximale. C URGENT!!!!!!

Pour la clique minimale, non pas maximale, il y a l' algo de Ford Fulkerson.

**PRomu@ld** · 30/12/2006, 09h38

2- C'est quoi une "clique" d'un graphe ?

Une clique est un sous-graphe complet.

Le calcul d'une clique d'ordre maximal est un problème NP-Complet, alors pour l'urgent tu vas attendre ...

**PRomu@ld** · 30/12/2006, 09h41

Pour la clique minimale, non pas maximale, il y a l' algo de Ford Fulkerson.

Euh, je ne vois pas l'intérêt de caculer une clique minimale : c'est un graphe à un sommet et pas d'arrête ...

De plus Ford-Fulkerson, c'est pas pour ça !

Créer un graphe et calculer la clique maximale

C++

Discussions similaires

Partager

Partager