TNSI : Vocabulaire des Graphes Non Orientés⚓︎

Arêtes⚓︎

Arêtes

Les liens entre sommets s'appellent des Arêtes ou Edges
On notera \(E=\{\text{couples }\{s,v\} \text{ non ordonnés, pour tous les sommets} \,\, s \,\, \text{et} \,\, v \,\, \text{du Graphe}\}\) l'ensemble des arêtes d'un graphe
Notation : l'arête \(\{s,v\}\) sera quelquefois notée s -- v
L'arête s -- v est dite incidente au sommet s (et à v)

Remarque

La notation mathématique pour un ensemble \(\{s,v\}\) de deux éléments, ne tient pas compte de l'ordre de s et v, ainsi par ex. \(\{1,2\} = \{2,1\}\)
en Python, cela peut être implémenté avec le type set

Une boucle ou loop est une arête d'un sommet vers lui-même

Sommets Adjacents⚓︎

Sommets Adjacents

Deux sommets s et v sont adjacents s'il existe une arête de s vers v (donc aussi de v vers s)

Degré d'un Sommet⚓︎

Degré d'un Sommet

Le Degré d'un Sommet s, noté \(deg(s)\) ou \(d(s)\), est le nombre d'arêtes incidentes à ce Sommet (=nombre d'arêtes Sortantes / Entrantes).
ATTENTION Une boucle compte pour \(2\)

Degré dans un graphe Simple

Un Graphe Simple

Le degré de \(0\) vaut \(3\): \(deg(0) = d(0) = 3\)
Le degré de \(1\) vaut \(3\): \(deg(1) = d(1) = 3\)
Le degré de \(2\) vaut \(2\): \(deg(2) = d(2) = 2\)
Le degré de \(3\) vaut \(2\): \(deg(3) = d(3) = 2\)
Le degré de \(4\) vaut \(2\): \(deg(4) = d(4) = 2\)

Degré dans un Multigraphe

Un Graphe Non Pondéré
Non Orienté
Multigraphe (avec boucles)

Le degré de \(0\) vaut \(6\): \(d(0) = 6\)
Le degré de \(1\) vaut \(5\): \(d(1) = 5\)
Le degré de \(2\) vaut \(6\): \(d(2) = 6\)
Le degré de \(3\) vaut \(2\): \(d(3) = 2\)
Le degré de \(4\) vaut \(3\): \(d(4) = 3\)

Degré Maximal d'un Graphe Simple

On considère un graphe simple \(G\), d'ordre \(n\). Quel est le degré maximal d'un sommet \(s\)?

Lemme des Poignées de main

Montrer que la somme des degrés de tous les sommets est un nombre pair : Plus précisément, La somme des degrés de tous les sommets vaut le double du nombre total d'arêtes : \(\displaystyle \sum_{s\in V} d(s) = 2a = 2\times |E|\) Autrement dit: si \(n=ordre(G)=|V|\) désigne son nombre de sommets: \(\displaystyle \sum_{i=1}^{n} d(s_i)=2a\)
Le nombre de sommets de degré impair est pair

Chaînes⚓︎

Définition⚓︎

Chaînes

Une Chaîne de
Longueur 3

Une Chaîne de s à v est une suite (finie) d'arêtes consécutives, reliant s à v, sur un graphe non orienté.

Chaîne de 0 à 4

noté 0-2-1-4 est une chaîne de longueur 3

Longueur d'une Chaîne⚓︎

Longueur d'une Chaîne

La Longueur d'une chaîne est :

le nombre d'arêtes de la chaîne, pour un graphe non pondéré, ou bien,
la somme des poids des arêtes, pour un graphe pondéré

Remarque Il n'y a (en général) évidemment pas unicité de la chaîne d'un même point de départ à un même point d'arrivée :

\(0 - 3 - 1 - 4\) est une autre chaîne de \(0\) à \(4\), de longueur \(3\)
\(0 - 4\) est une autre chaîne de \(0\) à \(4\), de longueur \(1\) : c'est une arête !

Distance entre deux sommets⚓︎

Distance

La distance entre deux sommets est la plus courte longueur entre eux (parmi toutes les chaînes possibles entre eux)

Chaînes Simples, Chaînes Élémentaires⚓︎

Chaînes Simples

Une Chaîne simple est une chaîne :

ne passant pas deux fois par la même arête
\(\Leftrightarrow\) dont toutes les arêtes sont distinctes

Chaînes Élémentaires

Une Chaîne élémentaire est une chaîne :

ne passant pas deux fois par le même sommet
\(\Leftrightarrow\) dont tous les sommets sont distincts

sauf peut-être les deux extrémités

Cycles⚓︎

Définition⚓︎

Cycles

Un autre Cycle

Un Cycle

Un Cycle est une chaîne menant d'un sommet à lui-même.

Exp

\(0-3-1-2-0\) est un cycle de longueur \(4\)

Graphe Acyclique

Un graphe sans aucun cycle est un graphe acyclique

Longueur d'un Cycle⚓︎

Longueur d'un Cycle

La Longueur du cycle est la longueur de sa chaîne sous-jacente.

Cycles Simples, Cycles Élémentaires⚓︎

Cycles Simples

Un Cycle simple est un cycle :

dont la chaîne est simple
\(\Leftrightarrow\) ne passant pas deux fois par la même arête, càd
\(\Leftrightarrow\) dont toutes les arêtes sont distinctes

Cycles Élémentaires

Un Cycle élémentaire est un cycle :

dont la chaîne est élémentaire
\(\Leftrightarrow\) ne passant pas deux fois par le même sommet, càd
\(\Leftrightarrow\) dont tous les sommets sont distincts

sauf les deux extrémités qui sont égales...

Pte

Un cycle élémentaire ne contient pas d'autre cycle
Un cycle élémentaire n'admet que des sommets d'ordre \(2\)

Graphe Connexe⚓︎

Connexité

Graphe NON Connexe,
et un Cycle 0 - 1 - 4 - 0

Graphe Connexe

Un graphe non orienté en un seul morceau, est appelé un graphe connexe

Pte

Un graphe non orienté est connexe \(\Leftrightarrow\) Il existe toujours une chaîne entre deux sommets quelconques du graphe

Exemple le graphe d'internet est connexe, mais pas le graphe du réseau routier mondial n'est PAS connexe

Composantes Connexes d'un Graphe⚓︎

Composante Connexe

Lorsque le graphe non orienté est composé de plusieurs morceaux, chaque morceau est appelé une composante connexe du graphe.

Pte

Chaque composante connexe est connexe
Deux sommets quelconques d'une composante connexe sont toujours connectés (reliables par une chaîne)
Toute Chaîne est connexe

Illustrations⚓︎

Graphe G Non Orienté Non Pondéré Non Connexe
et Une Chaîne de 2 à 10 de longueur 5

Graphe G Non Orienté Pondéré Non Connexe
et Une Chaîne de 2 à 10, de poids total =5+0,8+2+4+5=16,8

Arbres⚓︎

Arbres

Un Arbre est un graphe connexe acyclique

un Arbre