CONNEXION
  • RetourJeux
    • Sorties
    • Hit Parade
    • Les + populaires
    • Les + attendus
    • Soluces
    • Tous les Jeux
    • Gaming
  • RetourActu Gaming
    • News
    • Astuces
    • Tests
    • Previews
    • Toute l'actu gaming
  • RetourBons plans
    • Bons plans
    • Bons plans Smartphone
    • Bons plans Hardware
    • Bons plans Image et Son
    • Bons plans Amazon
    • Bons plans Cdiscount
    • Bons plans Decathlon
    • Bons plans Fnac
    • Tous les Bons plans
  • RetourJVTech
    • Actus High-Tech
    • Intelligence Artificielle
    • Smartphones
    • Mobilité urbaine
    • Hardware
    • Image et son
    • Tutoriels
    • Tests produits High-Tech
    • Guides d'achat High-Tech
    • JVTech
  • RetourCulture
    • Actus Culture
    • Culture
  • RetourVidéos
    • A la une
    • Gaming Live
    • Vidéos Tests
    • Vidéos Previews
    • Gameplay
    • Trailers
    • Chroniques
    • Replay Web TV
    • Toutes les vidéos
  • RetourForums
    • Hardware PC
    • PS5
    • Switch 2
    • Xbox Series
    • Switch
    • Pokemon pocket
    • FC 25 Ultimate Team
    • League of Legends
    • Tous les Forums
  • PC
  • PS5
  • Xbox Series
  • Switch 2
  • PS4
  • One
  • Switch
  • iOS
  • Android
  • MMO
  • RPG
  • FPS
En ce moment Genshin Impact Valhalla Breath of the wild Animal Crossing GTA 5 Red dead 2
Liste des sujets

Problème algorithmique / théorie des graphes

Jean_Python
Jean_Python
Niveau 10
27 avril 2021 à 21:52:53

J'ai un graphe G( V, E, w) non orienté et pondéré, avec w: E-> |R+

et je cherche H un sous-graphe de G tel que:
- les nœuds de H sont de degré 0 ou 1
- la somme des poids w des arêtes de H est maximale

Pas de contrainte sur son unicité, du moment que j'ai un sous-graphe qui correspond je suis content.

Je vois bien comment faire ça avec des méthodes classiques (backtracking ou autre), mais est-ce qu'il n’existerait pas déjà un algo sur étagère pour faire ça directement ? :noel:

Message édité le 27 avril 2021 à 21:55:22 par Jean_Python
Sous forums
  • Religion
La vidéo du moment