Exemples standards
Voici quelques exemples de graphes non orientés.
Définition
Soit \( n\in \N\) .
- \( (i)\)
- Si \( n{>}0\) , la clique standard à \( n\) sommets est le graphe \( \Kk_n\) défini par
\[\Som(\Kk_n)=\{1,\cdots,n\},\qquad \Ar(\Kk_n)=\left\{I\subseteq \Som(\G)\Big| \Card(I)=2\right\}\]
- \( (ii)\)
- La chaîne standard à \( n\) arêtes est le graphe \( \Cc_n\) défini par
\[\Som(\Cc_n)=\{0,\cdots,n\}\qquad \Ar(\Cc_n)=\left\{\{i-1,i\}\Big | i\in \{1,\cdots,n\}\right\}\]
- \( (iii)\)
- Si \( n{>}2\) le cycle standard à \( n\) sommets est le graphe \( \Zz_n\) défini par
\[\Som(\Zz_n)=\{0,\cdots,n-1\}\qquad \Ar(\Zz_n)=\left\{\{i-1,i\}\Big | i\in \{1,\cdots,n-1\}\right\}\cup\left\{\{n-1,0\}\right\}\]
\[
\xymatrix{1}
\]
\[\Kk_1\]
\[
\xymatrix{1\ar@{-}[r]&2}
\]
\[\Kk_2\]
\[
\xymatrix{&1\ar@{-}[rd]\ar@{-}[ld]&\\
3\ar@{-}[rr]&&2}
\]
\[\Kk_3\]
\[
\xymatrix{
1
\ar@{-}[r]\ar@{-}[rd]\ar@{-}[d]&
2\ar@{-}[d]\ar@{-}[ld]\\
4\ar@{-}[r]&
3
}
\]
\[\Kk_4\]
\[
\xymatrix{0}
\]
\[\Cc_0\]
\[
\xymatrix{0\ar@{-}[r]&1}
\]
\[\Cc_1\]
\[
\xymatrix{0\ar@{-}[r]&1\ar@{-}[r]&2}
\]
\[\Cc_2\]
\[
\xymatrix{0\ar@{-}[r]&1\ar@{-}[r]&2\ar@{-}[r]&3}
\]
\[\Cc_3\]
\[
\xymatrix@R=1.2cm@C=1.2cm{&0\ar@{-}[rd]\ar@{-}[ld]&\\
2\ar@{-}[rr]&&1}
\]
\[\Zz_3\]
\[
\xymatrix@R=1.2cm@C=1.2cm{0\ar@{-}[r]\ar@{-}[d]&1\ar@{-}[d]\\
3\ar@{-}[r]&2}
\]
\[\Zz_4\]
\[
\xymatrix@R=1.2cm@C=0.5cm{
&&0\ar@{-}[rrd]\ar@{-}[lld]&&\\
4\ar@{-}[rd]&&&&1\ar@{-}[ld]\\
&3\ar@{-}[rr]&&2&
}
\]
\[\Zz_5\]
Ces graphes ont leur analogues dans le cas orienté.
Définition
Soit \( n\in \N\) .
- \( (i)\)
- Si \( n{>}0\) , la clique standard orienté à \( n\) sommets est le graphe, également noté \( \Kk_n\) , défini par
\[\Som(\Kk_n)=\{1,\cdots,n\},\qquad \Arc(\Kk_n)=\Som(\G)\times\Som(\G)\]
- \( (ii)\)
- La chaîne standard orienté à \( n\) arêtes est le graphe, également noté \( \Cc_n\) , défini par
\[\Som(\Cc_n)=\{0,\cdots,n\}\qquad \Arc(\Cc_n)=\left\{(i-1,i)\Big | i \in \{1,\cdots,n\}\right\}\]
- \( (iii)\)
- Si \( n{>}2\) le cycle standard orienté à \( n\) sommets est le graphe, également noté \( \Zz_n\) , défini par
\[\Som(\Zz_n)=\{0,\cdots,n-1\}\qquad \Arc(\Zz_n)=\left\{(i-1,i)\Big | i\in \{1,\cdots,n-1\}\right\}\cup\left\{(n-1,0)\right\}\]
\[
\xymatrix{1\ar@(ul,ur)[]}
\]
\[\Kk_1\]
\[
\xymatrix{1\ar@(dl,ul)[]\ar@/^1pc/[r]&2\ar@/^1pc/[l]\ar@(dr,ur)[]}
\]
\[\Kk_2\]
\[
\xymatrix{
&1\ar@(ul,ur)[]\ar@/^1pc/[rd]\ar@{{<}-}@/_1pc/[rd]\ar@/^1pc/[ld]\ar@{{<}-}@/_1pc/[ld]&\\
3\ar@(dl,ul)[]\ar@/^1pc/[rr]\ar@{{<}-}@/_1pc/[rr]&&2\ar@(dr,ur)[]}
\]
\[\Kk_3\]
\[
\xymatrix{
1\ar@(ul,ur)[]\ar@/_1pc/[r]\ar@/_1pc/[rd]\ar@/_1pc/[d]\ar@/^1pc/@{{<}-}[r]\ar@/^1pc/@{{<}-}[rd]\ar@/^1pc/@{{<}-}[d]&
2\ar@(ur,ul)[]\ar@/_1pc/[d]\ar@/_1pc/[ld]\ar@/^1pc/@{{<}-}[d]\ar@/^1pc/@{{<}-}[ld]\\
4\ar@(dl,dr)[]\ar@/_1pc/@/^1pc/[r]\ar@/^1pc/@{{<}-}[r]&
3\ar@(dr,dl)[]}
\]
\[\Kk_4\]
\[
\xymatrix{0}
\]
\[\Cc_0\]
\[
\xymatrix{0\ar[r]&1}
\]
\[\Cc_1\]
\[
\xymatrix{0\ar[r]&1\ar[r]&2}
\]
\[\Cc_2\]
\[
\xymatrix{0\ar[r]&1\ar[r]&2\ar[r]&3}
\]
\[\Cc_3\]
\[
\xymatrix@R=1.2cm@C=1.2cm{&0\ar[rd]\ar@{{<}-}[ld]&\\
2\ar@{{<}-}[rr]&&1}
\]
\[\Zz_3\]
\[
\xymatrix@R=1.2cm@C=1.2cm{0\ar[r]\ar@{{<}-}[d]&1\ar[d]\\
3\ar@{{<}-}[r]&2}
\]
\[\Zz_4\]
\[
\xymatrix@R=1.2cm@C=0.5cm{
&&0\ar[rrd]\ar@{{<}-}[lld]&&\\
4\ar@{{<}-}[rd]&&&&1\ar[ld]\\
&3\ar@{{<}-}[rr]&&2&
}
\]
\[\Zz_5\]
Il existe un type de graphe qui est à la fois orienté et non orienté.
Définition
Soit \( n\in \N_{{>}0}\) . Le stable standard à \( n\) sommets est le graphe \( \Ss_n\) défini par
\[\Som(\Ss_n)=\left\{1,\dots,n\right\},\qquad\Ar(\Ss_n)=\Arc(\Ss_n)=\varnothing\]
Le stable standard est simplement représenté par ses sommets.