[index Math] Pour discuter de mathématique...

[freeshost]

1. Non, bien plus que 4.

(1 ; 2 ; 3 ; 4 ; 5 ; 6 ; 7 ; 8 ; 9 ; 10) est un ordre possible.
(4 ; 7 ; 10 ; 3 ; 6 ; 9 ; 2 ; 5 ; 8 ; 1) en est un autre possible.
...

2. Non, ce n'est pas possible. La boule a un rayon de 10 cm. Son diamètre est donc de 20 cm. Donc la distance minimale entre les deux murs est de 20 cm, auquel cas, elle toucherait les deux murs. Truc : se rappeler de la formule du périmètre du cercle en fonction du rayon.

3. Un full est la combinaison d'un brelan et d'une paire. Par exemple : trois as et deux rois.

4. Non, moins.

5. Il faut cocher 5 numéros parmi 50 et 2 étoiles parmi 10.

6. Juste !

7. Non, bien sûr, pas 10 équipes de 3 personnes, car il y a bien plus de 30 personnes. Il faut que chaque équipe ait au moins trois personnes et qu'il y ait au moins dix équipes.

Exemples : 10 équipes de 420 personnes ; 140 équipes de 30 personnes ; etc.

8. Non.

[Rem 82]

Un site sympa ...

http://www.pi314.net/fr/index.php

[Ixy]

En parlant des graphes :

1) Un graphe complet est un graphe qui a tous ses sommets reliés à tous les autres. Combien ce graphe a d'arêtes (les arêtes doubles ne sont pas autorisées) ?

2) Si pour un graphe il existe un chemin passant par toutes les arêtes, que peut-on dire sur le degré de chaque sommet ? Le degré d'un sommet est le nombre d'arêtes qui est relié à ce sommet.

3) Comparer le nombre d'arêtes et la somme des degrés.

Pour un graphe orienté (les arêtes sont des flèches), on distingue le degré entrant (le nombre d'arêtes dont la flèche pointe vers le sommet) et le degré sortant (nombre d'arêtes qui partent de ce sommet).

4) Existe-t-il un graphe dont tous les sommets ont un degré sortant strict. positif et qui n'admet pas de cycle ? Un cycle est un chemin dont le point de départ est aussi le pont d'arrivée. Quelle condition nécessaire doit vérifier un tel graphe ?


Voilà une bonne introduction à la théorie des graphes

[freeshost]

1. Soit n le nombre de sommet d'un graphe, alors ce graphe a n(n-1)/2 arêtes. [Bon, on peut appeler ces sommets des nœuds et ces arêtes des relations simples ?]

2. Il y a au moins n-2 sommets qui ont au moins le degré deux. Et au plus deux sommets qui ont le degré 1.

3. Le nombre d'arêtes est la moitié de la somme des degrés.

4. A priori, il me semble que non, puisque toute flèche donne lieu à un intrant et à un extant, avec ou sans cycle.

As-tu de bons pdf ou livres francophones sur la théorie des graphes ?

À quoi sert la théorie des graphes ?

Au fait, tes problèmes me font penser au problème du plus court chemin. Quels ouvrages pour apprendre à appréhender et comprendre et tâter les problèmes dits NP-Premiers ?

[Benoit]

Il y a des graphes orientes et non orientes, rien n'empeche d'avoir une arete dans chaque sens entre deux noeuds.

La terminologie 'officieuse' est noeud et arete, l'officielle est GEV / Graph / Edge / Vertex.

La theorie des graphes etait vachement utile quand les processeurs ramaient comme pas permis, maintenant c'est surtout un outil pour les mathematiciens qui comme chacun sait ne savent pas developper dans des langages utiles.

[freeshost]

C'est un cours de mathématiques pour l'informatique.

La théorie des graphes est utile pour comprendre certains algorithmes, par exemple l'algorithme de Djikstra.

Cet algorithme permet de résoudre le problème du plus court chemin ? Je croyais que ce problème n'avait pas encore été résolu.

[Benoit]

Pas s'il y a des aretes de valeur negative, il faut faire appel par exemple a BellmanFord dans ce cas la.

Heureusement, il reste plein de problemes NP complexes insolubles avant le terme de l'Univers.

[freeshost]

Qu'est-ce qu'une arête négative ?

[Ixy]

Tu confonds avec le pb du voyageur de commerce probablement où il faut passer par tous les noeuds (cycle hamiltonien sur graphe complet).

1 oui
2 je voulais parler d'un cycle (on revient au point de départ). On peut en dire plus alors sur le degré des sommets (en fait on recherche une condition nécessaire et suffisante avec la condition que le graphe est fortement connexe).
3 oui
4 pas la réponse attendue


Une intro : https://www.lri.fr/~paulin/MathInfo2/html/cours004.html

[Benoit]

Qu'est-ce qu'une arête négative ?

En général on affecte des valeurs sur les arêtes quand on recherche un chemin.

Il y a des centaines de problèmes concrêts où une valeur négative aide à faire le graphe.

L'algo de Dijkstra ne fonctionne pas avec un tel graphe.

[freeshost]

Bon, il me va falloir lire l'introduction quand j'en aurai le temps... heu... fin juin 2017... peut-être...

[Salicorne]

Un autre problème de la théorie des graphes :

Montrer que dans un groupe de n personnes, il y a toujours au moins deux personnes ayant le même nombre d'amis présents.
(Les personnes sont représentées par des sommets, les liens d'amitié par des arêtes.)

[Benoit]

Qu'est-ce que vous avez tous avec des graphes non orientés, surtout dans cet exemple où clairement il faut un graphe orienté.

[Bubu]

Dans les graphes, on distingue les arêtes des flèches.
L'arête, représentée par une ligne entre deux sommets, peut être parcourue dans les 2 sens.
La flèche ne peut qu'être parcourue dans le sens fixé.

Des théorèmes qui répondront aux énigmes :
Graphe eulérien

[Bubu]

L'algorithme de Dijkstra permet de déterminer un itinéraire optimal entre un ensemble de lieux séparés par des distances.
Cela se représente par un graphe orienté (ou mixte : simplement des flèches ou arcs dans les 2 sens pour les liens entre 2 sommets.)
Il faut étiqueter les arcs par une pondération correspondant à la distance. (Je place Brest. Je place Lorient. L'arc entre les 2 est étiqueté 200 km)

L'algo de Disktra vous dira le chemin optimal (la suite d'arcs à suivre) pour y parvenir avec la distance minimale.

Si l'on fait appel aux heuristiques, il y a une généralisation : A*
Adapté aux grandes cartes.
Votre GPS utilise cet algorithme.