2. LES GRAPHES TEMPORELS

Dans le premier chapitre, nous avons exposé quelques problèmes de synchronisation hypermédia (inter-média plus précisément) liés à la réalisabilité et à l'optimisation d'une planification pour la présentation synchronisée d'objets multimédia. Nous présentons ici une modélisation sous forme de graphe. Celle-ci ne permet pas de représenter toutes les spécifications désirées par les auteurs de documents hypermédia synchronisés, mais tente néanmoins d'en rassembler les principales. Travaillant en collaboration avec les concepteurs d'HyperProp (cf. [Soares00]), le choix des spécifications à prendre en compte dans notre modélisation a fortement été guidée par leurs besoins.

Mais avant d'étudier cette modélisation, il nous semble nécessaire de consacrer une section à l'introduction de notions et de propriétés élémentaires sur les graphes indispensables pour la compréhension du document et éventuellement pour intégrer les algorithmes des prochains chapitres dans un logiciel de conception et/ou de présentation de documents hypermédia synchronisés. Après quelques rappels très généraux sur les graphes, nous introduisons les notions de flot et de tension. Nous verrons dans les chapitres suivants qu'une relation très forte entre le flot et la tension, la dualité, joue un rôle très important dans les méthodes de résolution que nous présentons.

Après cette introduction, nous présentons la modélisation sous forme de graphe retenue, et précisons les restrictions qu'elle impose. Nous montrons ensuite que les problèmes de synchronisation hypermédia peuvent ainsi être considérés comme des problèmes de tension dans un graphe. En particulier, nous discutons de la pertinence des problèmes de la tension compatible et de la tension de coût minimal pour l'aspect hypermédia, et pour lesquels nous présentons des méthodes de résolution dans la seconde partie du mémoire. Nous exposons finalement différentes manières de mesurer la qualité d'une planification qui semblent significatives pour les auteurs de documents hypermédia, toutes ne seront pas abordées par la suite.

Cette section nous a semblé nécessaire pour rassembler les notions de base concernant les graphes. Le lecteur novice dans ce domaine y trouvera tous les éléments indispensables au suivi des chapitres suivants du mémoire. Pour le lecteur plus confirmé, il est possible d'utiliser cette section comme référence pour une définition ou un théorème.

En complément, nous proposons également un annexe qui regroupe des algorithmes dont le détail est jugé peu important dans le flot de nos réflexions, mais néanmoins utile notamment pour l'interprétation et la reproduction des résultats numériques. Cette section introduit aussi quelques propriétés nécessaires pour la génération aléatoire de problèmes pour nos jeux d'essais dont les principaux algorithmes sont détaillés dans l'annexe.

Une remarque importante sur la notation employée tout au long de ce document: les fonctions dont le domaine de définition est discret et fini (e.g. un ensemble d'arcs ou de noeuds) seront souvent utilisées comme des vecteurs. Ainsi une fonction pourra être considérée comme un vecteur dont les composantes seront notées .

Pour illustrer les définitions présentées ici, nous allons utiliser le graphe représenté par la figure 2.1, noté , où est l'ensemble des noeuds et est l'ensemble des arcs. Nous notons le nombre de noeuds de et le nombre d'arcs.

Ce graphe est orienté, cela signifie qu'une distinction est faite entre les deux extrémités (i.e. les noeuds) d'un arc. On appelle noeud origine le noeud d'où part l'arc et noeud destination le noeud où arrive l'arc. Ainsi pour un noeud , on appelle arcs entrants tous les arcs ayant pour noeud origine et arcs sortants tous les arcs ayant comme noeud destination.

Nous désignerons souvent un arc de source et de destination par le couple , bien que cette notation soit abusive dans la mesure où plusieurs arcs peuvent avoir même origine et destination . Dans un tel cas est appelé un arc multiple. Un multigraphe est un graphe possédant au moins un arc multiple.

On désignera par sens direct l'utilisation d'un arc dans le sens origine-destination et par sens indirect son utilisation dans le sens destination-origine.

Figure 2.1: Un exemple de graphe.

Le degré sortant, noté , d'un noeud est le nombre de ses arcs sortants et son degré entrant, noté , est le nombre de ses arcs entrants. Le degré d'un noeud est la somme de ses degrés sortant et entrant. Un noeud dont le degré entrant est nul est appelé noeud source du graphe. De même, un noeud dont le degré sortant est nul est appelé noeud puits du graphe.

On dit que deux arcs sont adjacents s'ils ont au moins une extrémité (le noeud origine ou le noeud destination) en commun. Un noeud est adjacent à un arc s'il est au moins l'une des deux extrémités de l'arc.

On désigne par chaîne une succession d'arcs dans un graphe telle que deux arcs consécutifs dans la chaîne sont adjacents dans le graphe. Si l'on considère une chaîne , on notera l'ensemble des arcs qui sont dans le sens de parcours et l'ensemble des arcs qui sont dans le sens opposé.

On appelle chemin une chaîne dont les arcs sont tous orientés dans le même sens, i.e. pour deux arcs consécutifs, le noeud destination du premier est le noeud source du second.

On désigne par chaîne élémentaire (respectivement chemin élémentaire) une chaîne (respectivement un chemin) qui ne passe qu'une seule fois par un même noeud.

D'après la figure 2.1, voici quelques exemples de chaînes et de chemins.

• est une chaîne (pas élémentaire),

• est une chaîne élémentaire,

• est un chemin (pas élémentaire),

• est un chemin élémentaire.

On appelle cycle une chaîne non vide telle que le noeud de départ et le noeud d'arrivée sont identiques (e.g. le cycle dans la figure 2.2). Si l'on considère un cycle et qu'on lui choisit arbitrairement un sens de parcours, on notera l'ensemble des arcs qui sont dans ce sens de parcours et l'ensemble des arcs qui sont dans le sens opposé. Si tous les arcs sont dans le même sens, le cycle est appelé un circuit.

Comme les chaînes et les chemins, un cycle élémentaire (respectivement un circuit élémentaire) est un cycle (respectivement un circuit) qui ne passe qu'une seule fois par un même noeud. Pour des facilités d'écriture, un cycle élémentaire noté pourra être considéré comme un vecteur d'entiers, ses composantes seront notées pour tout arc du graphe , telles que:

Dans la figure 2.2, le cycle peut être représenté par le vecteur , en supposant les arcs dans l'ordre .

Figure 2.2: Un exemple de cycle.

Si un graphe est sans cycle, alors (cette propriété se démontre facilement par récursivité sur la taille du graphe).

Soit un sous-ensemble des noeuds de . On note le cocycle de . Il s'agit de l'ensemble des arcs de qui ont une extrémité dans et l'autre dans , i.e. les noeuds qui ne sont pas dans (e.g. le cocycle dans la figure 2.3).

L'ensemble peut être séparé en deux sous-ensembles: qui contient les arcs du cocycle qui ont leur source dans , et qui contient ceux qui ont leur destination dans . Si tous les arcs sont dans le même sens, le cocycle est appelé un cocircuit.

Figure 2.3: Un exemple de cocycle.

De la même manière que le cycle, un cocycle noté pourra être considéré comme un vecteur d'entiers, ses composantes seront notées pour tout arc du graphe , telles que:

Dans la figure 2.3, le cocycle peut être représenté par le vecteur , en supposant les arcs dans l'ordre .

Deux noeuds et sont connectés si et seulement s'il existe une chaîne entre et ou bien . Un graphe est dit connexe si et seulement si tous ses noeuds sont connectés deux à deux.

Deux noeuds et sont fortement connectés si et seulement s'il existe un chemin de à et un chemin de à , ou bien . Un graphe est dit fortement connexe si et seulement si tous ses noeuds sont fortement connectés deux à deux.

Si le graphe est connexe, alors (cette propriété se démontre aisément par récursivité sur la taille du graphe).

On appelle composante connexe (respectivement composante fortement connexe) un ensemble de noeuds dont tous les noeuds sont connectés (respectivement fortement connectés) deux à deux et tout noeud extérieur à la composante n'est pas connecté (respectivement fortement connecté) à aucun noeud de la composante.

Pour exemple, le graphe de la figure 2.1 est connexe, mais pas fortement connexe. En revanche, la composante est fortement connexe.

Soit un graphe , le sous-ensemble de noeuds , et les sous-ensembles d'arcs et . Voici la définition de graphes qui peuvent être formés à partir de ces ensembles.

• Le graphe est appelé sous-graphe de . Autrement dit, un sous-graphe de , c'est privé de quelques noeuds et des arcs adjacents à ces noeuds.

• Le graphe est appelé graphe partiel de . Autrement dit, un graphe partiel de , c'est privé de quelques arcs.

Un arbre est un graphe connexe sans cycle. De cette définition découlent les propriétés suivantes.

• Tous les noeuds d'un arbre sont reliés par une chaîne (grâce à la connexité) et une seule (sinon deux chaînes formeraient un cycle).

• Un arbre à sommets contient exactement arcs (car connexe signifie et sans cycle signifie ).

• Un arbre possède au moins deux noeuds de degré 1 (cette propriété se vérifie facilement par récursivité sur la taille de l'arbre).

• L'ajout d'un seul arc dans un arbre introduit un cycle (car devient supérieur à ).

• La suppression d'un seul arc dans un arbre introduit deux composantes connexes (car devient inférieur à ).

Figure 2.4: Un exemple d'arbre recouvrant.

On appelle arbre recouvrant d'un graphe un arbre tel que . Autrement dit, un arbre recouvrant de est un graphe partiel connexe de sans cycle. Le graphe de la figure 2.4 est un arbre recouvrant du graphe de la figure 2.1. Un algorithme de recherche d'arbre recouvrant dans un graphe est détaillé dans l'annexe.

Un noeud est une racine du graphe si pour tout noeud de il existe un chemin de à . Un arbre de racine est appelé une arborescence de racine .

En particulier, nous empruntons le terme arbre binaire au domaine des structures de données pour la suite de ce document. Il désigne une arborescence pour laquelle tous les noeuds ont un degré entrant égal à (exceptée la racine pour laquelle c'est ) et un degré sortant d'au plus . Un exemple est montré par la figure 2.5.

Figure 2.5: Un exemple d'arbre binaire.

En partant de la racine et en suivant les arcs dans le sens direct de gauche à droite, une arborescence représente un ordre sur les noeuds. Nous proposons ainsi une notation récursive des arbres binaires. Supposons la racine d'un arbre binaire , si l'on supprime la racine, on se retrouve avec deux arbres et , que l'on nomme sous-arbres. sera alors représenté par le triplet . Pour chaque sous-arbre, on recommence l'opération jusqu'à avoir des sous-arbres vides qui seront symbolisés par . Voici la représentation de l'arbre binaire de la figure 2.5.

Nous proposons ici les structures les plus populaires pour représenter un graphe. Très souvent, les performances d'un algorithme sont liées à la structure de graphe employée. En effet, chaque structure est très efficace pour un certain type d'opération, mais est souvent mauvaise pour d'autres. Ainsi, il est impossible d'avoir une structure qui soit la plus efficace pour toutes les opérations. Dans notre étude, nous avons choisi de ne pas favoriser une ou plusieurs opérations en particulier et nous avons opté pour une structure qui a une efficacité à peu près égale pour toutes les opérations de base. Notre structure n'est donc jamais la plus efficace pour un algorithme mais n'est aussi jamais la plus médiocre.

Pour commencer, nous présentons des structures sous forme de matrice qui s'avèrent très intéressantes à manipuler d'un point de vue théorique. Ensuite, nous nous intéressons à une modélisation par listes d'adjacence qui est très similaire à la structure que nous avons utilisée pour coder les algorithmes. Le détail de notre structure est proposé dans l'annexe.

Un graphe peut être représenté par une matrice de dimension , dite matrice d'incidence noeud-arc, pouvant contenir uniquement les valeurs , et . Chaque ligne de la matrice est associée à un noeud et chaque colonne à un arc. Ainsi, une composante indique la relation qu'il existe entre un noeud et un arc . Pour chaque composante de la matrice , on a:

Pour exemple, voici la représentation par matrice d'incidence du graphe de la figure 2.1.

La structure de cette matrice est assez particulière. Seulement des composantes sont non nulles. Elle occupe donc beaucoup de place en mémoire. En outre, son utilisation n'apporte que rarement (dans le cas où la matrice elle même a de l'intérêt) de bons résultats au niveau des algorithmes. En effet, rien que le parcours du graphe s'avère difficile. Cependant, cette matrice a des propriétés mathématiques très intéressantes, notamment le fait qu'elle soit unimodulaire.

Soit une matrice . est dite unimodulaire si les conditions suivantes sont vérifiées.

• est à composantes entières.

• est de rang maximal (i.e. de rang ).

• Toute sous-matrice carrée de a un déterminant égal à , ou .

Le résultat intéressant de cette unimodularité est le suivant. est unimodulaire si et seulement si toute solution de base du système linéaire , avec , est entière lorsque est un vecteur d'entiers. Autrement dit, la résolution d'un programme linéaire de la forme:

avec la méthode du Simplex fournit une solution optimale à composantes entières pour tout vecteur d'entiers , à condition bien entendu que le problème soit borné et possède au moins une solution réalisable.

Un graphe peut être représenté par une matrice de dimension , dite matrice d'adjacence noeud-noeud, pouvant contenir uniquement les valeurs et . Chaque ligne et chaque colonne de la matrice est associée à un noeud. Ainsi, une composante indique la relation qu'il existe entre deux noeuds et . Pour chaque composante de la matrice , on a:

Dans cette matrice, seulement des composantes sont non nulles. Cette représentation sera donc efficace au niveau de l'espace mémoire utilisé lorsque le graphe est suffisamment dense (i.e. lorsqu'il y a suffisamment d'arcs). Néanmoins, cette représentation permet d'implémenter assez facilement les algorithmes. Son utilisation apporte plus souvent de bons résultats au niveau des algorithmes que la matrice d'incidence, en particulier si le graphe est dense. Malheureusement, il faut noter une simplification importante dans la modélisation: on suppose qu'il n'y a pas d'arc multiple dans le graphe. Pour exemple, voici la représentation par matrice d'incidence du graphe de la figure 2.1.

L'un des inconvénients de la représentation sous forme de matrice est la difficulté à connaître pour un noeud tous les arcs qui lui sont adjacents, information qui est très utilisée dans les algorithmes. D'où la modélisation dite par listes d'adjacence. Tous les arcs sont stockés dans une liste, tous les noeuds dans une autre et chaque noeud possède deux listes: une pour les arcs entrants (i.e. ), une autre pour les arcs sortants (i.e. ). La figure 2.6 montre comment représenter le graphe de la figure 2.1.

Figure 2.6: Un exemple de représentation par listes d'adjacence.

Plusieurs remarques pratiques peuvent être faites sur cette figure. Tout d'abord, pour les représentations par matrice, nous n'avons parlé que de la représentation de la structure du graphe en omettant volontairement la représentation des informations portées par les noeuds ou par les arcs, puisque nous n'allons pas utiliser ces structures en pratique.

Pour la représentation par listes d'adjacence, les informations seront stockées au niveau des identifiants, par exemple pour le noeud (resp. l'arc ), ses données seront stockées à l'endroit noté (respectivement ) sur la figure. Ainsi les listes des arcs entrants ou sortants ne contiennent que des références sur les arcs afin d'éviter toute redondance inutile d'information.

Il faut également noter que les listes utilisées pour cette structure peuvent être de simples tableaux (à condition que le graphe soit statique, i.e. pas d'ajout ou de suppression d'arcs ou de noeuds), des listes chaînées (à condition de limiter la suppression d'arcs ou de noeuds) ou bien des structures arborescentes (qui permettent efficacement l'ajout ou la suppression d'arcs ou de noeuds).

L'algorithme que nous présentons ici est basé sur le lemme de Minty (cf. [Minty61]). Minty propose d'associer une couleur à chaque arc d'un graphe parmi quatre (généralement vert, noir, bleu et rouge). Il démontre qu'une recherche basée sur une telle coloration conduit toujours à un cycle ou à un cocycle avec des propriétés bien particulières. L'intérêt de l'algorithme est que suivant la manière de colorer les arcs, on obtient des algorithmes pour rechercher différents types de cycle ou de cocycle.

Soit un graphe avec les arcs colorés en vert, noir, bleu et rouge. Minty a démontré qu'une et une seule des propositions suivantes est vérifiée pour tout arc .

• L'arc appartient à un cycle constitué (excepté ) seulement d'arcs verts, noirs et bleus avec les arcs noirs orientés dans la même direction que et les arcs bleus dans la direction opposée. Les arcs verts peuvent être dans n'importe quel sens.

• L'arc appartient à un cocycle constitué (excepté ) seulement d'arcs rouges, noirs et bleus avec les arcs noirs orientés dans la même direction que et les arcs bleus dans la direction opposée. Les arcs rouges peuvent être dans n'importe quel sens.

La preuve de ce lemme peut être faite par la justification de l'algorithme de recherche d'un tel cycle ou cocycle exposé dans la section qui suit.

Nous exposons ici une méthode pour trouver un cycle ou un cocycle d'après la coloration de Minty pour un arc donné du graphe . L'algorithme 2.1 parcours et marque les noeuds de un par un en partant de . Deux ensembles de noeuds et sont nécessaires pour cette opération. contient les noeuds marqués pendant le parcours et contient les noeuds marqués pendant le parcours susceptibles de conduire à des noeuds non marqués.

Le parcours d'un noeud à l'autre se fait en utilisant les arcs verts dans n'importe quel sens, les arcs noirs dans le sens direct et les arcs bleus dans le sens indirect. Si le noeud est atteint, alors il existe une chaîne de à et donc un cycle contenant qui correspond à la première proposition du lemme. L'algorithme nécessite alors une fonction qui indique pour chaque noeud marqué l'arc qui a permis d'y accéder, cela permettra de construire le cycle détecté.

Si ne peut pas être marqué, est le cocycle qui sépare des noeuds non marqués de . Ce cocycle correspond à la deuxième proposition du lemme. En effet, si contenait un arc vert, alors un autre noeud aurait dû être marqué. De manière similaire, si contenait un arc noir dans le sens opposé à dans le cocycle ou un arc bleu dans le même sens que dans le cocycle, alors un autre noeud aurait dû être marqué.

Algorithme 2.1: cycleMinty(arc ,graphe ,cycle ,cocycle )
  ;
  ;
  ;
 
 tant que et faire
  choisir ;
   ;
 
  pour tout tel que est vert ou noir et faire
    ;
    ;
    ;
  fin pour;
 
  pour tout tel que est vert ou bleu et faire
    ;
    ;
    ;
  fin pour;
 fin tant que;
 
 si alors /* Cocycle trouvé. */
  construire le cocycle de ;
 sinon /* Cycle trouvé. */
  construire le cycle en utilisant la fonction à partir de ;
 fin si;
fin algorithme;

Enfin, les deux propositions du lemme ne peuvent pas être vraies en même temps. Pour le prouver, supposons les deux propositions vérifiées. L'arc appartient donc à la fois au cycle et au cocycle. Dans le cocycle, il existe forcément un arc qui appartient au cycle comme (en effet, le cycle contenant doit forcément repasser dans le cocycle). Cet arc ne peut être ni rouge, ni vert. En outre, s'il était bleu, il serait opposé à dans le cycle mais aussi dans le cocycle, ce qui est impossible puisque deux arcs de même sens dans un cycle sont forcément opposés dans un cocycle. Pour la même raison, ne peut pas être noir. D'où la contradiction.

Cet algorithme étant un simple parcours de graphe, il permet de détecter un cycle ou un cocycle de Minty en opérations.

L'algorithme de Minty est très intéressant puisqu'en choisissant judicieusement la coloration des arcs, il permet la recherche de différents types de cycle ou de cocycle. En général, il permet la détection d'un cycle ou d'un cocycle dont les propriétés peuvent s'exprimer indépendamment sur chaque arc. Par contre une propriété globale à tout le cycle ou le cocycle, comme par exemple la longueur d'un cycle, ne peut pas être traduite en termes de couleurs sur les arcs. Voici quelques colorations simples qui permettent les recherches les plus classiques.

• Colorer tous les arcs en vert permet de rechercher un cycle contenant un arc donné (tous les arcs peuvent être employés pour trouver une chaîne de à ).

• Colorer tous les arcs en rouge permet de déterminer le cocycle du noeud source d'un arc donné (aucun arc ne peut être employé pour trouver une chaîne de à ).

• Colorer tous les arcs en noir permet de rechercher un circuit contenant un arc donné (si un cycle est trouvé, tous ses arcs sont noirs et donc dans le même sens que ). Si un tel circuit n'existe pas, alors un cocircuit est trouvé contenant l'arc (si un cocycle est trouvé, tous ces arcs sont noirs et donc dans le même sens que ).

Dans la suite du document, les chaînes, les chemins, les cycles et les cocycles seront toujours considérés élémentaires. Nous rappelons également que nous utiliserons sans le préciser la représentation vectorielle des fonctions quand cela s'avérera nécessaire.

Nous supposons également que les graphes que nous étudions sont toujours connexes (s'ils ne le sont pas, il suffit de considérer chaque composante connexe séparément) et peuvent être des multigraphes (comme nous le verrons dans une section suivante, il est dans la nature même des graphes représentant des problèmes de synchronisation hypermédia de posséder des arcs multiples).

Le flot est une notion très importante en théorie des graphes puisqu'elle permet de représenter des flux (e.g. l'information dans un réseau de télécommunication, les passagers dans un réseau de transport, les matières et les produits dans une chaîne de production...). De nombreux problèmes autour de ce concept ont été modélisés et étudiés, et par conséquent de nombreuses méthodes de résolution et d'importants résultats théoriques sont disponibles. Comme nous l'expliquons dans la seconde partie du document, pour résoudre des problèmes de tension, nous nous sommes fortement inspirés d'algorithmes conçus pour des problèmes de flot. En outre, la relation très particulière qui lie le flot et la tension est telle que la plupart des méthodes pour résoudre les problèmes de flot (respectivement de tension) manipulent la tension (respectivement le flot). Il semble donc important de rappeler ici quelques définitions et propriétés élémentaires sur le flot.

On appelle flot une fonction qui associe à chaque arc de une valeur (réelle ou entière). La particularité de cette fonction est que, pour chaque noeud de , on a la propriété suivante, appelée conservation des flots.

(2.1)

Autrement dit, est un flot si et seulement si, pour chaque noeud, la somme des flots sur les arcs entrants est égale à la somme des flots sur les arcs sortants. Par exemple, si représente un circuit électrique, l'intensité du courant est un flot sur . Ainsi, si on note la matrice d'incidence de , la formule 2.1 peut s'écrire:

(2.2)

Voici quelques propriétés élémentaires sur le flot très simplement vérifiables.

• Si est un flot et un réel, alors est un flot.

• Si et sont des flots, alors est un flot.

• Le seul flot possible sur un arbre est le flot .

• Le vecteur qui représente un cycle est un flot (il est très facile de vérifier la conservation des flots).

On dit que vecteurs , ... de sont dépendants s'il existe coefficients non tous nuls , ... dans tels que:

(2.3)

A l'inverse, si la relation 2.3 n'est vérifiée que pour tous les nuls, alors les vecteurs , ... sont dits indépendants.

Une base de vecteurs est un ensemble de vecteurs indépendants tel que tout vecteur de est une combinaison linéaire des vecteurs de la base, i.e. pour tout vecteur il existe des coefficients , ... tels que:

(2.4)

Les cycles pouvant être considérés comme des vecteurs, il est possible de construire une base de cycles. Nous rappelons ici une manière simple d'obtenir une telle base. Considérons un arbre recouvrant du graphe . Il ne contient pas de cycles, mais tout ajout dans l'arbre d'un arc de (i.e. un arc qui n'est pas déjà dans ) engendre un cycle . Si on considère l'ensemble des cycles engendré en ajoutant séparément chaque arc de dans l'arbre , on obtient un ensemble de cycles indépendants (car chaque cycle possède un arc qu'aucun autre ne possède, c'est ). Il faut s'assurer maintenant que tout cycle de est une combinaison linéaire des cycles de .

Considérons un flot . Soit . est une combinaison linéaire de flots donc un flot. La différence est également un flot. Or, pour tout arc de , puisque l'arc n'apparaît que dans le cycle . Le flot étant nul pour tout arc n'appartenant pas à , il représente donc un flot défini strictement sur , or tout flot sur un arbre est nul donc .

En conclusion, tout flot est une combinaison linéaire de la base . Un cycle pouvant être considéré comme un flot, tout cycle est une combinaison linéaire de . On remarque également que la base contient cycles (car possède arcs). Enfin, l'algorithme pour construire est détaillé dans l'annexe.

Nous présentons maintenant la notion de tension dont nous verrons par la suite la pertinence pour modéliser des problèmes de synchronisation hypermédia. La plupart des résultats théoriques liés à ce concept proviennent du développement de méthodes de résolution pour des problèmes de flot. L'utilisation de la tension pour modéliser des problèmes dans les graphes est beaucoup moins répandue que pour le flot, cependant il existe de nombreux problèmes que la tension peut représenter (e.g. [Rockafellar84]). Notamment dans le domaine de la planification, la tension peut être assimilée à une durée comme nous le verrons à la section suivante. Nous rappelons ici quelques définitions et propriétés élémentaires sur la tension (issues de [Berge62]) utiles pour notre étude.

On désigne par potentiel une fonction qui associe à chaque noeud de une valeur (entière ou réelle). Associée à ce potentiel, on peut définir une fonction appelée tension qui attribue à chaque arc de une valeur de la manière suivante.

(2.5)

Une fonction est donc une tension s'il est possible de lui associer un potentiel. Ces notions de tension et de potentiel peuvent être comparées à celles d'un circuit électrique. Si on note la matrice d'incidence de , la définition 2.5 de la tension peut se traduire:

(2.6)

Voici quelques propriétés élémentaires sur la tension très simplement vérifiables.

• Si est une tension et un réel, alors est une tension.

• Si et sont des tensions, alors est une tension.

• Toute fonction qui associe à chaque arc d'un arbre une valeur est une tension.

• Le vecteur qui représente un cocycle est une tension (il est très facile d'y associer un potentiel).

Tout vecteur tension et tout vecteur flot sur un graphe sont orthogonaux, i.e. le produit scalaire (d'après la définition 2.6, il existe un potentiel tel que où est la matrice d'incidence de , donc ). Il est alors possible d'en déduire une nouvelle définition de la tension.

(2.7)

Preuve:
() est orthogonale à tout flot sur et donc en particulier à tout cycle (le vecteur cycle représentant un flot).
() Si l'égalité est vérifiée, un potentiel peut être associé à . Dans le cas contraire, cela signifierait qu'il existe pour un arc une chaîne de à pour laquelle . Or si l'on considère le cycle formé de et de , on doit avoir , d'où la contradiction.

Il n'est pas nécessaire de vérifier l'égalité pour tous les cycles du graphe pour confirmer une tension. En effet, si l'égalité est vérifiée pour une base de cycles , i.e. , alors toute combinaison linéaire, donc tout cycle , vérifie . La définition suivante suffit donc à caractériser une tension.

(2.8)

De manière analogue aux cycles, nous rappelons ici une manière simple d'obtenir une base de cocycles. Considérons un arbre recouvrant du graphe . En supprimant un arc de l'arbre, on fait apparaître deux composantes connexes. Notons la composante qui contient le noeud source de et notons le cocycle de dans le graphe . Si on considère l'ensemble des cocycles engendré en supprimant séparément chaque arc de , on obtient un ensemble de cocycles indépendants (car chaque cocycle possède un arc qu'aucun autre ne possède, c'est ). Il faut s'assurer maintenant que tout cocycle de est une combinaison linéaire des cocycles de .

Considérons une tension . Soit . est une combinaison linéaire de tensions donc une tension. La différence est également une tension. Or, pour tout arc de , puisque l'arc n'apparaît que dans le cocycle . La tension étant nulle pour tout arc de , tous les noeuds de l'arbre et donc du graphe ont le même potentiel. Donc .

En conclusion, toute tension est une combinaison linéaire de la base . Un cocycle pouvant être considéré comme une tension, tout cocycle est une combinaison linéaire de . On remarque également que la base contient cocycles (car possède arcs).

Un graphe est dit temporel lorsque ses noeuds représentent des événements et ses arcs des contraintes de précédence entre deux noeuds, i.e. l'arc signifie que l'événement modélisé par doit se produire avant l'événement modélisé par .

Un graphe temporel est également accompagné d'un vecteur , appelé durée, qui associe à chaque arc une durée et d'un vecteur , appelé date, qui associe à chaque noeud une date . Un graphe temporel peut également être muni d'un vecteur , appelé capacité, qui associe à chaque arc un ensemble , indiquant les valeurs autorisées pour la durée .

Figure 2.7: Modélisation d'un simple objet multimédia par un graphe temporel.

Un objet multimédia de durée idéale et d'ensemble de tolérance sera donc représenté dans un graphe temporel par ses événements de début et de fin reliés par un arc indiquant la relation de précédence entre et (cf. figure 2.7) et portant toutes les informations associées à l'objet telles que la durée idéale et l'ensemble de tolérance .

En outre, un graphe temporel doit posséder un seul noeud source et un seul noeud puits , chacun représentant respectivement les événements de début et de fin du scénario complet modélisé. Il est possible de fixer la date de l'événement à , la date de représentera ainsi la durée totale de présentation du scénario. Et si l'on connaît le vecteur durée, on peut en déduire le vecteur date, et réciproquement.

A partir du principe qu'un arc représente une contrainte de précédence entre deux objets multimédia, la figure 2.8b modélise sous forme de graphe temporel un exemple de scénario illustré par la figure 2.8a (une flèche entre deux objets signifie que la fin de l'objet source coïncide avec le début de l'objet cible). Des simplifications peuvent être apportées à ce graphe temporel: deux événements liés par une contrainte de précédence de capacité signifient qu'ils sont confondus (cf. figure 2.8c).

Figure 2.8: Un exemple de modélisation d'un scénario par un graphe temporel.

Il est relativement simple d'exprimer les relations d'Allen par un graphe temporel (cf. figure 2.9). Nous ne prenons pas en compte dans cette représentation les durées et les événements imprévisibles. Nous supposons que la planification doit établir une durée pour tous les objets multimédia et une date relative au début de la présentation du document pour tous les événements. En outre, la disjonction qui est préconisée sur les relations d'Allen n'est pas toujours représentable. Soulignons deux disjonctions modélisables importantes, nous les nommons et . signifie que les objets et démarrent en même temps, ce qui s'exprime par . signifie de façon similaire que et se terminent en même temps, et s'exprime par . Comme le souligne [Allen91], les possibilités de disjonctions entre deux relations d'Allen sont au nombre de , mais il explique également que seulement sont modélisables par une représentation sous forme d'événements comme la nôtre.

Figure 2.9: Modélisation des relations d'Allen par un graphe temporel.

Nous allons montrer ici que les durées portées par les arcs correspondent à la notion de tension définie à la section 2.2. Une fois établi le fait que les problèmes que nous tentons de résoudre sont des problèmes de tension, nous en exposons les deux principaux, la tension compatible et la tension de coût minimal, qui modélisent les problématiques de synchronisation hypermédia soulignées au chapitre 1.

Supposons un graphe muni d'un vecteur durée et d'un vecteur date . La durée d'une chaîne entre deux noeuds et est définie par la somme . Pour un chemin du noeud au noeud , sa durée se résume à . Notons qu'un chemin dans un graphe temporel représente une succession d'objets multimédia et la durée du chemin représente la durée totale de présentation de ces objets. La satisfaction des contraintes temporelles par une planification (i.e. un vecteur durée ou un vecteur date sur ) peut être exprimée de la manière suivante: pour chaque paire de noeuds et , tous les chemins entre et doivent avoir la même durée.

En d'autres termes, telle que, pour tout chemin de à , . Tentons alors de prouver la propriété suivante.

Soit un graphe et un vecteur durée . telle que, pour tout chemin de à , , si et seulement si est une tension.

(2.9)

Preuve:
() Soit l'ensemble des cycles de . est une tension dans , donc , . Ainsi, un cycle formé de deux chemins et de à , e.g. et , vérifie . Donc deux chemins de mêmes extrémités sont de même durée.
() Notons la durée des chemins de la source au noeud (tous les chemins de mêmes extrémités sont de même durée). Soit un cycle de , considérons et deux noeuds consécutifs dans ce cycle. Il y a deux cas possibles:
- L'arc . De la définition d'un graphe temporel, il est toujours possible de trouver un chemin de à avec la durée . Le chemin de à passant par en utilisant l'arc du cycle est également de durée , et vaut aussi (cf. figure 2.10). D'après l'hypothèse de départ, .
- L'arc . De manière analogue au premier cas, on trouve que .
En résumé, on obtient l'égalité : .
Numérotons les arcs du cycle consécutivement . En sommant les égalités , on obtient: . Or les noeuds et sont confondus, donc . Le vecteur est donc une tension.

Figure 2.10: Illustration de la preuve.

En résumé, le vecteur durée est une tension. En outre, pour tout arc , la durée , le vecteur date est donc un potentiel. Etudions maintenant la relation entre certains problèmes de tension et la synchronisation hypermédia.

On dit qu'une tension d'un graphe est compatible (ou réalisable) avec une capacité si et seulement si, pour tout arc , . Le problème de la tension compatible consiste à déterminer une telle tension. Dans le contexte de la synchronisation hypermédia, cela signifie chercher une durée pour chaque objet hypermédia qui soit dans l'ensemble de tolérance associé. La résolution de ce problème permet également de répondre à la question: est-il possible de présenter le document en secondes ? Il suffit pour cela d'ajouter un arc de capacité entre le noeud source et le noeud puits du graphe, et de tenter de déterminer une tension compatible sur ce nouveau graphe.

Au cours de notre étude sur des méthodes de résolution de ce problème de réalisabilité, nous nous intéresserons au problème de la tension maximale (ou minimale). Il s'agit, pour un arc donné d'un graphe muni d'une capacité , de trouver la tension maximale (ou minimale) qu'il peut atteindre, restant compatible avec . Là aussi, en ajoutant un arc de capacité entre le noeud source et le noeud puits du graphe, il est possible de répondre à la question: quelle est la durée maximale (ou minimale) de présentation d'un document hypermédia ? Il suffit pour cela de déterminer la tension maximale (ou minimale) du nouvel arc.

L'un des principaux problèmes liés à la synchronisation hypermédia est tout de même de déterminer une planification de la meilleure qualité possible. Mais avant de tenter une résolution, il faut être capable de formaliser la notion de qualité d'une planification. Pour cela, nous avons choisi d'attribuer un coût (pour l'instant nous le supposerons quelconque) pour chaque arc en fonction de sa tension. Ce coût étant naturellement le plus faible lorsque la tension de l'arc est égale à sa tension idéale (i.e. sa durée idéale). Nous discutons à la section suivante des différents types de fonction de coût pertinents pour la synchronisation hypermédia.

En d'autres termes, pour chaque arc , on définit un coût sur un graphe comme étant un vecteur , qui attribue à chaque arc une fonction de coût . Le problème d'optimisation qui se pose alors est de trouver une tension compatible qui minimise la somme totale des coûts, i.e. . Ce problème est appelé le problème de la tension de coût minimal.

Comme il l'a déjà été souligné, afin de déterminer la meilleure planification d'un document hypermédia, il est nécessaire d'en mesurer la qualité. Pour cela, nous retenons la solution qui consiste à attribuer à chaque arc une fonction de coût dépendante de la valeur de la tension , telle que , i.e. le coût de la tension est nul si celle-ci est à sa valeur idéale (i.e. l'objet multimédia est planifié à sa durée idéale). Naturellement, ce coût augmente à mesure que la tension s'éloigne de . A travers la littérature, nous avons constaté trois types de coût pertinents pour représenter la qualité de la planification d'un document hypermédia.

La première idée consiste à affecter à un arc un coût proportionnel à l'écart entre la tension et sa tension idéale . Ce type de coût a été proposé et traité dans [Buchanan93b] et [Kim95]. Alors que [Kim95] propose un coût unitaire identique selon que la tension soit inférieure ou supérieure à la durée idéale (cf. figure 2.11a), [Buchanan93b] propose de différencier les deux cas (cf. figure 2.11b). [Kim95] considère même simplement la fonction . En résumé, ces approches similaires expriment la fonction de coût d'un arc par un coût unitaire de diminution de la tension et un coût unitaire d'augmentation de la tension d'un arc . Cette fonction s'écrit de la manière suivante.

La tension optimale obtenue avec le type de coût présenté précédemment peut produire une inégalité entre les objets multimédia (cf. [Kim95]). Autrement dit, certains objets peuvent subir une importante déformation alors que d'autres n'en subissent qu'une légère.

Figure 2.11: Exemples de coûts convexes pour mesurer la qualité d'une planification hypermédia.

Afin d'équilibrer ces altérations, i.e. que chacun est à peu près la même déformation, [Kim95] propose une fonction de la forme (cf. figure 2.11c). Nous nous intéresserons donc par la suite à déterminer une tension optimale avec des fonctions de coût convexes dérivables quelconques.

Un dernier type de coût présenté dans [Medina04] semble également illustrer la qualité d'un document hypermédia. La déformation de la durée d'un objet multimédia peut entraîner un temps d'exécution important au moment de la présentation du document. Une mesure de qualité qui intéresse donc les auteurs de documents hypermédia est simplement le nombre d'objets qui ne sont pas planifiés à leur durée idéale. Autrement dit, la fonction de coût est de la forme suivante.

Nous avons exposé ici une modélisation possible des relations temporelles d'objets multimédia à synchroniser. Nous avons supposé les ensembles de tolérance quelconques. Dans notre étude, nous nous limiterons pour l'instant à des intervalles de tolérance continu (pour tout arc , un intervalle ), simplement parce que les problèmes sont plus faciles à aborder dans le domaine continu que dans le domaine discret, où la combinatoire peut rapidement devenir trop importante. Nous choisissons également d'aborder l'étude du problème d'optimisation avec des fonctions convexes linéaires par morceaux ou simplement dérivables. Nous n'étudierons pas pour l'instant la minimisation du nombre d'objets touchés par une déformation dans une planification hypermédia. Cette modélisation est également de nature discrète.