Bonjour


Exo 1
Si aucuune personne n'a le même nombre de connaissances:
1 personne a 0 connaissance (elle ne connait personne dans le groupe)

1 personne a 1 connaissance (elle connait une personne mais cette personne la connaît aussi !)

1 personne a 2 connaissances (elle connait 2 personnes et ces personnes la connaîssent aussi !)

1 personne a 3 connaissances

...

1 personne a 9 connaissances

Le total des degré est 45
et ce nombre n'est pas paire d'o^ù une contradiction ...

merci pour l'exo1!

j'aurais dû me creuser plus, mais ça me paraissait pas évident du tout! des fois tellement c simple ça parâit compliqué!

Exo 2

considérons le graphe G obtenu avec la relation "a pour connaissance"

premier cas: il existe un sommet de degré supérieur ou égal à 3
On a un des deux cas suivants

soit il exite une 3-cycle soit trois sommets sans arête de l'un à l'autre.


second cas: il n'existe pas de sommet de degré supérieur ou égal à 3
On considére le graphe ssocié à la relation "ne connait pas"
et forcément celui a alors un spommet de degré supérieur ou égal à 3 ... et on apllique le raisonnement précédent

pour l'exo 2, je ne comprends pas trop le graphe... en fait, je ne sais pas comment le dessiner!

Sinon, une petite idée pour l'exo 4?

je suis démoralisé, personne ne trouve pour l'exo 4!

Coucou,

L'exo 4 sur les matrices, c'est le plus important pour moi, car c'est celui que je maîtrise le moins! Pouvez-vous m'aider s'il vous plait ?

Merci beaucoup d'avance!

Bonsoir

le terme a_i,j dans la matrice A^k représente le nombre de chemins de longueur k pour aller de i à j

si tu fais la somme des matrices, tu vas faire la somme des a_i,j, tu additiones alors le nombre de  chemin de longueur 1, le nombre de chemins de longueru 2 , ..., le nombre de chemins de longueur n pour aller de i à j

et tu obtiens donc le nombre de chemins de longueur inférieure ou égale à n permettant d'aller de i à j.

ce graphe donné et vraimùent incompéhensible
j'aimerais bien t'aider mes j'ai exactement le même pb
avec cette exo
et une réponse plus claire nous serait utile je pense a nous deux

Bonjour,

Pour paraphraser Siok

Vous avez 6 personnes.
Imaginons qu'il existe une personne A qui en connaisse au moins trois autres B, C, D (commencez à construire le graphe)
de deux choses l'une
* ou bien B connait C, ou C connait D ou D connait B et alors vous avez 3 personnes qui se connaissent mutuellement (relation en triangle)
* ou bien B ne connait pas C et C ne connait pas D et D ne connait pas D et vous avez 3 personnes qui ne se connaissent pas mutuellement

Imaginons maintenant que A connaisse au plus deux personnes B et C. Alors A ne connait pas D, ni E ni F. De deux choses l'une
* ou bien D ne connait pas E, ou E ne connait pas F ou F ne connait pas D et vous avez trois personnes qui ne se connaissent pas
* ou bien D connait E, E connait F et F connait D et vous avez 3 personnes qui se connaissent

Vous avez 4 graphes (incomplets) à dessiner qui illustrent chacun une des quatre situations. Vous tracer en rouge les branches qui relient deux personnes qui se connaissent et en jaune les branches qui relient deux personnes qui ne se connaissent pas. Vous verrez à ce moment là que vous ne pouvez pas faire autrement que de dessiner un triangle rouge ou un triangle jaune.

Lire dans le cas 2
"ou bien B ne connait pas C et C ne connait pas D et D ne connait pas B et vous avez 3 personnes qui ne se connaissent pas mutuellement"
au lieu de
"ou bien B ne connait pas C et C ne connait pas D et D ne connait pas D et vous avez 3 personnes qui ne se connaissent pas mutuellement"