23 November 2012, 10h30 - 23 November 2012, 11h30 Salle/Bat : 475/PCRI-N
Contact : rafael.castro@lri.fr

Activités de recherche :

Résumé :

Consider an undirected and connected graph $G=(V,E)$ of node set $V$ and edge set $E$, with $c_{uv}>0$ being the energy associated with an edge $uv in E$. Let $T$ be a pending spanning tree of $G$ rooted at a distinguished node $kin V$, where each node $vin V-{k}$ accumulates the information of the energy of the edges in the path from the root node $k$ until $v$ in $T$. We say that two nodes $u$ and $v$ present stable potential equilibrium in $T$ if any edge $uv in E$ not in $T$ have greater energy than the edge with larger energy in the direct path from $u$ to $v$ in $T$. Two nodes $u$ and $v$, with $uv in E$ and $uv notin T$, have instable potential equilibrium in $T$ if the paths from $u$ and $v$ to their first common ancestor in their paths to $k$ contain exactly (each path) the same edge energies having larger values than the one of $uv$ and all the remaining edges in the direct
path from $u$ to $v$ in $T$ have not greater energy than $c_{uv}$. A
$k$-rooted pending spanning tree of $G$ with equilibrated potentials is a crystal tree. In this work we present some properties of crystal trees and discuss their relations/differences with respect to spanning trees of minimum energy and $k$-rooted shortest path trees. We introduce a potential function allowing to describe the complete set of crystal trees of a graph $G$ as solutions of a polynomially bounded system of linear inequalities.