[PYTHON] Optimisation de combinaison - problème typique - problème de couverture de vertex minimum

Problème typique et méthode d'exécution

Problème de couverture minimale des sommets

Trouvez celui avec la plus petite somme de poids dans la couverture de vertex $ C $ dans le graphe non orienté $ G = (V, E) $.

Méthode d'exécution

usage

Signature: min_node_cover(g, weight='weight')
Docstring:
Problème de couverture minimale des sommets
contribution
    g:Graphique
    weight:Caractère d'attribut de poids
production
Liste des sommets

python

#Données CSV
import pandas as pd, networkx as nx, matplotlib.pyplot as plt
from ortoolpy import graph_from_table, networkx_draw, min_node_cover
tbn = pd.read_csv('data/node0.csv')
tbe = pd.read_csv('data/edge0.csv')
g = graph_from_table(tbn, tbe)[0]
t = min_node_cover(g)
pos = networkx_draw(g, node_color='white')
nx.draw_networkx_nodes(g, pos, nodelist=t)
plt.show()
print(t)

résultat

[0, 2, 3, 5]

python

#Données aléatoires
import networkx as nx, matplotlib.pyplot as plt
from ortoolpy import min_node_cover, networkx_draw
g = nx.random_graphs.fast_gnp_random_graph(10, 0.3, 1)
l = min_node_cover(g)
pos = networkx_draw(g, nx.spring_layout(g), node_color='white')
nx.draw_networkx_nodes(g, pos, nodelist=l)
plt.show()

Les données

• data/node0.csv
• data/edge0.csv