Niveau algorithmique

Maximum de sommet de degree n

Posté par
Vantin 03-04-23 à 22:16

Bonjour, voici l'énoncé:
Supposons que nous vivions dans une province, disons la province P, qui
- contient 10 villes, et
- possède 40 routes interurbaines.
En outre, une ville de la province P est appelée ville-centre si elle est reliée à toutes les autres villes de la province.
villes de P.

Soit G(P) le graphe représentant P et j le nombre de villes centrales dans P.
Nous pouvons remarquer que la somme des degrés des sommets est égale à la somme des degrés des villes centres et des autres villes.
D'après le lemme de la poignée de main, nous avons donc:
$\sum_{v\in V(P)} \delta(v)= 2\cdot 40 \Longleftrightarrow \sum_{k=1}^j 9 +\sum_{\text{v n'est pas une ville centre}} \delta(v) = 80$
v n'est pas une ville centre implique que $j\leq \delta(v) <9$
Donc notre problème c'est de trouver:
$\max\limits_{0\leq j \leq 10} \{9\cdot j +\sum_{k=1 \wedge j\leq \delta(v_k) <9}^{10-j} \delta(v_k) =80 \}$

Ma question est comment je trouve le maximum ? J'ai essayé de coder ça en python mais je n'arrive pas à l'implémenter car le graph n'est pas entièrement défini, il y a des sommets de degré indéterminé.
Le seul cas que j'ai réussi toutes les villes qui ne sont pas des centre ville sont de degré compris entre j et 8:

max([j for j in range (0,11,1) for i in range(0,11,1) if (j+i<9 and 9*j +(10-j)*(j+i)==80)])
Renvoie 5.

Or toutes les villes non centre ville peuvent avoir des degrés différentes donc ce code est insuffisant mais je suis bloqué...

PS: par une autre approche, je pense que la réponse est 6 mais j'aimerais arriver à trouver une méthode satisfaisante pour déterminer le maximum de cet ensemble.
merci par avance