Discussion :

[Mike888]

Salut !


Je suis occupé avec le développement d'un prog qui doit tester les propriétés d'un graphe.
Et je cale sur l'algo de la connexité.

J'ai trouvé ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 
const n = 8;
type t_tableau=array[1..n] of boolean;
var marquer : t_tableau;
 
procedure marquerSommets(s : integer);
 var i : integer;
 begin
 marquer[s] := True;
 for i:=1 to n do begin
  if ((marquer[i]=False) AND (graphe[s][i]=1)) then
   begin
    marquerSommets(i); { Appel recursif ! }
   end;
 end;
end;
 
 
function estConnexe : boolean;
var i:integer;
begin
for i:=1 to n do
 marquer[i]:= False;
 marquerSommets(1);
 result := True;
 for i:=1 to n do
  begin
  if marquer[i]= False then
  begin
   result := False;
  end;
 end;
end;

Mais le problème est qu'il n'est pas correct dans certains cas, comme ici par exemple :

0 0 1
0 0 1
0 0 0

Il zappe la 2eme ligne !
Est-ce que c'est normal ?

[FrancisSourd]

Comme la matrice n'est pas symétrique, tu fais un parcours orienté: depuis 3 tu ne peux pas aller à 2 car l'arc va de 2 vers 3: il faut rendre ta matrice symétrique ou lancer l'appel récursif si (graphe[i][s]=1 OR graphe[s][i]=1)

[Mike888]

Aaaah ok

Donc, pour voir s'il est simplement connexe :

- je fais comme tu as dit (je le symétrise);


Si par contre, je veux voir s'il est fortement connexe :

- là, je laisse comme c'est !


Merci !

[FrancisSourd]

Non pour le "fortement connexe", c'est en fait plus compliqué: si ton graphe est composé de deux sommets et d'un seul arc allant de 1 vers 2, ce graphe n'est pas fortement connexe car on ne peut pas aller de 2 vers 1. En revanche un parcours en profondeur à partir de 1 te permet bien de visiter tous les noeuds.

Dans le cours "Théorie des grpahesé présent sur ce site, il y a quelques paragraphes sur le calcul de composantes fortement connexes
http://lapoire.developpez.com/algorithmique/graphes/

[Mike888]

Oulalah...

J'ai visité ton lien (page 54), mais je dois dire que je comprends vraiment pas grand chose ...

J'ai comrpis qu'il fallait faire un 2nd parcours sur la matrice transposée... mais à part ça

Concrètement, ça implique quoi ? C'est compliqué à mettre en place ?

[Mike888]

J'ai une autre question (outre celle de ci-dessus) ...

A propos de la transitivité : "Est-ce que les relations réflexives interviennent dans la notion de transitivité ? "

Exemple 1 :

Si j'ai ceci comme graphe :



-> Est-ce qu'en rajoutant la relation (a,a), le graphe devient transitif ?




Exemple 2 :

Est-ce que ces 2 matrices sont transitives (ou bien seulement la 1ere) ?

1 1 1 1
1 1 1 1
0 0 0 0
0 0 0 0

0 1 1 1
1 0 1 1
0 0 0 0
0 0 0 0