Geek or not

Accueil du site > MOCA > Définitions sur les graphes

Aller à ...

OMFG

Informations

Dans la rubrique MOCA , cet article a été écrit par b3nj et publié le 10 mars 2006.
3950 personnes ont affiché cette page et sa popularité est de 100.

Pebkac

Mots clefs

I see dead pixels.

Outils

SYN

Définitions sur les graphes

Représentation des graphes

Matrice d’adjacence (Graphes orientés)


Matrice d’adjacence: graphes orientés

$G = <X, U>$

Soit $N$ le nombre de sommets et $A$ la matrice d’adjacence $A = \left( a_{ij}\right)$ avec $i \in \left[ 1, N \right]$ et $j \in \left[ 1, N \right]$

Pour compléter la matrice il convient de le faire de la sorte :

$a_{ij} = 1$ si (i,j) $\in$ U $\qquad$ [1]
$a_{ij} = 0$ si (i,j) $\not\in$ U $\qquad$ [2]

	1	2	3	4
1	0	1	1	1
2	0	1	1	1
3	1	0	0	0
4	0	0	1	0

Matrice d’adjacence (Graphes non-orientés)


Matrice d’adjacence: graphes non-orientés

$G = <X, U>$

Soit N le nombre de sommets et A la matrice d’adjacence

$A = \left( a_{ij}\right)$ avec $i \in \left[ 1, N \right]$ et $j \in \left[ 1, N \right]$

Pour compléter la matrice il convient de le faire de la sorte :

$a_{ij} = 1$ et $a_{ji} = 1$ si (i,j) $\in$ U [3]
$a_{ij} = 0$ et $a_{ij} = 0$ si (i,j) $\not\in$ U [4]

	1	2	3	4
1	0	1	1	1
2	1	1	0	0
3	1	0	0	1
4	1	0	1	0

Liste d’adjacence (graphes orientés)


Liste d’adjacence: graphes orientés

$G = $
N est le nombre de sommets
M est le nombre d’arcs

N	1	2	3	4
LP	1	3	5	7	N+1 éléments

M	1	2	3	4	5	6	7
LS	1	3	1	3	1	2	X	M+1 éléments

Méthode :
Les successeurs du sommet i se trouvent entre les indices $LP\left[i\right]$ et $LP\left[i+1\right] -1$ du tableau $LS$

Liste d’adjacence (Graphes non-orientés)


Liste d’adjacence: graphes non-orientés

$G = <X, U>$
N est le nombre de sommets
M est le nombre d’arêtes

N	1	2	3	4
LP	1	3	5	6	N+1 éléments

M	1	2	3	4	5	6
LS	1	2	1	3	2	X	2M+1 éléments

Matrice d’incidence (Graphes orientés)

$G = <X, U>$
N est le nombre de sommets
M est le nombre d’arcs

Soit A la matrice d’incidence :
$A = \left( a_{ij} \right)$ avec $i \in \left[ 1,N \right]$ et $j \in \left[ 1, M \right]$

Pour compléter la matrice il convient de le faire de la sorte :

$a_{ij} = 1$ si $u_{j} \in \omega^{+}\left(i\right)\qquad$ [5]
$a_{ij} = -1$ si $u_{j} \in \omega^{-}\left(i\right)\qquad$ [6]
$a_{ij} = 0$ dans les autres cas


Matrice d’incidence: graphes orientés

Dans ce cas on voit bien que :
$\omega^{+}\left( 1 \right) = \left\lbrace u_{1}, u_{2} \right\rbrace$
$\omega^{-}\left( 1 \right) = \oslash$
$\omega^{+}\left( 2 \right) = \left\lbrace u_{3}, u_{4} \right\rbrace$
$\omega^{-}\left( 2 \right) = \left\lbrace u_{1} \right\rbrace$

Et ainsi de suite on peut remplir la matrice suivante :

	1	2	3	4	5
1	1	1	0	0	0
2	-1	0	1	1	0
3	0	-1	-1	0	1
4	0	0	0	-1	-1

Matrice d’incidence (Graphes non-orientés)

$G = <X, U>$
N est le nombre de sommets
M est le nombre d’arcs

Soit A la matrice d’incidence :
$A = \left( a_{ij} \right)$ avec $i \in \left[ 1,N \right]$ et $j \in \left[ 1, M \right]$

Pour compléter la matrice il convient de le faire de la sorte :

$a_{ij} = 1$ si $u_{j} \in \omega\left(i\right)\qquad$ [7]
$a_{ij} = 0$ dans les autres cas


Matrice d’incidence: graphes non-orientés

$\omega\left(1\right) = \left\lbrace u_{1}, u_{2} \right\rbrace$
$\omega\left(2\right) = \left\lbrace u_{1}, u_{3}, u_{4} \right\rbrace$
$\omega\left(2\right) = \left\lbrace u_{2}, u_{3}, u_{5} \right\rbrace$
$\omega\left(2\right) = \left\lbrace u_{4}, u_{5} \right\rbrace$

	1	2	3	4	5
1	1	1	0	0	0
2	0	0	1	1	0
3	0	1	1	0	1
4	0	0	0	1	1

Faire les exercices : Exercice 2 et Exercice 3

pages : << 1 2 3 4 5 6 7 8

[1] Il faut mettre un 1 s’il existe un arc
[2] Il faut mettre un 0 s’il n’existe pas d’arc
[3] Il faut mettre un 1 s’il existe un arc
[4] Il faut mettre un 0 s’il n’existe pas d’arc
[5] Les arcs partant du sommet i
[6] Les arcs arrivant au sommet i
[7] Les boucles ne comptent pas

Poster un message