40 lines
1.2 KiB
Markdown
40 lines
1.2 KiB
Markdown
---
|
|
aliases:
|
|
- graphes non orientés
|
|
---
|
|
up:: [[graphe]]
|
|
#s/maths/graphes
|
|
|
|
> [!definition] Définition
|
|
> Soit $n \in \mathbb{N}^{*}$
|
|
> Soit $\underline{n} = [\![1; n]\!]$
|
|
> Soit $X = \mathscr{P}_{2}(\underline{n})$ l'[[ensemble des parties à n éléments d'un ensemble]]
|
|
> On définit $\mathcal{G}_{n}$ l'**ensemble des graphes non-orientés à $n$ sommets** comme :
|
|
> $\mathcal{G}_{n} := \{ 0, 1 \}^{X}$
|
|
> Un **graphe non orienté** est alors une fonction de $X \to \{ 0, 1 \}$
|
|
^definition
|
|
|
|
```breadcrumbs
|
|
title: "Sous-notes"
|
|
type: tree
|
|
collapse: false
|
|
show-attributes: [field]
|
|
field-groups: [downs]
|
|
depth: [0, 0]
|
|
```
|
|
|
|
# Propriétés
|
|
|
|
> [!proposition]+ Ensemble des arrêtes
|
|
> Soit $\Gamma \in \mathcal{G_{n}} = \{ 0, 1 \}^{X}$ un graphe.
|
|
> On définit l'ensemble de ses arrêtes comme :
|
|
> $\begin{align} E &:= \{ e \in X \mid \Gamma(e)=1 \} \\&= \left\{ (i, j) \in \underline{n}^{2} \middle| i\neq j \wedge \Gamma(\{ i, j \}) = 1 \right\} \end{align}$
|
|
|
|
> [!proposition]+ degré
|
|
> Le degré d'un noeud $i \in \underline{n}$ est défini comme :
|
|
> $\displaystyle \operatorname{deg}(i) = \operatorname{deg}_{\Gamma}(i) := \sum\limits_{\substack{j \in \underline{n}\\ i\neq j}} \Gamma(\{ i, j \})$
|
|
|
|
|
|
# Exemples
|
|
|