Rang d'une matrice, théorie des graphes

[invite423aa977]

Bonjour,

Je souhaite avoir de l'aide pour répondre à une question bonus dans un devoir d'optimisation (bonus car elle ne concerne en rien l'optimisation). Le plus simple est que je vous montre l'énoncé:



Ce qui m'intéresse c'est la remarque. Alors j'ai bien compris que la matrice A n'est pas de rang pleine et je sais en pratique que la matrice moins une ligne est de rang pleine (sinon mes algo ne fonctionneraient pas). J'aimerais bien savoir pourquoi elle est effectivement de rang pleine et comment le montrer.

Merci de m'aider à démontrer ce résultat.
-----

[acx01b]

salut, je montrerais qu'en partant d'un graphe à M noeuds de matrice d'incidence de rang M-1 on peut ajouter une arrête et être toujours de rang M-1, ou ajouter un noeud+une arrête (connectée à ce noeud) et ... à toi de finir

[invite423aa977]

Merci, je pense avoir un raisonnement qui tient la route grâce à cela. Et on peut construire tous les graphes de la sorte, en partant d'un arc reliant 2 noeuds. (en tout cas dans le cas connexe qui m'interesse).

[acx01b]

la connexité n'est pas un problème tu peux construire les composantes connexes indépendament,
le problème c'est juste les noeuds qui n'ont pas d'arrête (donc ligne de 0 donc le rang de la matrice est diminué d'autant)

[A voir en vidéo sur Futura]