Khalil
Webmaster
Messages : 143
Date d'inscription : 20/12/2008
Age : 36
 | | Sujet: Théorie des graphes Ven 5 Juin - 17:38 | |
| Théorie des graphes:
La théorie des graphes est une branche commune à l'informatique et aux mathématiques étudiant les graphes et les objets qui lui sont propres, comme par exemple les chemins. Le concept de graphe, à ne pas confondre avec le graphe d'une fonction, permet d'étudier les propriétés de certaines structures comme les réseaux (réseau social, réseau informatique, etc.) ou, plus largement, les relations binaires. Les algorithmes de la théorie des graphes ont ainsi de nombreuses applications importantes. Enfin, la nature particulière des relations entre les objets de cette théorie, ou les propriétés structurelles qu'elle révèle, ont influencé considérablement l'optimisation combinatoire.
Définition de graphe et vocabulaire:
Intuitivement, un graphe est un ensemble de points, dont certaines paires sont directement reliées par un lien. Ces liens peuvent être orientés, c'est-à-dire qu'un lien entre deux points u et v relie soit u vers v, soit v vers u : dans ce cas, le graphe est dit orienté. Sinon, les liens sont symétriques, et le graphe est non-orienté.
Dans la littérature récente de la théorie des graphes, les points sont appelés les sommets (en référence aux polyèdres) ou les nœuds (en références à la loi des nœuds). Les liens sont appelés arêtes dans les graphes non-orienté et arcs dans un graphe orienté.
L'ensemble des sommets est le plus souvent noté V, tandis que E désigne l'ensemble des arêtes. Dans le cas général, un graphe peut avoir des arêtes multiples, c'est-à-dire que plusieurs arêtes différentes relient la même paire de points. De plus, un lien peut être une boucle, c'est-à-dire ne relier qu'un point à lui-même. Un graphe est simple si il n'a ni liens multiples ni boucles, il peut alors être défini simplement par un couple G = (V,E), où E est un ensemble de paires d'éléments de V. Dans le cas d'un graphe simple orienté, E est un ensemble de couples d'éléments de V. Notons qu'un graphe sans arête multiple peut être représenté par une relation binaire, qui est symétrique si le graphe est non-orienté.
Pour définir un graphe général, il faut une fonction d'incidence γ qui associe à chaque arête une paire de sommets (ou un couple en cas orienté). Ainsi, un graphe est un triplet G = (V,E,γ) avec \gamma : E \rightarrow V \times V. Toutefois l'usage veut que l'on note simplement G = (V,E), sachant que ce n'est parfaitement rigoureux que pour les graphes simples.
Flots dans les réseaux:
Les Allemands Franz Ernst Neumann et Jacobi, respectivement physicien et mathématicien, fondèrent en 1834 une série de séminaires. Le physicien allemand Gustav Kirchhoff était un des étudiants participant au séminaire entre 1843 et 1846, et il étendit le travail de Georg Ohm pour établir en 1845 les Lois de Kirchhoff exprimant la conservation de l'énergie et de la charge dans un circuit électrique. En particulier, sa loi des nœuds stipule que la somme des intensités des courants entrant dans un nœud est égale à celle qui en sort. Un circuit électrique peut se voir comme un graphe, dans lequel les sommets sont les nœuds du circuit, et les arêtes correspondent aux connexions physiques entre ces nœuds. Pour modéliser les courants traversant le circuit, on considère que chaque arête peut-être traversée par un flot. Ceci offre de nombreuses analogies, par exemple à l'écoulement d'un liquide comme l'eau à travers un réseau de canaux[B 1], ou la circulation dans un réseau routier. Comme stipulé par la loi des nœuds, le flot à un sommet est conservé, ou identique à l'entrée comme à la sortie; par exemple, l'eau qui entre dans un canal ne disparaît pas et le canal n'en fabrique pas, donc il y a autant d'eau en sortie qu'en entrée. De plus, une arête a une limite de capacité, tout comme un canal peut transporter une certaine quantité maximale d'eau. Si l'on ajoute que le flot démarre à un certain sommet (la source) et qu'il se termine à un autre (le puits), on obtient alors les principes fondamentaux de l'étude des flots dans un graphe.
Si on considère que la source est un champ pétrolifère et que le puits est la raffinerie où on l'écoule, alors on souhaite régler les vannes de façon à avoir le meilleur débit possible de la source vers le puits. En d'autres mots, on cherche à avoir une utilisation aussi efficace que possible de la capacité de chacune des arêtes, ce qui est le problème de flot maximum. Supposons que l'on coupe le graphe en deux parties, telle que la source est dans l'une et le puits est dans l'autre. Chaque flot doit passer entre les deux parties, et est donc limité par la capacité maximale qu'une partie peut envoyer à l'autre. Trouver la coupe avec la plus petite capacité indique donc l'endroit où le réseau est le plus limité, ce qui revient à établir le flot maximal qui peut le traverser[B 2]. Ce théorème est appelé flot-max/coupe-min et fut établi en 1956.
L’étude des flots réseaux se généralise de plusieurs façons. La recherche d'un maximum, ici dans le cas du flot, est un problème d'optimisation, qui est la branche des mathématiques consistant à optimiser (i.e. trouver un minimum ou maximum) une fonction sous certaines contraintes. Un flot réseau est soumis à trois contraintes[B 3] : la limite de capacité sur chaque arête, la création d'un flot non nul entre la source et le puits (i.e. la source crée un flot), et l'égalité du flot en entrée/sortie pour tout sommet autre que la source et les puits (i.e. ils ne consomment ni ne génèrent une partie du flot). Ces contraintes étant linéaires, le problème d'un flot réseau fait partie de la programmation linéaire. Il est également possible de rajouter d'autres variables au problème pour prendre en compte davantage de situations : on peut ainsi avoir plusieurs sources et puits, une capacité minimale sur chaque arrête, un coût lorsqu'on utilise une arrête, ou une amplification du flot passant par une arête.
  
Graphes et algèbre linéaire:
Tout graphe G = (V,E) peut être représenté par une matrice. Les relations entre arêtes et sommets, appelées les relations d'incidence, sont toutes représentées par la matrice d'incidence du graphe. Les relations d'adjacences (si deux sommets sont reliés par une arête ils sont adjacents) sont représentés par sa matrice d'adjacence. Elle est définie par
  
De nombreuses informations d'un graphe peuvent-être représentées par une matrice. Par exemple, la matrice des degrés D est une matrice diagonale où les éléments Dii correspondent au nombre de connexions du sommet i, c'est-à-dire à son degré. En utilisant cette matrice et la précédente, on peut également définir la matrice laplacienne L = D − A; on obtient sa forme normalisée L' par L' = D − 1 / 2LD − 1 / 2 = I − D − 1 / 2AD − 1 / 2, où I dénote la matrice identité, ou on peut aussi l'obtenir directement par chacun de ses éléments :
\ell_{i,j}:= \begin{cases} 1 & \mbox{si}\ i = j\ \mbox{et}\ \deg(v_i) \neq 0\\ -\frac{1}{\sqrt{\deg(v_i)\deg(v_j)}} & \mbox{si}\ i \neq j\ \mbox{et}\ v_i \text{ est adjacent a } v_j \\ 0 & \text{sinon}. \end{cases}
Ces représentations dépendent de la façon dont les sommets du graphe sont étiquetés. Imaginons que l'on garde la même structure que dans l'exemple ci-dessus et que l'on inverse les étiquettes 1 et 6 : on inverse alors les colonnes 1 et 6 de la matrice d'adjacence. Il existe en revanche des quantités qui ne dépendent pas de la façon dont on étiquette les sommets, tels que le degré minimal/maximal/moyen du graphe. Ces quantités sont des invariants du graphe : elles ne changent pas selon la numérotation. Tandis qu'une matrice d'adjacence ou laplacienne varie, son spectre, c'est-à-dire l'ensemble de ses valeurs propres \lambda_0 \le \lambda_1 \le \cdots \le \lambda_{n-1}, est un invariant. L'étude du rapport entre les spectres et les propriétés d'un graphe est le sujet de la théorie spectrale[D 3]; parmi les rapports intéressants, le spectre donne des renseignements sur le nombre chromatique, le nombre de composantes connexes et les cycles du graphe.
| |
|
