# Presentation 17/02
[TOC]
### Légende
1: clics et touches du clavier
2: affichage (pixel)/rien
3: sommets selectionnés, arcs selecttiones, graphe, choix des interactions, taille du graphe
4: graphe, ?rien dans la supression?
5: nom du fichier, graphe
6: nom du fichier, message de validation (supression, suavegarde) ou contenu du fichier
7: graphe, sommet du graphe, message de demande d'actions
8: liste de sommets, graphe, message de validation de l'operation (ex: si on le nombre chromatique du graphe)
9: graphe modifié,
10: graphe,
### Manipulation de base
- Création d’une matrice d’adjacence(simple, complet, biparti, cycle…)
Prend en entrée la taille de ma matrice NxN.
Métrique:
- Vérifier si la matrice générée correspond au type de graphe demandé
- Complet : Matrice d'adjacence sans poids symétrique
- Biparti : Matrice bipartite
- Commun : Matrice qui respecte la logique des matrices d'adjacence et les futurs règles de stockage.
- Modification de matrice
Prend en entrée la matrice d’adjacence du graphe et le numéro du sommet N. Au niveau de la ligne et colonne N x N, on renvoie l’adresse de l’objet sommet.
Métrique :
- Si les valeurs ont changé comme souhaité
- Si nouveaux sommets la taille de la matrice a changée.
- Suppression de matrice
Métrique :
- Si y'a plus la matrice c'est bon
- Duplication de matrice
Instancie une nouvelle matrice M2 à partir de la matrice M1 passée en argument.
Métrique:
- Si la matrice retournée est identique à celle d'origine
- Conversion d'une matrice d'adjacence en matrice d'incidence
Métrique:
- Vérifier la correspondance entre la matrice d'adjacence mère et la matrice d'incidence fille
- Conversion d'un arbre en codage de Prüfer
Métrique:
- Vérifier la correspondance entre la matrice d'adjacence mère et la liste de Prüfer
- Vérifier que cet algorithme s’exécute dans le cas où le graphe est un arbre.
- Conversion d'une matrice d'adjacence en matrice d'incidence
Métrique:
- Verifier par la conversion qu'on obtient la meme matrice d'adjacence de base.
- Verifier que le nombre de colonnes est égale au nombres d'arv dans le graphe
- Conversion d’un arbre en codage de Prüfer et inversement
métrique: obtention d'une liste ou d'une matrice en fonction du résultat demandé. conversion inverse, vérifier si on obtient le même arbre.
###### Entrée/Sortie
Entrée :
Matrice de taille NxM, Sommet S de la matrice M
Sortie :
Adresse d'un sommet, matrice d'adjacence, matrice d'incidence, codage de Prüfer
### Opérations sur les graphes
### Interface graphique
##### Métrique
- Affichage global
- Avoir un graphe affiché
- Possibilité de déplacer/ajouter/supprimer un arc ou un sommet
- Afficher les valeurs (poids des arcs, nom des sommets)
- Selection d'un ou de plusieurs sous graphe (minimum 2 sommets et un arc)
- Changer les valeurs (poids, nom des sommets)
- Test d'algo de superposition
- Vérifier que les graphes ne se superpose pas en un seul sommet, vérifier la lisibilité des graphes
###### Entrée/Sortie
- Affichage des données globales :
-> graphes à afficher ( numéro, poids )
-> type de graphes ( couvrant, complet, ..)
-> nb d'arcs, de sommets
- Aficher des données par sommet :
-> degré entrant/sortant
- modifier arc, somme, sous-graphe
- déplacer arc, sommet, sous-graphes(sélection)
- selection arc, sommet, sous-graphes ( 2 sommets & 1 arc minimum)
- Alg de positionnement (dans l'espace )
### Systeme de Gestion de fichiers
###### Entrée/Sortie
- Sauvegarde normale:
Entree -> Nom de fichier, graphe
Sortie -> Message de validation
- Suppression:
Entree -> Nom du fichier
Sortie -> Message de validation
- Chargement: verification du format
Entree -> Nom du fichier
Sortie -> Informations contenue dans le fichier (graphe, position des sommets et arcs, informations sur les arcs, information des sommets)
- Sauvegarde avancée (enregistrer sous):
Entree -> Nom du fichier, chemin du fichier, graphe
Sortie -> Message de validation
##### Contraintes pour les fichiers:
- Nombre de sommets négatifs
- Taille du fichier
- Format du fichier (nombre de colonne / ligne )
#### Metriques:
- Vérifier qu'il soit au bon format
- Vérifier qu'il écrase au bon endroit (dans le cas de la sauvegarde simple)
- Vérifier que la sauvegarde écrit correctement le fichier (respect la syntaxe)
- Vérifier que les données issues d'un fichier se charge correctement
- Vérifier la suppression du fichier
- Vérifier la validité du chemin
Type de fichiers : TxT, autre chose ??
## Algorithmes et Entrées-Sorties
Coût = nb personnes + lignes de code + complexité
### Matrice d'adjacence
### Matrice d'incidence : *O(n<sup>2</sup>)*
Calcul depuis la matrice d'adjacence.
### Degrés entrants et sortants : *O(n<sup>2</sup>)*
Calcul le degré pour 1 sommet et appel dans interface logiciel pour calculer tout les sommets.
```
a b c d e f
a 0 1 1 1 0 1
b 1 0 0 1 0 1
c 0 0 0 1 1 0
d 1 0 1 0 1 0
e 0 1 1 1 0 1
f 1 0 0 1 0 0
```
Pour b par exemple on parcours de position(b) de 0 à n
et de 0 à n position(b)
```
Algorithme (Qui affiche le degrès entrant/sortant/nb_voisin total)
---------------------------------------------------------------
Entrée : k = position(sommet), MA[n][n] (matrice d'adjacence)
succ = 0;
pred = 0;
nb_voisin = 0;
Pour i de 0 à n
| Si (MA[i][k] == 1)
| | succ++;
| | nb_voisin++;
| Fin Si
| Si (MA[k][i] == 1)
| | pred++;
| | nb_voisin++;
| Fin Si
Fin Pour
Afficher(succ);
Afficher(pred);
Afficher(nb_voisin);
```
sinon appliquer l'algo pour tout les sommets et mettre les résultats dans une matrice (N x 3) (ou plus suivant les informations à sauvegarder)
### Liste de voisins : *O(n)*
Entrée : Graphe
Sortie : liste de voisins (txt)
Calcul pour 1 sommet et appel dans interface logiciel pour tout les sommets.
### Calcul du plus court chemin
Entrée : Graphe, sommet de départ
Sortie : Matrice de sommets pères
3 fonctionalitées différentes :
- Entre tout les sommets : **Floyd-Warshall** *O(n<sup>3</sup>)*
```
Matrice Adjacence Matrice Sommet Père(not Floyd-Warshaliser)
a b c d e f a b c d e f
a 0 1 1 1 0 1 a 0 b c d 0 f
b 1 0 0 1 0 1 b a 0 0 d 0 f
c 0 0 0 1 1 0 => c 0 0 0 d e 0
d 1 0 1 0 1 0 d a 0 c 0 e 0
e 0 1 1 1 0 1 e 0 b c d 0 f
f 1 0 0 1 0 0 f a 0 0 d 0 0
```
```
Algo Floyd-Warshall
-------------------------------------------------------------------------------
Entrée: MA[n][n] (matrice d'adjacence),MP[n][n] (Matrice Sommet Père)
W = MA (si MA[i][j] == 0 alors W[i][j] = infini, si i==j alors W[i][j] = 0 )
Pour k allant de 1 à n
| Pour i allant de 1 à n
| | Pour j allant de 1 à n
| | | si (W[i,j] > W[i,k] + W[k,j])
| | | | W[i,j] = W[i,k] + W[k,j]
| | | | MP[i,j] = MP[i,k];
| | | Fin Si
| | fin pour
| fin pour
fin pour
```
- Entre 2 sommets : ??
- D'un sommet à tout les autres : ??
---
- **Dijkstra**
```
1 function Dijkstra(Graph, source):
2
3 create vertex set Q
4
5 for each vertex v in Graph:
6 dist[v] ← INFINITY
7 prev[v] ← UNDEFINED
8 add v to Q
10 dist[source] ← 0
11
12 while Q is not empty:
13 u ← vertex in Q with min dist[u]
14
15 remove u from Q
16
17 for each neighbor v of u: // only v that are still in Q
18 alt ← dist[u] + length(u, v)
19 if alt < dist[v]:
20 dist[v] ← alt
21 prev[v] ← u
22
23 return dist[], prev[]
```
- **Ford-Bellman** : *O(n<sup>2</sup>)*
```
Entrée : (G,w,s)
Pour tout sommet v appartenant à V
| [v] = +infini
| pi[v] = NULL
d[s] = 0, L = {S}
Tant que L ! 0
```
### Arborescence de poids minimal : *O(EV)*
Entrée : Graphe (Matrice)
Sortie : Sous-graphe (matrice)
- Chu-Liu/Edmonds
E : ensemble des arcs
V : ensemble des sommets
### Coloration de graphe et nombre chromatique
Entrée : Graphe
Sortie : Matrice 2D avec la couleur de chaque sommets.
- Welsh et Powell *O(n\*m)* ou *O(n ln(n) +m)*
```
- Trier les sommets par ordre de degrés décroissants
- Attribuer au premier sommet A une première couleur
- suivre la liste en attribuant la même couleur au premier sommet B non adjacent à A
- Continuer à parcourir la liste en attribuant la couleur aux sommets non adjcents à ceux déjà colorés
- Lorsque la liste est finie prendre une deuxième couleur et repartir du début de la liste
```
- DSATUR *O(n<sup>2</sup>)* ou *O(n<sup>2</sup> + n\*m)*
```
- Trier les sommets par ordre de degrés décroissants
- Attribuer au premier sommet A une première couleur
- Choisir le sommet avec le plus couleurs différentes dans les sommets adjacents et le colorer avec la plus petite couleur possible
- En cas d'égalité choisir le sommet de degré maximum
```
- Algorithme glouton *O(n\*m)*
```
On regarde l'ensemble des couleurs déjà attribuées aux voisins de s et on en déduit le plus petit entier naturel qui n'appartient pas à cet ensemble
```
### Chaine Eulérienne
Entrée : Graphe
Sortie : liste (vide ou non) + algo si liste vide
```
Eulérien G(X,Y)
---------------------
parcours eulerien=
principe:
on marque tous les arcs utilisé
si tous marqué alors chaine eulerienne
sinon on insert un cycle dans cette chaine
```
### Chaine Hamiltonienne
Entrée : Graphe
Sortie : liste (vide ou non) + algo si liste vide
```
Input: Vertex v and position k.
Output: Checks whether placing v in the position k is valid or not.
Begin
if there is no edge between node(k-1) to v, then
return false
if v is already taken, then
return false
return true; //otherwise it is valid
End
```
```
cycleFound(node k)
Input: node of the graph.
Output: True when there is a Hamiltonian Cycle, otherwise false.
Begin
if all nodes are included, then
if there is an edge between nodes k and 0, then
return true
else
return false;
for all vertex v except starting point, do
if isValid(v, k), then //when v is a valid edge
add v into the path
if cycleFound(k+1) is true, then
return true
otherwise remove v from the path
done
return false
End
```
### Cliques
Sous-graphes complet, coût linéaire
UNION-find (cf Hugo)
### Stables
- Stable maximale *O(n^2)
```
Entrées : un graphe G = (X, A), non orienté
Sorties : un stable maximal S de G
Pour chaque sommet x de G faire
marque[x] ← FAUX
S←∅
tant qu'il existe un sommet x sommets non marqué faire
S ← S ∪ {x}
marque[x] ← V RAI
pour chaque y ∈ Γ(x) faire
marque[y] ← V RAI
Retourner S
```
- Luby's Algorithm *O(log n)*
```
Algorithm 1 MIS(G=(V,E)) Maximal Independant Set
1: Add all singletons to I
2: I ← ∅
3: Chaque v choisit une valeur aléatoire P (v) ∈ [0, 1]
4: Si P(v) < P(w), Pour tous w ∈ N(v) then
5: Ajoutez v into I
6: Fin Si
7: V ′ = V \ (I ∪ N(I))
8: E′=E\Bords(I ∪ N(I))
9: Return I ∪ MIS(G′ = (V ′, E′))
```
- Random-priority parallel algorithm *O(n)*
```
Initialisez I, un ensemble vide
While V est non vide ,
Pour chaque noeud v Faire :
Selectionner un nombre aléatoire r(v) dans [0,1] et l'envois. à ses voisins;
Si r(v) est plus petit que les nombres de tous les voisins de v,
alors v s'insère dans I, se retire de V et en informe ses voisins.
Si v a appris qu'un de ses voisins est entré dans I,
alors v se retire de V.
Return I.
```
### Optimisation des tâches
PERT:
Entrée:
| Code de la tache | Durée | Antériorités |
|:----------------:|:-----:|:------------:|
| A | 12 | - |
| B | 15 | - |
| C | 17 | A, B |
| D | 8 | B |
- Création du sommet Départ
- On parcours la liste des sommets, si il n'y a pas de contraintes d'antériorités, on créé un arc entre Départ et ce sommet, avec pour valeur la durée. On ajoute la valeur au plus tôt pour le nouveau sommet avec pour valeur la durée
- Si il y a une antériorité, on créé un arc entre le sommet antérieur et le nouveau sommet, avec pour valeur la durée. On ajoute la valeur au plus tôt qui est égale à la somme de la durée et de la valeur au plus tôt du sommet antérieur.
- Si il y a plusieurs antériorités, on créé un arc entre le sommet antérieur ayant la plus grande valeur au plus tôt et le nouveau sommet. On ajoute la valeur au plus tôt qui est égale à la somme de la durée et de la valeur au plus tôt du sommet antérieur. On créé des arcs informels de valeur 0 qui partent de tous les sommets antérieurs non utilisés vers le sommet antérieur utilisé.
- Une fois qu'on arrive au dernier sommet, sa valeur au plus tard est égale à sa valeur au plus tôt
- Pour chaque sommet, sa valeur au plus tard est égale au minimum de la valeur au plus tard de ses successeurs moins la valeur de l'arc.
### Gestion des flots
- Ford-Fulkerson : Complexité de *O(n m<sup>2</sup>)*
```
```
- tri topologique
```
Algorithme tri_topo (Graphe g)
Entrée : Un graphe G =(V,E) orienté non cyclique.
Sortie : La liste des sommets dans l'ordre topologique.
Variables : listeSommets = []
t = 0 //C'est la variable qui établira les dates d'entrées et sorties.
tabCouleur = [] //Le tableau qui indiquera la couleur et donc le traitement d'un sommet.
Exécution : Pour i allant de 1 à nbSommets :
ajouter(tabCouleur, 0) //On initialise tous les sommets à blancs, soit non traité.
Fin Pour;
Pour chaque x appartenant à V Faire :
Si couleur(x) = Blanc alors :
Parcours_Profondeur_Topo(G, listeSommets, x, t)
Fin Pour;
Afficher(listeSommets) et/ou Retourner(listeSommets)
Fin Exécution;
```
```
Algorithme Parcours_Profondeur_Topo(G, listeSommets, x, t)
Entrée : Un graphe G =(V,E) orienté non cyclique.
La liste des sommets.
Le sommet en traitement.
La date.
Sortie : Les sommets empilés dans l'ordre topologique dans listeSommets.
Exécution : couleur(x) = Gris
t = t + 1
dateDébut(x) = t
Pour chaque y appartenant à Γ+ (x) Faire : //Γ+ (x) est l'ensemble des voisins de x.
Si couleur(y) == Blanc alors :
Parcours_Profondeur_Topo(G, listeSommets, y, t)
Fin Si;
Fin Pour;
couleur(x) = Noir
t = t + 1
dateFin(x) = t //Les dates ne sont pas nécessaires à l'algorithme mais pourraient être utilisées à d'autre fins.
empiler(x, listeSommets)
Fin Exécution;
```
### Le problème du voyageur de commerce
#### Explication du problème
Le problème du voyageur de commerce est le problème suivant: pour un réseau de sommets donné avec des arcs pondérés, comment effectuer le cycle le plus court possible ?
#### Algoritme de Chirstofides
En pseudo-code :
- Calculer un arbre couvrant de poids minimal T de G ;
- Soit I l'ensemble des sommets de degré impair dans T, calculer un couplage parfait M de poids minimum dans le sous-graphe induit par les sommets de I ;
- On définit un multigraphe H à partir des arêtes issues de M et T ;
- Trouver un cycle eulérien dans H (H est eulérien car il est connexe et tous les sommets sont de degrés pairs) ;
- Transformer le cycle eulérien en un cycle hamiltonien en supprimant les éventuels passages en double sur certains sommets.
c'est un algorithme de complexité cubique. Cependant, il est important de préciser que c'est un algorihme d'approximation. C'est à dire que l'on s'approche du résultat de manière assez importante sans pour autant y parvenir.
#### Algorithme de Little
```algorithme de Little :
maxi = +inf
s[racine] = ville de depart
calculer e[racine]
visiter la racine
visiter un noeud n :
SI e[n] <= maxi
ALORS
SI s[n] != ville de depart
ALORS
POUR toutes les liaisons s[n] -> v possibles
calculer le regret de s[n] -> v
FIN POUR
soit s[n] -> v une liaison de
regret maximal r
créer les fils v et V de n
s[v] = v
calculer e[v]
visiter v
s[V] = s[n]
e[V] = e[n] + r
visiter V
SINON
maxi = max[maxi, e[n])
FIN SI
FIN SI
```
c'est un algorithme de complexité linéaire.
### Algorithmes choisis
- Plus court chemin :
- Tout les sommets : Floyd-Warshall car il permet de trouver l'ensemble des plus courts chemins. *O(n<sup>3</sup>)*
- Un sommet vers tout les autres : Ford-Bellman pour les plus courts chemins d'un somet vers tous les autres car contrairement à Dijkstra il permet les poids négatifs sur les arcs. *O(n<sup>2</sup>)*
- Entre deux sommets : Ford-Bellman
- Arborescence de poids minimal : Algo D'Edmonds, il fournit une arborescence couvrante de poids minimal. *O(EV)*
- Coloration de graphes : DSATUR donne une coloration moins mauvaise que Welsh-Powell dans le pire des cas (par-exemple si le graphe G a la structure de couronne à n sommets). *O(n<sup> 2</sup>)
- Stables :
- Cliques :
- Optimisation des tâches : PERTERTERT
- Gestion des flots :
- Problème du voyageur de commerce : Algorithe de Little car il résout le problème en temps linéaire par rapport aux nombre de sommets entrés. De plus, l'algorithme de Chistofides donne une solution approximative.
- Chaine Eulérienne
- Chaine hamiltonienne
Sign in with Wallet
Connect another wallet