4.5 Nombre chromatique

Le nombre chromatique est le nombre minimale que l'on peut colorier un dessin, par exemple une carte du monde, sans que la même couleur soit utilisée pour 2 région limitrophes.

4.4 Chemin critique, Arbre de valeur minimale

4.3 Arbre et graphe valué

Un arbre est un graphe qui n'a pas de cycle simple. Si l'arête A-E était présente, cela créerait un cycle simple et le graphe ne serait plus un arbre.

 

Quelque définition d'un graphe valué.

Voici un exemple d'un graphe valué.

4.2 Chaînes et cycles (Eulerien ou Hamiltonien)

Différence entre chaîne et cycle.
Concept de longueur

Concept de distance

Chaîne Eulerienne et cycle Eulerien
Eulerien: une seule fois toutes les arêtes 

Hamilton: Une seule fois tous les sommets

4.1. Théorie des graphes: Définition

Les graphes servent à montrer les liens entre différents éléments

Un graphe est une façon simple de représenter une réalité.

Un graphe connexe, tous ses points sont reliés.
C'est-à-dire que tous les points sont reliés et que d'un point quelconque je peux atteindre tous les autres.

Un graphe complexe c'est que tous ses points sont relié directement (sont adjacent) à tous les autres sommets.

Cours 3.2 Procédure de vote

Devoir:

p.113 #1 à 8

p.123 # 1 à 4 et 6, 7 et 9.

Parfois les votes sont pris par préférences.  C'est-à-dire que les personnes donnent, non pas un seul nom, mais un ordre dans leur choix de candidat.

La méthode de Borda donne plus de point au premier choix
et diminue pour chaque chois subséquent.

Dans ce cas, où il y a 3 candidats, 3 points sont accordé pour un premier choix,
2 points pour le 2e choix et 1 seul point pour le 3e choix

Le principe de condorcet

Pluralité vs proportionnel

Selon la pluralité, chaque circonscription est indépendante l'une de l'autre.
C'est le candidat dans sa circonscription qui a le plus de vote qui gagne.

Dans une proportionnelle, les siège sont distribuer en proportion
 des votes sur l'ensemble de toutes les circonscriptions. 

On voit que dans une proportionnelle, il peut y avoir des fractions de sièges. Donc on attribue les sièges entiers d'abord. Une fois que tout les sièges sont distribué on calcul le nombre de sièges encore libres dû au décimales. On attribue un siège au parti ayant la plus grande partie décimale. S'il y a plus d'un sièges libre, les distribuer 1 à 1 aux partis ayant la plus grande décimale en décroissant.

Poids démographique
Dans le cas où chaque circonscription n'a pas le même nombre d'électeurs on utilise le principe de la moyenne pondérée.

On voit dans cet exemple un tableau qui a été construit à partir des 2 autres tableaux pour tenir compte des pourcentages du nombre d'électeurs par circonscription.

Cours 3.1

Le devoir est...

p. 92 #1 à 11 

p. 101 # 1 à 4

p. 84 # 1 à 8

On démontre ici la différence mathématique (logique) du ET / OU. Cette différence se transpose aussi dans la langue française.

Le signe d'union (U = ou) montre que s'il est dans A ou B
Le signe d'intersection ( et ) montre qu'il doit être à la fois dans A et dans B
La visualisation par un diagramme de Venn aide à comprendre

Ici on a un exemple de 3 événements représentés par un diagramme de Venn

Le diagramme de Venn permet de calculer rapidement des probabilités

P(A U B) n'est pas simplement l'addition de la probabilité de chacun des événements.
On a remarqué que l'intersection est comptée 2 fois.
Ce qui nous a amené à parle d'événements mutuellement exclusifs... 

Et d'événement Non-Mutuellement Exclusif.
C'est-à-dire que ces derniers partagent des éléments communs.

Probabilité conditionnelle. C'est-à-dire, qu'elle sont les chance qu'un
événement arrive s'achant qu'un autre s'est produit?
On peut remarquer que s'il ne sont pas mutuellement exclusifs alors cette probabilité conditionnelle est nulle

Dépendance et indépendance d'événement

Un arbre des possibilités est intéressant, mais lorsqu'il y a beaucoup, mais beaucoup de branches et/ou d'étapes, l'arbre est complexe.   On peut s'en sortir avec la règle de multiplication.  Mais pour l'utiliser, il faut très attentif

Un arbre des probabilités pour 2 tirage d'une pièce de monnaie.
Sur le côté, on remarque que l'on a utiliser la règle de mutliplication. Pour le tirage d'au moins une face, il faut penser au cas où il y a 2 faces.

Le cas des plaques d'immatriculation impose la règle de multiplication. L'arbre serait immense et incompréhensible, voir inutile. Il y a le cas où la plaque débute avec "SSS" 1*1*1*10*10*10 = 1000,
le cas où il y a un seul " S"  (3 exemples SXX, XSX, XXS) = 1*26*26*10*10*10 fois 3 = 2 028 000
le cas où il y a 2 "S" (3 exemples SSX, SXS, XSS) = 1*1*1*26*10*10*10 fois 3 =78 000
Donc la possibilité de 2 107 000 / 17 576 000 = 11,99%