Problème de graphe.
nico
-
dominool -
dominool -
Bonsoir tout le monde,
je souhaite modéliser un réseau de communication par un graphe non orienté où chaque sommets modélisent les ordinateurs et les arrêtes les liens physique entre les ordinateurs. Les liens sont de deux types: sécurises et non-sécurisés.
Mon problème est : si je choisit deux sommets A et B, (deux pc ) est ce qu'il existe une chaine sécurisée entre ces deux dans le réseau? si oui quelle serait sa longueur minimale (en nombre de lien.
Et aussi comment déterminer un arbre couvrant qui utilise un nombre mini d'arêtes non-sécurisées.
Merci pour vous réponses.
nico
je souhaite modéliser un réseau de communication par un graphe non orienté où chaque sommets modélisent les ordinateurs et les arrêtes les liens physique entre les ordinateurs. Les liens sont de deux types: sécurises et non-sécurisés.
Mon problème est : si je choisit deux sommets A et B, (deux pc ) est ce qu'il existe une chaine sécurisée entre ces deux dans le réseau? si oui quelle serait sa longueur minimale (en nombre de lien.
Et aussi comment déterminer un arbre couvrant qui utilise un nombre mini d'arêtes non-sécurisées.
Merci pour vous réponses.
nico
A voir également:
- Problème de graphe.
- Graphe easy - Télécharger - Études & Formations
- Graphe excel - Guide
- Logiciel graphe - Télécharger - Études & Formations
- Tracage d'un graphe de nuage de point 3D ✓ - Forum Excel
- Excel: Réaliser un graphe de cause à effet - Forum Excel
1 réponse
Salut Nico,
pour ta deuxième question ce qu'il faut se dire est que un arbre couvrant de ce graphe est un sous-ensemble qui est un arbre et qui connecte tous les sommets ensemble.
Un graphe peut comporter plusieurs arbres couvrants différents. On peut associer un poids à chaque arête, ce qui est un nombre qui représente le coût de cette arête, et prendre la somme des poids des arêtes de l'arbre couvrant. Un arbre couvrant de poids minimal est un arbre couvrant dont le poids est plus petit ou égal à celui de tous les autres arbres couvrants du graphe.
pour ta deuxième question ce qu'il faut se dire est que un arbre couvrant de ce graphe est un sous-ensemble qui est un arbre et qui connecte tous les sommets ensemble.
Un graphe peut comporter plusieurs arbres couvrants différents. On peut associer un poids à chaque arête, ce qui est un nombre qui représente le coût de cette arête, et prendre la somme des poids des arêtes de l'arbre couvrant. Un arbre couvrant de poids minimal est un arbre couvrant dont le poids est plus petit ou égal à celui de tous les autres arbres couvrants du graphe.
