23 lines
1.1 KiB
Markdown
23 lines
1.1 KiB
Markdown
up:: [[graphe non orienté étiquetté]]
|
|
#s/maths/graphes
|
|
|
|
> [!definition] Définition
|
|
> Soit $n \in \mathbb{N}^{*}$ et $\underline{n} = [\![1;n]\!]$
|
|
> Soit $X = \mathscr{P}_{2}(\underline{n})$ l'[[ensemble des parties à n éléments d'un ensemble|ensemble des parties à 2 éléments]] de $\underline{n}$
|
|
> Soit $\mathcal{G}_{n} = \{ 0, 1 \}^{X}$ l'ensemble des [[graphe non orienté étiquetté|graphes non orientés]] à $n$ sommets
|
|
> Soit $\mathfrak{S}_{n}$ l'ensemble des [[permutation|permutations]] de $n$ éléments
|
|
> Soit l'opération :
|
|
> $\begin{align} \mathcal{G}_{n} \times \mathfrak{S}_{n} &\to \mathcal{G}_{n} \\ (\Gamma, \pi) &\mapsto \Gamma^{\pi} \end{align}$
|
|
> avec $\Gamma^{\pi}(\{ i, j \}) := \Gamma(\{ \pi(i), \pi(j) \}),\quad \forall \{ i, j \} \in X$
|
|
> Alors :
|
|
> Les éléments ([[orbite d'un groupe|orbites]]) de $\mathfrak{S}_{n} \backslash\backslash \mathcal{R}_{n, k}$ sont appelés **graphes simples**.
|
|
^definition
|
|
|
|
# Propriétés
|
|
|
|
> [!proposition]+ graphes simples et [[isomorphisme de graphes]]
|
|
> Les graphes simples sont les classes d'équivalences pour la relation d'[[isomorphisme de graphes]].
|
|
|
|
# Exemples
|
|
|