Force d'un graphe
De Wikipedia, l'encyclopédie encyclopedia
En théorie des graphes, la force d'un graphe (strength en anglais) non orienté est le plus petit rapport entre le nombre d'arêtes supprimées et le nombre de composantes créées dans une décomposition du graphe.
Faits en bref
Force d'un graphe (exemple) | |
Un graphe de force 2 : le graphe est décomposé en trois parties avec un total de 4 arêtes entre les composantes, ce qui donne le rapport 4/(3-1)=2. | |
modifier |
Fermer