Enoncé:
On considère une ville formé d'un certain nombre de carrefours relié entre eux par des
rues (aucune supposition n'est faite sur la possibilité ou non de représenter sur un plan
de manière à ce que les rues ne se croisent pas; il est possible que certaines "rues"
empruntent des souterrains ou des ponts suspendus). On suppose qu'il est normalement
possible de se déplacer de n'importe quel carrefour a n'importe quel autre en empruntant
une succession de rues.
On considère q'une rue est critique si, lorsqu'elle est soudainement barrée (alors
qu'aucune autre rue n'est barrée), il devint impossible de se déplacer de certains
carrefours à certains autres.
Un édile fou décide d'instaurer un sens unique sur chacune des rues.A un de ses opposants
qui s'inquiète des possibilités futures de circulation, il rétorque:"Notre ville ne
comporte actuellement aucune rue critique; par conséquent il est possible d'attribuer à
chacune des rues un sens unique de circulation, de telle manière qu'il reste possible de
passer de n'importe quel endroit à n'importe quel autre.Votre objection est donc rejeté".
Travail demandé:
On demande de modéliser la situation décrite ci-dessus en termes de graphes et de prouver
que l'affirmation du maire est effectivement correcte: pour toute ville imaginable, les
assertions "il n'existe aucune rue critique" et " il est possible de mettre toutes les
rues au sens unique sans rendre la circulation impossible" sont équivalentes. Décrire un algorithme, qui étant donné une ville, exhibe soit une rue critique, soit une solution au problème des sens uniques ; et étudier sa complexité.
Réaliser un programme C offrant au moins les fonctionnalités suivantes :
• Lire, dans un fichier ou clavier, une description d’une « ville ».
• Ecrire dans un fichier une description d’une « ville ».
• Etant donné une « ville », décide si le problème des sens uniques admet une solution et, dans le cas positif, exhibe une telle solution.
• Etant donné une « ville », décide si elle possède une rue critique et, c’est le cas, en exhibe une.
Voila ce aue j'ai comme solution algorithmique:
1. REPRESENTATION DES DONNEES
* Un sommet est une structure à plusieurs champs:
struct sommet
{
indice : entier;
date : entier;
ind_critique : entier;
}
****************************** ****************************** ****************************** ********************
* Le graphe sera également une structure :
struct graphe
{
MatriceLiaison : Matrice de taille nxn; (int[n][n] en C)
ListeSommets : Tableau de taille n; (int[n] en C)
}
****************************** ****************************** ****************************** ****************************** ****************************** *******
****************************** ****************************** ****************************** ****************************** ****************************** *******
2. ALGORITHMES / PROBLEMES DES SENS UNIQUES
* Pb : Orienter toutes les rues d'une ville en sens unique si possible
//ENTREE : Un graphe non orienté connexe dont les sommets sont les carrefours et les arrêtes les rues
//SORTIE : Un graphe orienté fortement connexe si aucune rue critique dans la ville
Une rue critique (arrête) sinon
fonction sensUnique(G : graphe) : graphe orienté ou arrête
DEBUT
global TabDates <- Pile_vide() ;
global n <- nb_sommets(G) ;
global T <- Créer_graphe_vide() ;
Parcours_profondeur(G, sélectionnerSommet(G) , 0) ;
Calcul_indices_critiques(G) ;
RueCritique <- Detecter_rue_critique(G , TabDates) ;
si ( Est_non_vide(RueCritique) ) alors
retourner ( RueCritique ) ;
sinon
retourner ( Orienter(G,T,TabDates ) ;
FIN
****************************** ****************************** ****************************** *******************
* Pb : Parcours_profondeur
//ENTREE : Un graphe G connexe, un sommet s, un entier compteur
//SORTIE : Un arbre couvrant T de G et un tableau TabDates regroupant les sommets par ordre
de date de détection pdt le parcours
fonction Parcours_profondeur (G: graphe , s: sommet , compteur: entier) : graphe x tableau
DEBUT
s.visité <- 1 ;
TabDates <- empiler(s);
s.date <- compteur;
T <- Ajouter_sommet(T,s);
pour chaque sommet y adjacent à s faire
si (y.date = 0) ) alors
Parcours_profondeur(G , y , compteur+1);
T <- Ajouter_arc(T,s,y);
finsi
finpour
FIN
****************************** ****************************** ****************************** *******************
* Pb : Tableau des indices critiques
//ENTREE : un graphe G (on rappelle que T et TabDates sont des variables globales);
//SORTIE : Met à jour les champs IndCritique des sommets.
fonction Calcul_indices_critiques(G , T: graphes): tableau
DEBUT
pour i<- n-1 à 0 faire
IndiceCritique <- n-1;
sommet<-dépiler(TabDates);
fils <- Successeurs( Différence(G, T), Sommet);
pour j<- 0 à taille(fils)-1 faire
si ( fils[j].date < IndiceCritique ) alors
IndiceCritique <- fils[j].date;
finsi
j<-j+1;
finpour
fils <- Successeurs(T, sommet);
pour j<-0 à taille(fils)-1 faire
si ( fils[j].IndCritique <IndiceCritique ) alors
Indice <- fils[j].IndCritique;
finsi
j<-j+1;
finpour
sommet.IndCritique <- IndiceCritique;
i<-i+1;
finpour
FIN
****************************** ****************************** ****************************** ******
* Pb : détection de rue critique
//ENTREE : l'arbre couvrant T issu du parcours en profondeur de G, un tableau regroupant par dates
de découvertes lors du parcours en profondeur croissantes les sommets de G
//SORTIE : une arrête de G critique s'il en existe, l'élément vide sinon.
fonction Detecter_rue_critique (T, TabDates) : Graphe
DEBUT
pour i<-0 à n-1 faire
s1 <- TabDates[i];
pour j<-i à n-1 faire
s2 <- TabDates[j];
si ( (T.MatriceLiaison [s1][s2] = 1) ET (s2.IndCritique > i) ) alors
retourner ((s1,s2));
finsi
j<-j+1;
finpour
i<-i+1;
finpour
retourner (élémentVide);
FIN
****************************** ****************************** ****************************** ******
* Pb : orienter les rues de la ville
//ENTREE : un graphe G sans arrête critique, son arbre couvrant par le parcours en profondeur
//SORTIE : un graphe orienté tel que tous les carrefours soient accessibles à partir de n'importe
quel autre carrefour de la ville
fonction Orienter(G , T : graphe) : Graphe
DEBUT
H <- Créer_graphe_vide(n);
H <- Union(H,T);
H <- H - MatIdentité(n) + Tansposer(H);
pour i<-0 à n-1 faire
s1 <- H.ListeSommet[i];
pour j<-i+1 à n-1 faire
s2 <- H.ListeSommet[j];
si (H.MatriceLiaison[i][j] = 1) alors
si (s1.Date > s2.Date) alors
H.MatriceLiaison[i][j]=1;
sinon
H.MatriceLiaison[j][i]=1;
finsi
j<-j+1;
finpour
i<-i+1;
finpour
retourner (H);
FIN
Mon probleme c'est que je suis debutant en C et j'ai du mal a coder ces algo en C et je vous demande de mon donner un coup de main.
Cordialement
-----