Graphes

Coucou,

C'est encore moi.

Des problèmes, toujours des problèmes

Soit G un graphe correspondant au problème des n carrefours et M sa matrice.

1) Montrer que dans un graphe la somme des degrés est égale à deux fois le nombre d'arêtes.
2) Que représente l'ordre du graphe pourM ? Que dire de M si toutes les rues sont à double sens ?
3) Un graphe est complet si tous ses sommets sont adjacents. Que dire de M dans ce cas là ? Représenter un graphe complet non orienté puis orienté d'ordre 4. [
Combien un graphe complet orienté puis non orienté d'ordre n a-t-il d'arêtes ?
4) Comment interpréter les sommes d+ = [Somme pour j= 0 à n] mij et d- = [Somme pour j= 0 à n] mji ainsi que la trace de M ?
5) Comment interpréter la transposée de M ?

J'ai fait la 1, 2, 3 mais je n'arrive pas les autres, quelqu'un peut-il m'aider ? Merci beaucoup d'avance encore une fois.

salut LiLi §!!!!

je crois que ça est dans le cours de "theorie des graphes"

PS:tu es en quelle ecole?? et quel niveau?? et merci
PS: si tu n'as pas trouvé la reponse je peux reponds
__________________________
Theorie des graphes

Salut wagshall, merci pour ta réponse.

Je suis en MPSI dans le Nord de la France.

Je viens de vérifier mon cours et je ne trouve pas la réponse, je veux bien un peu d'aide. Merci

OK LiLi j'ai etudié les théorie des graphes en 2éme année DEUG et je rappelle ce cours c'est un formidable et important cours bon... pour la réponse je le posterai trés prochain aprés avoir terminer une truc
et merci
_____________________________________________
th des G

Vous êtes tous merveilleusement gentils ici, merci énormément.

J'aurais peut-être encore 2-3 questions, si ça ne te dérange pas.

Non pas de probleme merci pour toi egalement!!!!
qu'il est votre questions??

______________________________________________
tHG

Je vais réfléchir aux questions que je devrais peut-être te poser. J'attends que tu me dises quoi pour celles du dessus. Je ne vais plus savoir où j'en suis sinon lol

BSR LiLi !!

J'aurais bien voulu te donner un coup d'pouce mais hélàs , je n'en ai jamais fait dans mon cursus !!
Pourtant celà sert beaucoup au quotidien ( en Recherche Opérationnelle ) ; on a résolu pas mal de problèmes à l'aide de la Théorie des Graphes ( les 7 Ponts de Koenigsberg , les Réseaux de Bus , les Feux Rouges etc ..... )

http://fr.wikipedia.org/wiki/Probl%C3%A8me_des_sept_ponts_de_K%C3%B6nigsberg

Bonsoir LILI , j'ai eu le sujet des graphes ou plus précisement le théorème d'euler dans mon ADS , et j'ai traiter on dirait presque les questions en passant ! je posterais dés possible

salut LiLi !!!

j'ai pas lu ta derniere phrase mais c pas grave je reponds a 4++ d'abord je crois que vous avez commencé ce cours avant des semaines ou des jours c'est a dire c'est pas pour longtemps car:

pour 4:
d+ :c'est le degré sortant d'un sommet i
d- :.................... entrant ..................
la trace c'est les boucle cest a dire l'arrete sortant et entrant dans même sommet.

5) la matrice transposé de M est la matrice qui represente le role inverse de celle de M en effet:

M= { mij=1 si (i,j)£A et mij=0 sinon} dans le cas de graphe non orienté

donc tM={mji=1 si(j,i)£A et mij=0 sinon} dans même graphe.

dans le graphe orienté:
M={mij=1 si (i;j)£A et mij=-1 si (j;i)£A et mij=0 sinon}
de même pour tM il suffit de permetter i et j de celle de M.

PS: A: ensemble des arrets

2) l'ordre c'est le nombre des sommets donc l'intersection de carrefour.....

je crois ça c'est le cours ou non????
ps sinon signaler le et je completerai merci
________________________________________________
merci

Merci énormément.

Ce midi, je poserai encore quelques questions que je n'arrive pas à faire.

Vous êtes géniaux !!!!!

Me revoilà

Soit k € |N* et mij^(k) le coefficient de la i-ème ligne et de la j-ème colonne de M^k

1) Montrer par récurrence que mij^(k) est le nombre d'itinéraires de Ci à Cj empruntant k rues, distinctes ou non. Un tel itinéraire sera appelé un k-chemin

2) On suppose que M est nilpotente : Il existe N € |N, M^N = On
a) Interpréter la nilpotence de M
b) Montrer par récurrence que, pour tout (i,j) € [1,n]², mij^(k) =< n^(k-1)
c) En déduire que le nombre total Zij de chemins de Ci à Cj est fini.
d) On pose T = Zij € Mn(|R). Montrer que In + T = (In - M)^(-1)


Je n'y comprends rien du tout. Ce serait vraiment gentil de m'aider là. Merci beaucoup beaucoup.


PS : Coucou oeil de lynx et les autres