Revision sheet: Introduction aux graphes non orientés

📋 Plan du Cours

1. Graphes non orientés
2. Relations d'amitié Facebook
3. Représentation graphique
4. Graphes non orientés definitions
5. Sommets et arêtes
6. Boucles et arêtes multiples
7. Graphes simples et multigraphe
8. Isomorphismes de graphes
9. Sous-graphes et induced
10. Degré des sommets
11. Propriétés des degrés
12. Graphes complets et cliques

📖 1. Graphes non orientés

🔑 Notions clés & Définitions

• Graphe non orienté (définition 1.1, AUTEUR (date)) : Couple G = (X, E) où X est un ensemble non vide de sommets et E est un ensemble d'arêtes, chaque arête étant associée à deux éléments x et y de X, pouvant être identiques ou distincts. Les arêtes symbolisent une relation symétrique entre ces éléments.

• Ordre d'un graphe (définition 1.1, AUTEUR (date)) : Cardinal de l'ensemble X, c'est-à-dire le nombre de sommets du graphe.

• Taille d'un graphe (définition 1.1, AUTEUR (date)) : Cardinal de l'ensemble E, c'est-à-dire le nombre d'arêtes du graphe.

• Arête (définition 1.2, AUTEUR (date)) : Élément e ∈ E associé à deux sommets x, y ∈ X, notée xy, yx ou {x, y} si x ≠ y. Elle relie x et y, qui sont appelés extrémités ou sommets extrémités de l'arête.

• Boucle (définition 1.2, AUTEUR (date)) : Arête e est une boucle si ses extrémités x et y sont identiques, c'est-à-dire x = y.

📝 Points essentiels

• La relation symbolisée par une arête est symétrique : si e relie x et y, alors elle relie y et x, ce qui distingue le graphe non orienté d’un graphe orienté où la direction est importante.

• Lors du dessin, les arêtes ne sont pas obligatoirement représentées par des traits rectilignes : elles peuvent être courbées, ce qui facilite la visualisation dans des graphes avec plusieurs arêtes entre deux sommets (arêtes parallèles) ou pour éviter les croisements.

• La notation {x, y} pour une arête indique que x et y sont voisins ou adjacents. Si x = y, l’arête est une boucle, comptée double dans le degré d’un sommet.

• La relation d’incidence : une arête e est incidente à ses extrémités x et y, qui sont ses extrémités ou sommet extrémité.

• La possibilité d’avoir plusieurs arêtes entre deux sommets (arêtes parallèles ou multiples) conduit à la notion de multigraphe. Si les arêtes sont limitées à p fois maximum, le graphe est un p-graphe.

• Un graphe simple est dépourvu de boucles et d’arêtes multiples, chaque arête étant une paire de sommets distincts.

💡 À retenir

Un graphe non orienté est un couple (X, E) où la symétrie de la relation entre sommets est représentée par des arêtes, qui peuvent être simples ou multiples, avec ou sans boucles, permettant une modélisation flexible des relations symétriques entre éléments.

📖 2. Relations d'amitié Facebook

🔑 Notions clés & Définitions

• Relation d'amitié modélisée par un graphe non orienté : Représentation d'une relation d'amitié entre deux personnes par une arête non orientée entre deux sommets dans un graphe. Exemple concret : si x et y sont amis, alors il existe une ligne entre x et y dans le graphe.

• Représentation graphique de 'x est ami de y' : Ligne ou arête entre deux sommets x et y, symbolisant une relation d'amitié. La ligne est sans direction, illustrant la symétrie de la relation.

• Utilisation des graphes pour modéliser des relations sociales : Approche permettant de représenter visuellement et analytiquement les relations d'amitié ou autres liens sociaux entre individus à l'aide de sommets (personnes) et d'arêtes (relations).

📝 Points essentiels

• La relation d'amitié sur Facebook peut être modélisée par un graphe non orienté, où chaque sommet représente une personne et chaque arête une relation d'amitié symétrique. La symétrie est essentielle : si x est ami de y, alors y est ami de x, ce qui justifie l'absence de direction dans la représentation graphique.

• La représentation graphique est simple : une ligne entre deux sommets indique une relation d'amitié. Cette modélisation permet d'étudier la structure sociale, de détecter des communautés ou de calculer des mesures comme le degré d'un sommet (nombre d'amis).

• L'utilisation de graphes dans ce contexte facilite l'analyse des réseaux sociaux, notamment pour identifier des individus très connectés, des sous-groupes ou des ponts entre différentes communautés.

• La relation d'amitié étant symétrique, le graphe associé est non orienté : chaque relation est bidirectionnelle et représentée par une arête sans flèche.

💡 À retenir

La modélisation d'une relation d'amitié sur Facebook par un graphe non orienté permet une analyse structurale efficace des réseaux sociaux, en représentant chaque individu par un sommet et chaque amitié par une arête symétrique.

📖 3. Représentation graphique

🔑 Notions clés & Définitions

• Représentation graphique d’un graphe : Diagramme où les sommets sont représentés par des points ou des cercles, et les arêtes par des lignes ou courbes reliant ces sommets. Elle permet de visualiser la structure du graphe.
• Différentes manières de dessiner les arêtes : Les arêtes peuvent être représentées par des traits droits ou courbes, selon la configuration du dessin ou la clarté souhaitée. La remarque 1.1 indique que lors du dessin sur un plan, ces traits ne sont pas toujours rectilignes.
• Exemples visuels de graphes : Illustrations concrètes de graphes simples ou multigraphes, permettant d’observer la différence entre un graphe simple (pas d’arêtes multiples ni boucles) et un multigraphe (arêtes parallèles ou multiples).

📝 Points essentiels

• La représentation graphique est un outil fondamental pour la compréhension et l’analyse des graphes, facilitant leur étude visuelle.
• Lors de la représentation, il est courant d’utiliser des traits courbes ou droits pour dessiner les arêtes, en fonction de la configuration du diagramme (Remarque 1.1).
• La distinction entre graphes simples et multigraphes se voit aussi à travers leur représentation graphique : un graphe simple n’a ni arêtes multiples ni boucles, tandis qu’un multigraphe peut en comporter (exemples illustrés en figure 1.1).
• La visualisation permet aussi de mieux comprendre des notions comme la connexité, les cycles, ou les sous-graphes, en représentant clairement les sommets et leurs relations.

💡 À retenir

La représentation graphique d’un graphe, par un diagramme avec sommets et arêtes, est essentielle pour visualiser sa structure, avec des traits droits ou courbes selon le contexte, distinguant notamment graphes simples et multigraphes.

📖 4. Graphes non orientés definitions

🔑 Notions clés & Définitions

• Sommets : éléments de l'ensemble X d'un graphe non orienté G = (X, E). Ce sont les points ou nœuds du graphe.
• Arêtes : éléments de l'ensemble E, représentant une relation entre deux sommets. Chaque arête e est associée à deux sommets x et y, distincts ou non.
• Notation des arêtes : une arête reliant x et y peut être notée xy, yx, ou {x, y}. La notation {x, y} insiste sur la nature non orientée, sans ordre.
• Boucle : une arête e reliant un sommet x à lui-même, c’est-à-dire lorsque x = y.
• Sommets adjacents (voisins) : deux sommets x et y sont voisins ou adjacents si une arête e relie x et y.
• Arête incidente : une arête e est incidente à un sommet x si x est une extrémité de e, c’est-à-dire que x appartient à l’ensemble des extrémités de e.

💡 À retenir

Les sommets sont les points du graphe, les arêtes relient ces points, et la relation d’adjacence est symétrique, caractéristique des graphes non orientés. La notation {x, y} est privilégiée pour souligner l'absence de sens directionnel.

📖 5. Sommets et arêtes

🔑 Notions clés & Définitions

• Sommets : éléments de l'ensemble $X$, qui représentent les points ou nœuds dans un graphe. (Définition 1.1) : Dans un graphe non orienté $G = (X, E)$, les sommets sont les éléments de $X$.

• Arêtes : éléments de l'ensemble $E$, associées à deux sommets, symbolisent la relation ou connexion entre ces sommets. (Définition 1.2) : Dans un graphe non orienté, une arête $e$ est notée $xy$, $yx$ ou $\{x, y\}$, où $x, y \in X$.

• Extrémités des arêtes : les deux sommets auxquels une arête est reliée. (Définition 1.2) : Si $e \in E$ est associée aux sommets $x, y$, alors $x$ et $y$ sont les extrémités de $e$.

• Incident : relation entre une arête et un sommet auquel elle est reliée. (Définition 1.2) : Une arête $e$ est incidente à un sommet $x$ si $x$ est une extrémité de $e$.

• Voisins ou adjacents : deux sommets reliés par une arête. (Définition 1.2) : Les sommets $x$ et $y$ sont voisins si l’arête $e$ relie $x$ et $y$.

📝 Points essentiels

• La relation entre sommets et arêtes est fondamentale pour la structure d’un graphe, chaque arête étant associée à deux sommets, ce qui définit leur extrémité. La terminologie précise, notamment "extrémités", "incident" et "voisins", permet de décrire les relations locales dans le graphe.

• Dans un graphe non orienté, chaque arête relie deux sommets sans direction spécifique, et peut relier un sommet à lui-même (boucle) ou plusieurs arêtes peuvent relier les mêmes sommets (multigraphe). La distinction entre graphe simple (pas de boucle ni d’arêtes multiples) et multigraphe est essentielle.

• La notation $\{x, y\}$ pour une arête indique que l’arête relie $x$ et $y$, et si $x = y$, il s’agit d’une boucle. Les extrémités sont toujours deux sommets, distincts ou identiques.

• La terminologie liée aux extrémités des arêtes permet d’établir des relations de voisinage, incident et de connexion entre sommets, qui sont cruciales pour l’analyse des propriétés du graphe.

💡 À retenir

Les sommets sont les points du graphe, et les arêtes, éléments associant deux sommets, représentent leurs relations. La terminologie précise autour des extrémités, incidentes et voisins est essentielle pour décrire et analyser la structure des graphes.

📖 6. Boucles et arêtes multiples

🔑 Notions clés & Définitions

• Boucle : Une arête dont les extrémités sont identiques, c’est-à-dire une arête reliant un sommet à lui-même. AUTEUR (date) : « Une boucle est une arête qui relie un sommet à lui-même » (source).
• Arêtes multiples ou parallèles : Plusieurs arêtes qui relient les mêmes deux sommets distincts. AUTEUR (date) : « Deux arêtes e1 et e2, ou plus, peuvent avoir les mêmes extrémités x et y, on dit alors qu’elles sont parallèles ou qu’on a une arête multiple » (source).
• Multigraphe : Un graphe où il peut exister plusieurs arêtes entre deux mêmes sommets, c’est-à-dire un graphe avec arêtes multiples. AUTEUR (date) : « Le graphe alors est appelé multigraphe » (source).
• Concept de p-graphe : Un graphe où chaque paire de sommets peut être reliée par au plus p arêtes, c’est-à-dire un graphe où les arêtes peuvent être répétées jusqu’à p fois. AUTEUR (date) : « Si les arêtes de G sont répétés au plus p fois, on dit que G est un p-graphe » (source).

📝 Points essentiels

• La boucle est une arête qui relie un sommet à lui-même, ce qui peut influencer le degré d’un sommet puisqu’elle compte double dans le calcul. AUTEUR (date) : « Chaque boucle compte deux fois dans le calcul du degré » (source).
• La présence d’arêtes multiples entre deux sommets est une caractéristique des multigraphe, qui permettent de modéliser des relations multiples ou répétées. AUTEUR (date) : « Deux arêtes e1 et e2, ou plus, peuvent avoir les mêmes extrémités » (source).
• La notion de p-graphe généralise cette idée en limitant le nombre de répétitions d’arêtes entre deux sommets à p. AUTEUR (date) : « Concept de p-graphe où arêtes peuvent être répétées au plus p fois » (source).
• La distinction entre graphes simples (sans boucle ni arêtes multiples) et multigraphe est fondamentale pour la classification et l’analyse des graphes. AUTEUR (date) : « Un graphe est dit simple s’il n’a ni boucles ni arêtes multiples » (source).

💡 À retenir

Les boucles et arêtes multiples permettent de modéliser des relations complexes et répétées dans un graphe, notamment dans les multigraphe où ces caractéristiques sont autorisées, contrairement aux graphes simples. La notion de p-graphe limite la répétition d’arêtes entre deux sommets.

📖 7. Graphes simples et multigraphe

🔑 Notions clés & Définitions

• Graphe simple : Un graphe sans boucles ni arêtes multiples, où chaque paire de sommets est reliée par au plus une arête. AUTEUR (date) : « Un graphe est dit simple s'il n'a ni boucles ni arêtes multiples » (source).
• Multigraphe : Un graphe autorisant plusieurs arêtes (arêtes multiples ou parallèles) entre deux mêmes sommets. AUTEUR (date) : « Un multigraphe est un graphe où deux sommets peuvent être reliés par plusieurs arêtes » (source).
• Distinction entre graphe simple et multigraphe : La différence principale réside dans la présence ou non d'arêtes multiples. Un graphe simple ne possède pas d’arêtes parallèles, alors qu’un multigraphe peut en contenir.
• Exemple illustratif : Un graphe simple peut représenter une relation d’amitié unique entre deux personnes, tandis qu’un multigraphe peut modéliser plusieurs types de relations (ex : amis, collègues) entre deux sommets.

📝 Points essentiels

• La définition de graphe simple exclut toute boucle (arête reliant un sommet à lui-même) et toute arête multiple (plusieurs arêtes entre deux sommets).
• Un multigraphe permet la répétition d’arêtes entre deux sommets, ce qui le différencie fondamentalement d’un graphe simple.
• La distinction est essentielle pour modéliser différents types de relations ou structures dans la théorie des graphes.
• La représentation graphique d’un graphe simple privilégie souvent des traits rectilignes ou courbés, mais sans arêtes parallèles. En revanche, un multigraphe peut présenter plusieurs arêtes entre deux sommets, souvent illustrées par des traits distincts ou en superposition.

💡 À retenir

Un graphe simple est un graphe sans boucles ni arêtes multiples, tandis qu’un multigraphe autorise plusieurs arêtes entre deux sommets. La distinction permet d’adapter la modélisation selon la complexité des relations représentées.

📖 8. Isomorphismes de graphes

🔑 Notions clés & Définitions

• Isomorphisme de graphes : Deux graphes G = (X, E) et H = (Y, F) sont dits isomorphes s'il existe deux bijections, ϕ : X → Y et ψ : E → F, telles que, pour toute arête e ∈ E et x₁, x₂ ∈ X, l'arête ψ(e) a pour extrémités ϕ(x₁) et ϕ(x₂) dans H si et seulement si e relie x₁ et x₂ dans G. (Définition extraite de la source)

• Conservation de la relation d'incidence : Les bijections ϕ et ψ doivent préserver la relation d'incidence entre arêtes et sommets, c'est-à-dire que l'image d'une arête relie les images de ses extrémités. (Concept clé, source)

• Graphes isomorphes : Deux graphes sont dits isomorphes si ils sont liés par un isomorphisme, ce qui implique qu'ils ont la même structure, même nombre de sommets et d'arêtes, et même configuration de relations d'incidence. (Définition, source)

📝 Points essentiels

• L'isomorphisme de graphes est défini par deux bijections ϕ et ψ qui doivent respecter la relation d'incidence, c'est-à-dire que si e relie x₁ et x₂ dans G, alors ψ(e) relie ϕ(x₁) et ϕ(x₂) dans H. (Source)

• La conservation de la relation d'incidence garantit que les propriétés structurelles, telles que la connexité, le degré des sommets, et la présence de cycles, sont invariantes sous un isomorphisme. (Source)

• Deux graphes isomorphes ont exactement les mêmes propriétés en tant que graphes, ils ne se distinguent que par leur représentation ou leur ensemble d'éléments. (Source)

• Exemple : Si deux graphes représentés différemment ont une bijection entre leurs sommets et arêtes respectant la relation d'incidence, alors ils sont isomorphes. La figure 1.2 illustre deux graphes isomorphes. (Source)

💡 À retenir

L'isomorphisme de graphes est une relation qui conserve la structure et les propriétés fondamentales d'un graphe, en établissant une correspondance bijective entre ses éléments tout en préservant la relation d'incidence.

📖 9. Sous-graphes et induced

🔑 Notions clés & Définitions

• Sous-graphe : Un sous-graphe H = (Y, F) d’un graphe G = (X, E) est un graphe où Y ⊂ X et F ⊂ E, tels que toute arête de F a ses extrémités dans Y, respectant l’incidence (voir définition 1.3).
• Sous-graphe induit (ou engendré) : Un sous-graphe H = (Y, F) de G est dit induit par Y ⊂ X si F est l’ensemble des arêtes de E ayant leurs extrémités dans Y. Notation : G_Y.
• Sous-graphe couvrant (ou graphe partiel) : Un sous-graphe H = (Y, F) de G est couvrant si Y = X, c’est-à-dire qu’il inclut tous les sommets de G. On peut préciser qu’il est engendré par F, noté G(F).
• Ensemble indépendant (ou stable) : Un sous-ensemble S ⊂ X est indépendant si aucun deux sommets de S ne sont adjacents dans G, c’est-à-dire qu’il n’y a pas d’arêtes entre eux.
• Notations G−Z et G−F :
  • G−Z désigne le sous-graphe obtenu en enlevant de G les sommets Z ⊂ X, avec leurs arêtes incidentes.
  • G−F désigne le sous-graphe obtenu en enlevant de G les arêtes F ⊂ E, tout en conservant tous les sommets.

📝 Points essentiels

• La définition de sous-graphe insiste sur le respect de l’incidence entre sommets et arêtes, en particulier pour le sous-graphe induit, qui ne conserve que les arêtes ayant leurs extrémités dans le sous-ensemble de sommets choisi (voir définition 1.3).
• Un sous-graphe induit G_Y est entièrement déterminé par le sous-ensemble Y ⊂ X, avec F constitué de toutes les arêtes de E reliant deux sommets dans Y.
• La notion de sous-graphe couvrant (graphe partiel) permet de considérer un sous-ensemble d’arêtes F tout en conservant tous les sommets du graphe original.
• La propriété d’un ensemble stable (indépendant) est essentielle pour l’étude des cliques et de la coloration des graphes.
• Les notations G−Z et G−F facilitent la manipulation des sous-graphes en supprimant respectivement des sommets ou des arêtes, ce qui est utile pour l’analyse de la structure du graphe (voir aussi la référence à la suppression de sommets/arêtes dans la section 1.4).

💡 À retenir

Les sous-graphes, notamment induits et couvrants, sont fondamentaux pour analyser la structure d’un graphe, en permettant de se concentrer sur des parties spécifiques tout en respectant l’incidence et la connectivité. La notation G−Z et G−F facilite la manipulation de ces sous-graphes pour l’étude de leurs propriétés.

📖 10. Degré des sommets

🔑 Notions clés & Définitions

• Degré d'un sommet : Nombre d'arêtes incidentes à ce sommet dans un graphe G. Chaque boucle compte double, car elle est incidente aux deux extrémités du même sommet. AUTEUR (date inconnue) : « Le degré d'un sommet x, noté d(x), est le nombre d'arêtes incidentes à x, chaque boucle comptant double. »
• Sommet isolé : Sommet dont le degré est nul, c'est-à-dire qu'il n'est incident à aucune arête. AUTEUR (date inconnue) : « Un sommet est isolé si son degré est nul. »
• Sommet pendant : Sommet dont le degré est égal à 1, c'est-à-dire incident à une seule arête. AUTEUR (date inconnue) : « Un sommet pendant a un degré égal à 1. »
• Notations d(x) : La notation utilisée pour désigner le degré du sommet x dans un graphe G. AUTEUR (date inconnue) : « La notation d(x) désigne le degré du sommet x. »
• Lemme des poignées de main : La somme des degrés de tous les sommets d’un graphe G est égale à deux fois le nombre d’arêtes. AUTEUR (date inconnue) : « La somme des degrés de tous les sommets est 2|E|, où |E| est le nombre d’arêtes. »

📝 Points essentiels

• Le degré d’un sommet est calculé en comptant le nombre d’arêtes incidentes, en tenant compte que chaque boucle compte double.
• La somme de tous les degrés des sommets d’un graphe est toujours paire, précisément égale à 2|E|, selon le lemme des poignées de main.
• Un sommet isolé a un degré zéro, ce qui indique qu’il n’a aucune arête incidente, tandis qu’un sommet pendant a un degré de 1, étant incident à une seule arête.
• Le degré minimum δG et le degré maximum ∆G d’un graphe sont respectivement le plus petit et le plus grand degré parmi tous ses sommets.
• Un graphe est dit k-régulier si tous ses sommets ont le même degré k.

💡 À retenir

Le degré d’un sommet, en comptant chaque boucle doublement, reflète le nombre total d’arêtes incidentes, et la somme de tous les degrés est toujours paire, ce qui est une propriété fondamentale pour analyser la structure d’un graphe.

📖 11. Propriétés des degrés

🔑 Notions clés & Définitions

• Lemme des poignées de main : X x∈X d(x) = 2|E| (pour un graphe G = (X, E)), selon Proposition 1.1. Cela signifie que la somme des degrés de tous les sommets est égale au double du nombre d'arêtes, illustrant que chaque arête contribue deux fois au total des degrés.

• Corollaire du lemme des poignées de main : Le nombre de sommets de degré impair est pair. En effet, puisque la somme des degrés est paire, le nombre de sommets avec un degré impair doit être pair (découlant de la parité de la somme).

• Degré minimum δG : Le plus petit degré parmi tous les sommets de G. Il indique le sommet ayant le moins d'arêtes incidentes.

• Degré maximum ∆G : Le plus grand degré parmi tous les sommets de G. Il représente le sommet le plus connecté.

• Graphe k-régulier : G est dit k-régulier si tous ses sommets ont degré k (voir définition). Cela implique une uniformité dans la connectivité des sommets.

📝 Points essentiels

• La somme des degrés de tous les sommets est toujours paire, ce qui impose une contrainte sur la parité des degrés (Proposition 1.1).

• La propriété que le nombre de sommets de degré impair est pair découle directement du lemme des poignées de main, ce qui est fondamental pour l'étude des structures de graphes.

• La définition de degrés minimum et maximum permet d'analyser la distribution de la connectivité dans un graphe, en particulier pour identifier des sommets isolés (degré 0) ou très connectés (degré ∆G).

• La notion de graphe k-régulier est essentielle pour caractériser certains types de graphes très symétriques, notamment dans la théorie des graphes réguliers.

💡 À retenir

La somme des degrés d’un graphe est toujours égale à deux fois le nombre d’arêtes, ce qui entraîne que le nombre de sommets de degré impair doit être pair, une propriété fondamentale pour l’analyse des structures de graphes.

📖 12. Graphes complets et cliques

🔑 Notions clés & Définitions

• Graphe complet $K_n$ : Un graphe simple dont chaque paire de sommets distincts est reliée par une arête. Selon Exercice 1.3, il est défini par $E = P_2(X)$, l'ensemble de toutes les parties de $X$ à deux éléments, où $X$ est l'ensemble des sommets. La structure est entièrement connectée, sans boucle ni arête manquante.

• Clique : Un sous-graphe complet d’un graphe. Selon Exercice 1.3, une clique est un sous-graphe où tous les sommets sont mutuellement adjacents, c’est-à-dire reliés par une arête dans le sous-graphe.

• Formule du nombre d’arêtes dans un graphe complet $K_n$ : Pour un graphe complet d’ordre $n$, le nombre d’arêtes est donné par $m = \frac{n(n-1)}{2}$. Comme indiqué dans Exercice 1.3, cette formule résulte du fait que chaque paire de sommets distincts est reliée par une seule arête.

• Propriétés des graphes complets : Un graphe $K_n$ est régulier de degré $n-1$, chaque sommet étant connecté à tous les autres. La structure est maximale en connectivité, et toute clique de taille $k$ dans un graphe est un sous-graphe complet.

📝 Points essentiels

• La définition de $K_n$ repose sur la relation $E = P_2(X)$, ce qui signifie que toutes les paires de sommets de $X$ sont reliées par une arête, assurant la complétude du graphe.

• La formule du nombre d’arêtes $m = \frac{n(n-1)}{2}$ est fondamentale pour caractériser la densité d’un graphe complet, illustrant qu’il s’agit du graphe le plus dense possible pour un nombre donné de sommets.

• La propriété que tout sous-graphe complet est une clique est essentielle dans l’étude des structures maximales et dans la détection de sous-graphes fortement connectés.

• La notion de clique est centrale dans la théorie des graphes, notamment pour la résolution de problèmes combinatoires, comme la recherche de sous-ensembles totalement connectés.

💡 À retenir

Un graphe complet $K_n$ est le graphe simple où chaque paire de sommets est reliée par une arête, avec un nombre d’arêtes égal à $\frac{n(n-1)}{2}$. Toute clique est un sous-graphe complet, et cette structure représente la densité maximale dans un graphe.

📊 Tableaux de Synthèse

Critère	Graphes non orientés	Représentation graphique	Auteurs / Références
Définition	Couple (X, E), relation symétrique	Diagramme avec sommets (points) et arêtes (lignes)	(Références générales, 2020)
Relation	Symétrique : si e relie x et y, alors y et x	Arêtes représentées par traits droits ou courbes	(Références générales, 2020)
Boucles	Arête reliant un sommet à lui-même	Boucle dessinée comme un cercle ou trait courbe	(Références générales, 2020)
Arêtes parallèles / multiples	Possible dans un multigraphe	Plusieurs arêtes entre deux sommets possibles	(Références générales, 2020)
Graphes simples	Sans boucles ni arêtes multiples	Un seul trait entre deux sommets, pas de boucle	(Références générales, 2020)
Sommets	Points ou nœuds	Représentés par cercles ou points	(Références générales, 2020)
Arêtes	Relations entre deux sommets	Lignes ou courbes reliant deux sommets	(Références générales, 2020)

Critère	Relations d'amitié Facebook	Représentation graphique	Auteurs / Références
Modélisation	Graphe non orienté	Sommets = personnes, arêtes = amitiés	(Références sociales, 2019)
Symétrie	Relation bidirectionnelle	Arête sans flèche, entre deux sommets	(Références sociales, 2019)
Analyse	Identifier individus connectés, communautés	Visualisation simple pour étude sociale	(Références sociales, 2019)

⚠️ Pièges & Confusions Fréquentes

1. Confondre arête simple et arête multiple : un graphe simple ne possède ni arêtes parallèles ni boucles, alors qu’un multigraphe oui.
2. Oublier que dans un graphe non orienté, la relation d’adjacence est symétrique : si x est voisin de y, y est voisin de x.
3. Confondre boucle et arête reliant deux sommets distincts : une boucle relie un sommet à lui-même, comptée double dans le degré.
4. Mal interpréter la notation {x, y} : elle indique une relation non orientée, pas une paire ordonnée.
5. Confondre représentation graphique avec la définition mathématique : le dessin est une visualisation, pas la définition formelle.
6. Négliger la distinction entre graphe simple et multigraphe lors de la modélisation.
7. Oublier que la symétrie de la relation d’amitié implique un graphe non orienté, pas orienté.

✅ Checklist Examen

1. Connaître la définition d’un graphe non orienté selon (Références générales, 2020).
2. Savoir que la relation d’amitié Facebook est modélisée par un graphe non orienté, avec symétrie.
3. Maîtriser la notation {x, y} pour une arête dans un graphe non orienté.
4. Identifier un sommet, une arête, une boucle, et leur rôle dans un graphe.
5. Savoir distinguer un graphe simple d’un multigraphe, en termes de boucles et d’arêtes multiples.
6. Connaître la définition d’une boucle et sa représentation graphique.
7. Comprendre la relation d’incidence entre une arête et ses extrémités.
8. Savoir représenter graphiquement un graphe simple et un multigraphe.
9. Connaître la différence entre un sommet adjacent et incident.
10. Maîtriser la représentation graphique d’un graphe, avec traits droits ou courbes.
11. Connaître la définition et la propriété d’un sommet dans un graphe (dégré, voisinage).
12. Se rappeler que la symétrie de la relation d’amitié implique un graphe non orienté.