TNSI : Définitions sur les Graphes Quelconques⚓︎

Graphes⚓︎

Def

Un Graphe $G = (V, E)$ est la donnée de:
un ensemble fini $V$ de Points, ou Sommets ( $V =$ Vertices ), ou Noeuds ou Nodes
un ensemble $E$ de Liens, entre ces points ( $E=$ Edges )
Ces liens font correspondre un sommet de départ $s$ à un sommet d'arrivée $v$

Graphes Non orientés vs Graphes Orientés⚓︎

Graphes Non Orientés

Un Graphe Non Orienté

Lorsque les liens sont symétriques, c'est-à-dire lorsque l'existence d'un lien entre $s$ et $v$ est équivalent à l'existence d'un lien entre $v$ et $s$ :

$s \longrightarrow v \Leftrightarrow v \longrightarrow s$

Alors on dit que:

le graphe est Non Orienté, et
les liens entre les sommets sont appelés des Arêtes, et
les arêtes sont représentées par des traits

Exemple : Arbre 1 : Réseau Internet

Graphes Orientés

Un Graphe Orienté

Lorsque les liens NE sont PAS symétriques, càd lorsqu'il existe au moins une relation non symétrique, Alors on dit que :

le graphe est Orienté, et
les liens entre les sommets sont appelés des Arcs, et
les Arcs sont représentés par des flèches

Exemple : Arbre 2 : Réseau Social

Remarque

Une arête non orientée est équivalente à une double relation d'arcs orientés, donc :

$$\quad \Leftrightarrow \quad$$

Cela signifie qu'un graphe non orienté est un graphe orienté "symétrique", donc un graphe non orienté peut être vu comme un cas particulier de graphe orienté (contrairement à l'intuition ?)

BONUS : Dessiner des Graphes Grâce au Langage DOT⚓︎

graph G { // Graphe Non Orienté
  node [shape=circle]
  c, d [style=bold, color=blue, fontcolor=blue]
  a -- b -- c
  b -- d [label="5"]
  c -- d [label="2", style=bold, color=red, fontcolor=red]
  {rank=same;c;d;}
}

$$\Rightarrow$$

Graphe Non Orienté

digraph G {  // Graphe Orienté
  node [shape=circle]
  c, d [style=bold, color=blue, fontcolor=blue]
  a -> b -> c
  b -> d [label="5"]
  c -> d [label="2", style=bold, color=red, fontcolor=red]
  {rank=same;b;c;}
}

$$\Rightarrow$$

Graphe Orienté

Graphes Simples vs Multigraphes⚓︎

Graphe Simple

Un Graphe Simple

Un Graphe Simple est un graphe qui:

n'admet pas d'arêtes/arcs multiples, ou multi-arêtes/multi-arcs (plusieurs arêtes/arcs entre deux sommets fixés)
n'admet pas de boucle (arête/arc entre un sommet et lui-même)

Multigraphe

Un Multigraphe

Un multigraphe est le contraire d'un graphe simple:

il peut admettre des arêtes/arcs multiples entre deux sommets fixés
il peut admettre des boucles (arêtes/arcs d'un sommet vers lui-même)

Convention Dans la suite de ce cours, sauf mention contraire (par défaut):

Tous les graphes Non Orientés considérés seront des graphes Simples.
Les graphes Orientés pourront quelquefois avoir des boucles, ainsi que plusieurs arcs entre plusieurs sommets

p-graphes (CULTURE : HORS-PROGRAMME)⚓︎

Def

Un p-graphe est un graphe dont le nombre maximum d'arêtes/arcs, entre deux sommets adjacents quelconques, vaut p.

Exp

Un 1-graphe
= Un Graphe Simple

Un 2-graphe

Un 3-graphe

Graphes Pondérés⚓︎

Graphe Pondéré

Un Graphe Pondéré
Orienté

Un Graphe Pondéré
Non Orienté

Des poids / coefficients / valuations peuvent être associés aux arêtes/arcs d'un graphe (orienté ou non).
Par exemple pour modéliser la distance, le temps, la probablité ou les coûts nécessaires pour passer d'un état à un autre.
Un tel graphe est appelé un graphe pondéré. Exemple : Arbre 3 : Le Réseau Routier ci-dessus.

Ordre d'un Graphe⚓︎

Ordre d'un Graphe

L'ordre d'un graphe est son nombre total de sommets/Noeuds.
En général, il est noté $n=ord(G)=|V|$

Taille d'un Graphe⚓︎

Taille d'un Graphe

La taille d'un graphe est son nombre total d'arêtes/arcs.
En général, elle est notée $a=taille(G)=|E|$

Taille Maximale d'un Graphe Simple Non Orienté

On considère un graphe simple $G$ non orienté, d'ordre $n$. Quel est la taille maximale du graphe $G$? Autrement dit, combien d'arêtes au maximum peut-on tracer avec $n$ sommets (une seule arête au maximum entre deux sommets)

Pour $n=2$ sommets,
$a=1$ arête au max.

Pour $n=3$ sommets,
$a=3$ arêtes au max.

Pour $n=4$ sommets,
$a=6$ arêtes au max.