Forum de Mathématiques: Maths-Forum

Une méthode intéressante ici : http://szhorvat.net/pelican/hh-connected-graphs.html surtout de par son théorème de faisabilité. L'algorithme soit trouve une solution connexe, soit pas de solution et ne propose pas de solution non connexe. En tout cas plus l'on cherche plus l'on voit que ce problème ...

La méthode ne garantit pas la connexité : (A2, B2, C2, D2, E1, F1) => AB, AC, DB, DC, EF Je regarde aussi du côté de la matrice d'incidence nœuds-arcs (une ligne par nœud et une colonne par arc) telle que par exemple présentée ici: https://www.sciencedirect.com/topics/mathematics/incidence-matrix Ai...

Merci pour les réponses. Le fait que la somme des degrés doit être paire est une propriété classique (d'ailleurs évidente) : https://fr.wikipedia.org/wiki/Lemme_des_poign%C3%A9es_de_main Sinon, j'ai trouvé plusieurs algorithmes en ligne, par exemple : https://www.geeksforgeeks.org/construct-graph-gi...

Bonjour, Je ne sais pas si c'est le bon forum (sinon merci de m'indiquer où je devrais poser la question) mais voici mon problème. On cherche à construire un graphe G d'après les informations suivantes : 1) non orienté 2) connexe 3) N nœuds 4) les degrés d(i) des nœuds (ou, présentation équivalente,...

Mon code (Matlab) peut générer les séquences finies pour tout K <=N (enfin, en principe, car dès que N est un peu grand, c'est trop long pour mon micro-ordinateur). Donc on peut, en théorie, générer une séquence aussi grande que l'on veut en concaténant les suites finies pour toutes les valeurs de (...

En fait on a quelque chose de semblable ici :
https://oeis.org/A134640
mais pas tout-à-fait, la définition n'étant pas exactement la même.

Ainsi, pour N=5, K=3, ma séquence est
5, 7, 11, 14, 15, 16, 17, 19, 21, 22, 23, 25 , 29, 32, ...
alors que A134640 donne
5, 7, 11, 15, 19, 21, 27 , 30, 39, ...

Merci d'avoir considéré ce problème, qui semble en effet difficile.
En tout cas les séquences générées ne sont pas dans l'OEIS ...

Bonjour, Je bute sur un petit problème que je me suis posé et résume comme suit. On considère les nombres dont l'écriture en base K est de longueur N (K<=N). Si nécessaire, on tient compte des zéros pour assurer cette longueur N. Exemples N=5, K=4 Des nombres possibles sont n1=00312, n2=11310, n3=22...

Merci, je me doutais bien que c'était un problème connu et résolu.
Personnellement, je suis plus à l'aise avec la démonstration par récurrence.

Il manque un mot important vers la fin de mon dernier message :
« Pour construire l'ensemble cherché on prend toutes les paires d'éléments orthogonaux ...»

Un vecteur doit comprendre les chiffres {1,2,...,K et les dispositions possibles sur les composantes forment un ensemble E_{1} , de taille card(E_{1})=A\begin{pmatrix} N\\ K \end{pmatrix} . Un élément de E_{1} peut être vu comme un vecteur e_{1} de dimension N avec N-K composantes nulles. Ce...

Bonjour (ou bonsoir ?), On considère les vecteurs V à N composantes dont les valeurs sont prises dans E={1, 2, ..., K). On suppose N>=K. Combien y en a-t-il satisfaisant à la condition « contenir au moins une fois chaque élément de E » ? J'avais d'abord pensé à une formule comme arrangements(N,K)*K^...