[PDF]

[PDF] Exemple de calcul de fermeture transitive avec les - Adrien Poupa

Voici le graphe pour lequel on se propose de calculer la fermeture transitive en calculant les puissances successives des matrices 1 2 3 4 5 6 La matrice 

[PDF] TP 6 Fermeture transitive dun graphe orienté

Le but de ce TP est de calculer la fermeture transitive d'un graphe orienté D, puis de l'utiliser afin de calculer les composantes fortement connexes de D Langage

[PDF] Graphes orientés - Université de Montréal

8 Graphes orientés Calculer la fermeture transitive d'un graphe On peut utiliser l'algorithme de parcours en profondeur à partir de chaque sommet: O(n(n+m))

[PDF] Théorie des graphes et optimisation dans les graphes Table - CNRS

peut modéliser ce problème par un graphe non orienté, dont les sommets matrice d'adjacence de la fermeture transitive Gf du graphe G de départ

[PDF] Fermeture transitive - Dimitri Watel

TD 2 : Fermeture transitive Théorie des Dessinez la fermeture transitive des graphes suivants : A B C D E A Soit G un graphe orienté sans circuit Montrer 

[PDF] Parcours de graphes - IRIF

13 déc 2017 · Les graphes sans circuits Fermeture transitive Données: un graphe orienté G = (X,U), un sommet x0 ∈ X Résultat: une arborescence de 

[PDF] Algorithmique de graphes - LIPN

Tri topologique dans un graphe orienté sans circuit Déterminer la fermeture transitive du graphe réduit Gr qui est sans circuit 3 Déduire la fermeture 

[PDF] Graphes Orientés - uOttawa

Utiliser l'Algorithme 5 16 (Algorithme 5 17) afin de trouver la fermeture transitive des graphes de l'Probl`eme 5 13 Montrer chaque matrice W(k) et graphe orienté  

[PDF] Les graphes BTS SIO2

longueur p, la fermeture transitive, les niveaux et chemin de valeur minimale 1 Graphes simples orientés a) Graphe – représentation sagittal b) Sommets – arcs  

[PDF] le temps de la révolution et de l'empire cycle 3

[PDF] fermeture transitive matrice

[PDF] décomposition d'un graphe en niveaux

[PDF] chemin hamiltonien

[PDF] de l'année 1789 ? l'exécution du roi cm1

[PDF] graphe d'ordonnancement

[PDF] sujet algorithme bts sio corrigé

[PDF] calcul matrice booléenne

[PDF] calcul matriciel bts

[PDF] prise de note rapide tableau abréviations

[PDF] sauzay programme

[PDF] programme voltaire

[PDF] un petit paragraphe sur l'environnement

[PDF] exemple de texte argumentatif sur l'environnement

[PDF] texte sur l'environnement

14/12/2009

et structuresdedonnéesavancés 11

PatrickReuter

http://www.labri.fr/~preuter/asda2009 surrécurrenceetTD8

Siteweb/solutions

Dictionnaires

Lesarbres

quipèsentp 1 ,p 2 ,...,p n grammes. •Cethommeàdeuxenfants ensemblesdisjointspourquelasommedespoids desdeuxsousͲensemblessoitégal?

Ils'agitduproblèmePARTITIONPARTITION

•Commenttrouverlespartitions? lessommesdesdeuxpoidssont

égales?graphes

-UnensembleV(G)={v1 ,v 2 ,...,v n }desommets(anglais: onevertex,twovertices)

14/12/2009

•Orientation: -lesgraphesnonorientés -lesgraphesorientés •degré •boucle •parité(sommetspairsetimpairs) •adjacence,voisinetvoisinage sommetisolésommetisolé •sousͲgraphe,clique •Isomorphisme •Chaîne,sousͲchaîne •Cycle •Grapherégulier •Graphecomplet •Grapheconnexe d'adjacence •SoitG=(V,E)avecV={s 1 ,s 2 ,...,s n 1si(s i ,s k )E,A i,k =0sinon decontacts descontacts...

PatrickPetra

d'adjacence pourchaquesommetpourchaquesommet

Matriced'adjacence

0 1 0 0 0 0 0

1 0 1 0 0 0 0

0 1 0 1 1 0 0

Patrick(1)

Jérôme(5)Petra(4)

(7) A

Pierre(2)Clémentine(3)

(6)

1:montrerlescontactsdirects

Entrée : Graphe G définie par une matrice d'adjacence A et un sommet s défini par son indice

fonction montrerContacts(s) début pour i de 1 à nbSommets(G) si(i s ET A[s][i]=1) alors afficher nom[i] à l' fin si fin pour fin { Montrer les conacts directs }

14/12/2009

unsommetadéjàétévisité

2:montrerlescontactsetles

contactsdescontacts

Entrée : Graphe G définie par une matrice d'adjacence A et un sommet s défini par son indice

fonction montrerContacts(s)

Début

marquerSommet(s) pour i de 1 à nbSommets(G) si (i s ET A[s][i]=1 ET NOT marqué(i)) alors afficher nom[i] à l' fin si fin pour fin { Montrer les contacts directs et les contacts des contacts directs }

Etape2:montrerlescontactsetles

contactsdescontacts

Entrée : Graphe G définie par une matrice d'adjacence A et un sommet s défini par son indice

fonction montrerContacts(s : integer) début marquerSommet(s) pour i de 1 à nbSommets(G) si (i s ET A[s][i]=1 ET NOT marqué(i)) alors pour j de 1 à nbSommets(G) si (j s ET A[i][j]=1 ET NOT marqué(j)) alors marquerSommet(j); afficher nom[j] à l'écran fin si fin pour fin si fin pour fin { Montrer les contacts directs et les contacts des contacts directs }

Etape3:Reconnaîtrelarécursivité

fonction montrerContacts(s : integer) début marquerSommet(s) pour i de 1 à nbSommets(G) si (i s ET A[s][i]=1 ET NOT marqué(i)) alors afficher nom[i] à l'écran pour j de 1 à nbSommets(G) si (j s ET A[i][j]=1 ET NOT marqué(j)) alors marquerSommet(j); afficher nom[j] à l'écran fin si fin pour fin si fin pour fin { Montrer les contacts directs et les contacts des contacts directs }

Etape4:Récursivité

Entrée : Graphe G définie par une matrice d'adjacence A et un sommet s défini par son indice

fonctionmontrerContacts(s : integer)

Début

marquerSommet(s); pour i de 1 à nbSommets(G) si (i s ET A[s][i]=1 ET NOT marqué(i)) alors fin si fin pour fin { Montrer les conacts directs et les contacts des contacts directs }

Vérificationdesdeuxconditionsd'un

algorithmerécursif nepass'appelerinfiniment -Quandtouslessommetsvoisinsd'unsommet

14/12/2009

d'adjacence

0 1 0 0 0 0 0

1 0 1 0 0 0 0

0 1 0 1 1 0 0

Patrick(1)

Jérôme(5)Petra(4)

(7) A

Pierre(2)Clémentine(3)

(6) transitive

GrapheG*

+=(V,E*+),oùunearête(i,j)̿E+ssi ilyaunechaînedeiàj. transitiveetréflexiveG*. transitive

1 1 1 1 1 0 0

1 1 1 1 1 0 0

1 1 1 1 1 0 0

•A:Matriced'adjacence

Fermeturetransitive

Matriced'adjacencedelafermeture

transitive •G(V,E):(Matriced'adjacenceA): -A i,k =1si(s i ,s k )E,A i,k =0sinon d'adjacenceA*) -A* i,k =1ssiilyaunechaînedes i às k pourlecalculscientifique -Maple -Matlab -Mupad -Scilab

14/12/2009

deWarshall d'ungrapheorientéounonorienté.

AlgorithmedeWarshall

•OnsupposequeA k Ͳ1 OU(A kͲ1 ETA kͲ1 •Matriced'adajcencedeG*:A n [i,j]

AlgorithmedeWarshall

Entrée:Matriced'adjacenceA

pourk de 1 à |V(G)| faire pouri de 1 à |V(G)| faire pourj de 1 à |V(G)| faire

A[i][k]=1 ET A[k][j]=1))

A[i][j]=1

else

A[i][j]=0

A[i][j] = A[i][j] OU (A[i][k] ET A[k][j])

deWarshall •Complexité -O(n 3 transitived'dungrapheunefoispourtoute, onpeutsavoirsilessommetss i ets j appartiennentà •Commenttestersiun grapheestconnexe? marquerSommet(s) visite[s]=true

POURtouslesvoisinsidesFAIRE

visite[i]==falseALORS marquerSommet(i)

14/12/2009

•Dictionnaires desclés "associativearray" •Rappel:PHP... MySQL

Parcourirlesenregistrenents

Dictionnaires •fa ={} •fa['salut']="hello" •fa['oui']="yes" •fa['non']="no" différencequ'ilssontnonmodifiables référencesréférences descrochets

14/12/2009

différencequ'ilssontnonmodifiables référencesréférences descrochets

Tuples

>>> x = (1,2,3) >>> x (1, 2, 3) >>> x[2]

Théoriedelacomplexité

ClassesdeGrandͲO

•O(1) complexitéconstante •O(logn)complexitélogarithmique •O(n) complexitélinéaire •O(nlognquasͲlin •O(n a) complexitépolynomiale -O(n 2) complexitéquadratique -O(n 3) complexitécubique •O(a n) complexitéexponentielle •O(n! complexitéfactorielle n)O(n)O(nlogn)O(n 2 )O(n 3 )O(a n )O(n!) delacomplexité-

Changementdelafonction

2èmesolution

changerlafonction •O(logn) logarithmique O(n) •O(n) linéaire •O(nlogn)

QuasiͲlinéaire

•O(n 2) quadratique •O(n 3) cubique •O(a n) exponentiel n

Informatiquethéorique

•Théoriedecomplexité •Théoriedecalculabilité

14/12/2009

quipèsentp 1 ,p 2 ,...,p n grammes. •Cethommeàdeuxenfants ensemblesdisjointspourquelasommedespoids desdeuxsousͲensemblessoitégal?

Ils'agitduproblèmePARTITION

PARTITION

•Commenttrouverlespartitions? lessommesdesdeuxpoidssontégales? decomplexité eninformatique lldi idlhé idl•Esedistdelatdela calculabilité pasêtrerésoluparunordinateur.

Théoriedecomplexité

effectivementêtrerésolus,

Savoirs'silyaunesolutionefficaceense

basantsuruneestimation(théorique) -desbesoinsenmémoireinformatique (complexitédemémoire)

Théoriedecomplexité

•Unproblèmeformalisédelamanièresuivante :

éventuellementuncalcul).

problèmesdedécisionbinaire (réponsesoitouiou non) decomplexité •Cependant: d' •Eneffet,ilestfaciledetransformerun problèmed'optimisationenproblèmede décision.

14/12/2009

decomplexité valeurn titlblèddé i iiità-ontraleprodedécquconsà comparernàuncertaink. -Entraitantplusieursvaleursdekonpeut déterminerunevaleuroptimale. TSP TSP- TravelingSalesmanProblem(Problèmeduvoyageurdecommerce)

étantdonné

retlesdistancesséparantchaquesommet, (nͲ1)!Possibilités!

Grapheorientéponderé

•G=(V,E,ʔ)

0 64 94

A = 64 0 47 78

94 47 0 65 197

78 65 0 193

197 193 0

TSP TSP- TravelingSalesmanProblem(Problèmeduvoyageurdecommerce)

étantdonné

retlesdistancesséparantchaquesommet, (nͲ1)!Possibilités! •TSPmétrique:

Onpeutpasserplusieursfoisparlememe

sommet

14/12/2009

Données :

tEbld' ttquotesdbs_dbs44.pdfusesText_44