Un résumé de cours en version imprimable est téléchargeable ici.

Demander le programme !

programme officiel
programme officiel programme officiel

Un problème initial

La ville de Königsberg était une ville de Prusse puis une des principales villes de l'Empire Allemand avant d'être céder à l'URSS en 1945. Cette ville est désormais appelée Kaliningrad et fait partie de la Fédération de Russie.

localisation

Cette ville s'étendait au $XVIII^e$ siècle autour de deux îles situées sur le fleuve Pregel. Ces deux îles étaient reliées entre elles par un pont. Six autres ponts reliaient les rives de la rivière à l'une ou l'autre des deux îles, comme représenté sur le plan ci-dessous.

pont de Könisberg

La légende raconte que certains habitants de cette ville cherchaient lors de promenade à passer une fois et une seule par chacun des ponts pour revenir au point de départ (évidemment, ils ne pouvaient traverser l'eau du Pregel qu'en passant par un des ponts.)

Est-ce possible ? Si oui, par quel chemin ?

Les habitants ont cherché des solutions et l'un d'eux, le grand mathématicien Euler, a réussi en 1735 à répondre à la question précédente. Pour cela, il a développé des outils mathématiques à la base de la théorie des graphes, théorie qui sera effleurée dans ce cours.

Modélisation :

Une des idées d'Euler fut de modéliser la situation pour réduire à l'essentiel le problème ; il a représentée la configuration précédente des ponts dans la ville en la figure ci-dessous :

modélisation par un graphe

figure qui peut être déformée ainsi :

modélisation clarifiée par un graphe

Cet objet synthétique s'appelle un graphe où les points A, B, C et D sont des sommets et les traits reliant ce points des arêtes.

Graphe non-orienté

Vocabulaire sur les graphes non-orientés

modélisation clarifiée par un graphe
modélisation clarifiée par un graphe
  1. Justifier la première affirmation de la propriété précédente.

  2. Code de déblocage de la correction :

  3. Démontrer, à l'aide d'un raisonnement par l'absurde, la seconde affirmation de la propriété précédente.

Code de déblocage de la correction :

On considère le graphe représenté ci-dessous ; il modélise le plan d'un village. Les arêtes du graphe représentent ses rues et les sommets les croisements de celle-ci.

graphe exo1
  1. Quel est l'ordre du graphe ?

  2. Déterminer le degré de chacun des sommets.

  3. En déduire le nombre de rues de ce village.

  4. Quel est le nombre de sommets de degré impair ?

  5. Citer deux sommets adjacents.

  6. Citer deux sommets non adjacents.

  7. Ce graphe est-il complet ?

Code de déblocage de la correction :

Parcours sur un graphe non-orienté

On considère le graphe non-orienté suivant :

graphe exemple 3
  1. Quel est l'ordre du graphe ?

  2. Quel nom peut porter la chaîne $B - C - E - B$ ? Quelle est sa longueur ?

  3. Déterminer une chaîne de longueur 8 reliant $F$ à $D$

  4. Déterminer un cycle d'origine $G$.

  5. Le graphe est-il connexe ?

Code de déblocage de la correction :

Proposer un graphe qui n'est pas connexe.

Code de déblocage de la correction :

Graphe orienté

Vocabulaire

Proxémie des termes suivant l'orientation ou non du graphe :

Graphe non-orienté Graphe orienté
arête arc
chaîne chemin
cycle circuit

Voici un graphe :

premier graphe orienté du cours

Le graphe suivant représente le plan d’une ville. Les arcs du graphe représentent ses avenues commerçantes, en prenant en compte le sens de circulation, et les sommets du graphe les carrefours de ces avenues.

bac ES métropole septembre 2017
  1. Est-ce un graphe orienté ou non-orienté ? Pourquoi ?

  2. Quel est l'ordre du graphe ?

  3. Proposer un chemin de longueur 4 d'origine $F$ et d'extrémité $B$.

  4. Proposer un circuit passant par tous les sommets.

Code de déblocage de la correction :

Matrice d'adjacence d'un graphe

Un journaliste britannique d’une revue consacrée à l’automobile doit tester les autoroutes françaises. Pour remplir sa mission, il décide de louer une voiture et de circuler entre six grandes villes françaises : Bordeaux ($B$),Lyon ($L$), Marseille ($M$), Nantes ($N$), Paris ($P$) et Toulouse($T$). Le réseau autoroutier reliant ces six villes est modélisé par le graphe ci-dessous sur lequel les sommets représentent les villes et les arêtes les liaisons autoroutières entre ces villes.

bac ES Polynésie juin 2018

Plutôt que de représenter la situation par un graphe, le journaliste visualise le réseau avec un tableau dans lequel il met 1 s'il existe une liaison directe entre les deux villes correspondant à la case et 0 sinon. Il obtient donc le tableau ci-dessous :

Villes $B$ $L$ $M$ $N$ $P$ $T$
$B$ 0 1 0 1 1 1
$L$ 1 0 1 1 1 1
$M$ 0 1 0 0 0 1
$N$ 1 1 0 0 1 0
$P$ 1 1 0 1 0 1
$T$ 1 1 1 0 1 0

Par exemple, il existe une autoroute reliant directement Paris $P$ à Nantes $N$, donc il y a le nombre 1 dans les cases repérées par $N$ et $P$ ;

il n'existe pas d'autoroute reliant directement Marseille $M$ à Bordeaux $B$, donc il y a le nombre 0 dans les cases repérées par $M$ et $B$.

Pour synthétiser l'information (en mémorisant le fait que les villes sont rangées dans l'ordre alphabétique), il suffit de considérer le tableau extrait contenant les données chiffrées. On peut appeler ce tableau matrice. Voici la matrice représentant la situation :

$$G = \begin{pmatrix} 0 &1 &0 &1 &1 &1 \\ 1 &0 &1 &1 &1 &1\\ 0 &1 &0 &0 &0 &1\\ 1 &1 &0 &0 &1 &0 \\ 1 &1 &0 &1 &0 &1\\ 1 &1 &1 &0 &1 &0 \end{pmatrix} $$

La matrice associée à un graphe d'ordre $n$ est la matrice carrée de taille $n$, où le terme de la $i$-ème ligne et de la $j$-ème colonne est égal au nombre d'arêtes (ou d'arc) partant du sommet $i$ pour arriver au sommet $j$.

Cette matrice s'appelle la matrice d'adjacence de ce graphe.

Le graphe ci-dessous représente, dans un aéroport donné, toutes les voies empruntées par les avions au roulage. Ces voies, sur lesquelles circulent les avions avant ou après atterrissage, sont appelées taxiways. Les sommets du graphe sont les intersections. Les arcs du graphe représentent les voies de circulation (les « taxiways ») en prenant en compte le sens de circulation pour les avions dans les différentes voies ainsi que le temps de parcours pour chacune en minute(s).

bac ES Polynésie juin 2014

En rangeant les sommets dans l'ordre alphabétique, la matrice $M$ d'adjacence de ce graphe est

$$M = \begin{pmatrix} 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{pmatrix}$$

En effet peu importe les distances écrites et, par exemple, :

Le graphe suivant représente le plan d’une ville. Les arcs du graphe représentent ses avenues commerçantes, en prenant en compte le sens de circulation, et les sommets du graphe les carrefours de ces avenues.

bac ES métropole septembre 2007
  1. Écrire la matrice $M$ associée à ce graphe. (On rangera les sommets dans l’ordre alphabétique).

  2. Cette matrice est-elle symétrique ? Pourquoi ceci était-il prévisible ?

Code de déblocage de la correction :

Exercices

Graphe non-orienté

On a schématisé ci-dessous une partie du plan du métro londonien par un graphe $\Gamma$ dont les sommets sont les stations et les arêtes sont les lignes desservant ces stations.

Chaque station de métro est désignée par son initiale comme indiqué dans la légende.

Bas ES centre étranger juin 2015
  1. Proposer un cycle qui permettrait de passer par chacune des stations de métro du graphe $\Gamma$.

  2. Déterminer en justifiant si le graphe $\Gamma$ est connexe.

  3. Déterminer en justifiant si le graphe $\Gamma$ est complet.

  4. Donner la matrice d'adjacence $M$ du graphe $\Gamma$ (les sommets seront rangés dans l'ordre alphabétique).

  5. On appelle chaîne eulérienne une chaîne qui permet de passer par toutes les arêtes une et une seule fois.

    Existe-t-il une chaîne eulérienne à ce graphe $\Gamma$ ? Si oui, en donner une.

Sarah, une jeune étudiante en géologie, souhaite partir en voyage en Islande avec des amis. Elle a loué une voiture tout terrain pour pouvoir visiter les lieux remarquables qu'elle a sélectionnés.
Sarah a construit le graphe ci-dessous dont les sommets représentent les lieux à visiter et les arêtes représentent les routes ou pistes :

Bas ES Amérique du Nord juin 2017
  1. Dans cette question, chaque réponse sera justifiée.

    1. Déterminer l'ordre du graphe.

    2. Déterminer si le graphe est connexe.

    3. Déterminer si le graphe est complet.

    1. Dresser un tableau dans lequel apparaîtront chaque sommet avec son degré.

    2. Comment peut-on en déduire le nombre d'arêtes du graphe ?

  2. On appelle $M$ la matrice associée au graphe précédent sachant que les sommets sont placés dans l'ordre alphabétique.

    $$M = \begin{pmatrix} 0 &0 &0 &0 &0 &0 &0 &1 &1 \\ 0 &0 &0 &0 &0 &0 &1 &0 &0 \\ 0 &0 &0 &0 &0 &1 &0 &1 &1 \\ 0 &0 &0 &0 &0 &0 &1 &1 &0 \\ 0 &0 &0 &0 &0 &1 &1 &0 &1\\ 0 &0 &1 &0 &1 &0 &1 &0 &1\\ \ldots&\ldots&\ldots&1 &1 &1 &0 &0 &1\\ \ldots&\ldots&\ldots&1 &0 &0 &0 &0 &0\\ \ldots&\ldots&\ldots&0 &1 &1 &1 &0 &0 \end{pmatrix}$$

    Il manque certains coefficients de la matrice $M$. Compléter et recopier uniquement la partie manquante de cette matrice.

Huit villages d'une zone rurale sont reliés entre eux par un réseau de routes. Pour simplifier, les villages sont numérotées de 1 à 8. On admet que le réseau de routes reliant ces villages est représenté par le graphe suivant :

schéma à la rue !

Un virus arrive dans la zone, il va peut-être falloir mettre en quarantaine tout un village ! Quod video ! O COVID !
Dans ce cas, toutes les routes menant à ce village seraient interdites.

  1. Existe-t-il un village tel que si on le met en quarantaine, il ne sera plus possible d'aller de certains villages à d'autres ? Si oui, donner le numéro représentant ce village.

  2. Dessiner le graphe représentant le réseau de routes encore possibles si le village proposé précédemment est mis en quarantaine.

  3. Ce graphe est-il connexe ?

L'exercice précédent est adapté d'un exercice du serveur WIMS de WIMS de l'université de Paris-Sud qui propose des exercices et des cours interactifs en accès libre et gratuit.

Si vous voulez plus d'exercices corrigés automatiquement, vous pouvez utiliser ce serveur .

Pour les graphes :

Ci-dessous, un deuxième exercice inspirée de ce site afin de vous inciter à le découvrir.

Douze villes internationales sont reliées par des liaisons aériennes assurées par une même compagnie. Pour simplifier, les villes sont numérotées de 1 à 12. Le réseau aérien de ces villes est modélisé par le graphe ci-dessous où l'existence d'une liaison aérienne entre deux villes est modélisée par une arête reliant les deux numéros de villes.

Comme le secteur aérien souffre d'une crise de clientèle, la compagnie aérienne réfléchit à la possibilité de supprimer certaines liaisons aériennes entre ces villes.

Quelle liaison aérienne est-il impossible de supprimer sous peine de ne plus pouvoir rejoindre n'importe laquelle des douze villes depuis certaines de ces villes ?

Graphe orienté

Un parcours sportif est composé d'un banc pour abdominaux, de haies et d'anneaux. Le graphe orienté ci-dessous indique les différents parcours conseillés partant de D et terminant à F.

Les sommets sont: D (départ), B (banc pour abdominaux), H (haies), A (anneaux) et F (fin du parcours).

Les arcs représentent les différents sentiers reliant les sommets.

bac ES métropole juin 2018
  1. Quel est l'ordre du graphe?

  2. Est-il possible de suivre un parcours en passant par toutes les étapes ?

  3. On note $M$ la matrice d'adjacence de ce graphe où les sommets sont rangés dans l'ordre alphabétique. Déterminer cette matrice $M$.

  4. Le responsable souhaite ajouter une barre de traction notée T. De nouveaux sentiers sont construits et de nouveaux parcours sont possibles.

    La matrice d'adjacence $N$ associée au graphe représentant les nouveaux parcours, dans lequel les sommets sont classés en ordre alphabétique, est :

    $$N = \begin{pmatrix} 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ \end{pmatrix}$$

    Compléter le graphe précédent en ajoutant les arcs nécessaires pour que le graphe orienté obtenu corresponde à la matrice $N$.

Modélisation par un graphe

Voici la carte des arrondissements du département de la Marne lors des dernières élections législatives.

carte arrondissements de la Marne
  1. Modéliser cette carte des arrondissements par un graphe dans lequel les sommets sont les arrondissements (prendre l'initiale du nom de l'arrondissement comme nom du sommet) et les arêtes traduisent la présence d'une frontière entre deux régions.

  2. Le graphe est-il orienté ?

  3. Le graphe est-il complet ?

  4. Le graphe est-il connexe ?

$P_1$, $P_2$, $P_3$, $P_4$, $P_5$ et $P_6$ désignent 6 espèces de poissons.

Dans le tableau ci-dessous, une croix signifie que deux espèces ne peuvent cohabiter dans le même milieu.

Espèces de poissons $P_1$ $P_2$ $P_3$ $P_4$ $P_5$ $P_6$
$P_1$ X X
$P_2$ X X X
$P_3$ X X
$P_4$ X X
$P_5$ X X
$P_6$ X
  1. Le graphe où les sommets sont des espèces de poissons tandis que les arêtes indiquent les incompatibilités entre espèces est-il orienté ou non ? Justifier.

  2. Représenter ce graphe.

  3. Combien de bassins différents faut-il prévoir au minimum pour pouvoir élever ces 6 espèces de poissons ?

Une classe de Terminale est en voyage scolaire en Angleterre.

Les professeurs organisateurs de ce voyage décident de visiter plusieurs sites de Londres.

Les sites retenus dans Londres sont les suivants : Warren Street, Oxford Circus, Piccadilly Circus, Leicester Square, Holborn, Embankment et Temple. Ces lieux sont désignés respectivement par les lettres $W$, $O$, $P$, $L$, $H$, $E$ et $T$.

Le professeur d'anglais aimerait représenter l'ensemble des sites à visiter avec les jonctions possibles entre eux à l'aide d'un graphe.

Il y a demandé de l'aide à son collègue de mathématiques, qui très taquin, lui a transmis le "tableau de nombres" suivant :

$$ \begin{pmatrix} 0 &0 &0 &0 &1 &1 &0 \\ 0 &0 &1 &0 &0 &1 &1 \\ 0 &1 &0 &0 &1 &1 &1\\ 0 &0 &0 &0 &1 &0 &1\\ 1&0 &1 &1 &0 &1 &0\\ 1 &1 &1 &0 &1 &0 &0\\ 0 &1 &1 &1 &0 &0 &0\\ \end{pmatrix} $$

Le professeur de maths lui a aussi dit que :

Tout cela est très obscur pour le professeur d'anglais, il est tout dés-orienté ! Il fait donc appel à vous pour obtenir le graphe recherché.

Construire un graphe correspondant au besoin du professeur d'anglais ; il vous remerciera au moins d'un grand "Thanks a lot !"

Lors d'une soirée chez mes voisins, j'ai entendu 45 tintements de verre.

En supposant que chaque personne a trinqué une et une seule fois avec les autres, déterminer le nombre de personnes présentes.

Un État virtuel compte 11 grandes villes dont la capitale $C$.

Chacune de ces 11 villes est reliée a au moins 5 grandes villes par une autoroute.

Peut-on aller, en empruntant l'autoroute, de la capitale à chacune des autres grandes villes de ce pays ?

On donne ci-dessous le plan simplifié d'un lycée :

bac ES centre étrangers 2014
  1. Traduire la situation par un graphe dont les sommets représentent les salles et dont les arêtes représentent les passages possibles entre ces salles.

  2. Quel est l'ordre du graphe ?

  3. Le graphe est-il connexe ? Qu'en déduire concrètement ?

  4. Le graphe est-il complet ? Qu'en déduire concrètement ?

À la fin d'un semestre, les examens de licence proposent six options : Calcul différentiel ; Géométrie euclidienne ; Théorie des nombres ; Algèbre linéaire ; Probabilités et Statistiques.

Chacun des candidats a pu choisir deux ou trois de ces options.

Certains ont choisi Théorie des nombres et Algèbre linéaire ; d'autres le Calcul différentiel, les Probabilités et les Statistiques ; enfin d'autres ont choisi Géométrie euclidienne et Théorie des nombres.

Sachant que les étudiants passent au plus une épreuve chaque jour, combien peut-on programmer d'épreuves au maximum en une journée ?

Parmi 11 élèves volontaires, un professeur de mathématiques doit constituer des groupes d'au plus 4 personnes pour faire préparer une présentation orale.

Le professeur doit faire attention aux relations entre les élèves :

Comme le professeur de mathématiques n'arrive pas à constituer le minimum de groupes ne dépassant pas 4 élèves, il fait appel à vous :

Combien de groupes ne dépassant pas 4 élèves peut-on faire au minimum ? Proposez une répartition des élèves pour avoir un minimum de groupes.

Code de déblocage de la correction :

Si vous voulez plus d'exercices corrigés automatiquement, vous pouvez utiliser le serveur WIMP de PAris-Sud à cette adresse .

Vous pouvez y sélectionner "Matrice d'un graphe", Matrice d'un graphe orienté" ou "Chaînes orientées fermées".

Un colloque réunit $n$ personnes.
Le premier jour chaque personne peut serrer une fois ou non la main de chacune des autres personnes.

Justifier qu'au moins deux personnes ont serré le même nombre de mains ce premier jour.

Code de déblocage de la correction :

Exercices de prolongement

Partie A : Conjecture d'un théorème

Une chaîne eulérienne est une chaîne qui contient une fois et une seule chaque arête du graphe.

Concrètement, Chercher une chaîne eulérienne revient à essayer de dessiner le graphe sans lever le crayon et sans passer plus d'une fois sur le même trait

Voici ci-dessous différents graphes :

graphe poisson K5 K5 sans une arête maison croisée

Partie B : Application au problème du pont de Königsberg

On considère un graphe contenant une chaîne eulérienne.

  1. Expliquer pourquoi tous les sommets sont d'ordre pair, sauf éventuellement le premier et le dernier de la chaîne.

  2. On se place dans le cas où les extrémités sont confondues. Considérons un sommet $S$ par lequel la chaîne est passée $k$ fois, $k\in\mathbb{N}$. Quel est le degré de $S$ ?

  3. On se place à présent dans le cas où les extrémités ne sont pas confondues? Quel est le degré Quel est le degré d'une extrémité par lequel la chaîne est passée $k$ fois, $k\in\mathbb{N}$ ?

  4. Voici un théorème, énoncé par Euler en 1736 et prouvé par Hierholzer en 1873 :

    un graphe connexe possède une chaîne eulérienne si, et seulement si, au plus deux de sommets sont de degré impair.

    Avec les questions précédentes, a-t-on prouvé ce théorème ou non ?

  5. Conclure sur le problème des ponts de Königsberg.

Partie A : étude du problème

  • Colorier un graphe, c'est affecter une couleur à chaque sommet, de sorte que deux sommets adjacents ne portent pas la même couleur.

  • Le nombre chromatique, noté $\gamma$, est le plus petit nombre de couleurs nécessaires pour colorier un graphe.

  • Considérons un graphe $\Gamma$.

    Un sous-graphe de $\Gamma$ est un graphe $\Gamma'$ composé de certains sommets de $\Gamma$ et de toutes les arêtes reliant ces sommets.

Notons $m$ l'ordre du plus grand des sous-graphes complets de $\Gamma$ et $\Delta$ le plus grand des degré des sommets de $\Gamma$.

Justifier que $m\leqslant \gamma \leqslant \Delta+1$.

Code de déblocage de la correction :

Partie B : algorithme de Welsh-Powell

Pour colorier un graphe, on peut utiliser l'algorithme glouton suivant :

Colorier le graphe ci-dessous à l'aide de cet algorithme :

exemple de graphe connexe assez grand

Partie C : application sur un problème concret

Diogène est éducateur de chiens ; il donne donne des leçons à 9 chiots : Antisthène, Bion, Cléomène, Démétrios, Échéclès, Favonius, Gadarides, Héracléios et Isidore.

Diogène souhaite réaliser des exercices par petits groupes, de 2 ou 3 chiots tout en respectant la nature de ces animaux :

  1. Représenter cette situation à l'aide d'un graphe $\Gamma$.

  2. Le graphe est-il connexe ? Justifier.

    1. Déterminer un sous-graphe complet d'ordre maximal du graphe $\Gamma$.

    2. Que peut-on en déduire pour le nombre chromatique du graphe $\Gamma$ ?

  3. Donner la valeur du nombre chromatique du graphe $\Gamma$.

  4. Peut-on proposer une répartition des chiots en groupes de deux ou trois chiots pouvant travailler ensemble ?

Partie D : limite de l'algorithme

L'algorithme de Welsh-Powell permet d'obtenir une coloration de tout grapheme_extract, mais permet-il d'obtenir à coup sûr une coloration avec un nombre de couleurs minimal ?

  1. Colorier le graphe ci-dessous en utilisant l'algorithme de Welsh-Powell. Combien de couleurs sont nécessaires ainsi ?

  2. Pouvez-vous trouver une coloration du graphe précédent avec seulement 2 couleurs ?

  3. Conclure quant à l'interrogation posée en début de partie D.

Pour plus de détail, vous pouvez consulter ce site.

Dans un monde imaginaire, un Hobbyt et un Forfadais, deux êtres gentils doivent traverser une rivière dangereuse pour atteindre la Terre du Miredor. Un Mazgueul, un être horrible et maléfique les accompagne. Un Passeur, qui est un frère, peut faire traverser la rivière dans sa barque à au plus une personne à la fois.
Cependant, il faut que ni le Hobbyt et le Mazgueul, ni le Forfadais et le Mazgueul ne restent tous les deux seuls sur une rive à un moment donné sinon le Mazgueul en profitera pour dévorer cet être resté seul avec lui. Par contre, vu comme est rabougri le Passeur, lui ne risque rien à transporter seul le Mazgueul.

Comment faire pour que les trois êtres fabuleux puissent traverser la rivière grâce au Passeur sans que le Mazgueul n'en dévore un ?

Réaliser un graphe dont chaque sommet correspondra à une situation autorisée.
Par exemple, le sommet "(MP/FH)" signifie que sur une rive se trouvent le Mazgueul et le Passeur (qui s'apprête à le faire traverser dans sa barque), tandis que sur la seconde rive se trouvent le Hobbyt et le Forfadais.
Par contre, les situations "(HM/FP)" ou "(HP/FM)" sont interdites car alors le Mazgueul dévorerait dans le premier cas le Hobbyt et dans le second cas le Fofadais.
La situation initiale est ainsi modélisé par le sommet "(FHMP/)" et la situation finale recherchée est "(/FHMP)"

Code de déblocage de la correction :

Vous êtes un.e agent travaillant pour les services secrets français. Votre nom de code est :

Êtes-vous prêt.e.s à partir de nouveau en mission ? Si oui, saisissez votre code secret vous permettant d'accéder aux informations secrètes de cette nouvelle mission.

Entrez votre code secret si vous acceptez de partir dans une nouvelle mission :

Savoirs et savoirs-faire

  1. le vocabulaire sur les graphes non-orientés (ordre, sommets adjacents, degré, chaîne, longueur, connexe, complet),

  2. le vocabulaire sur les graphes orientés (arc, degré),

  3. la notion de matrice d'adjacence.

  1. modéliser un problème concret à l'aide d'un graphe,

  2. écrire la mtrice d'adjacence associée à un graphe.

Licence Creative Commons
Les différents auteurs mettent l'ensemble du site à disposition selon les termes de la licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International