Quelques éléments mathématiques
pour les graphes
[email protected]
Notion de relation
● Relation R binaire entre
deux ensembles:
● A = {a, b, c}
● B = {f, g, h, i}
● Une représentation
graphique appelée graphe
de la relation (sous-
ensemble du produit
cartésien A x B)
● G = {(a,g), (a,h), (b,f)}
Vocabulaire (1)
● Application :
● De chaque sommet de l'ensemble de départ, il part
un arc et un seul
● Application surjective :
● A chaque sommet de l'ensemble d'arrivée, il arrive
au moins un arc (Γ-(x) ≥ 1)
● Application injective :
● A chaque élément de l'ensemble d'arrivée, il arrive
au plus un arc (Γ-(x) ≤ 1)
● Application bijective :
● Injective et surjective (un et un seul) (Γ-(x) = 1)
Propriétés
● Réflexive (boucle)
● ∀ x ∈ A, xRx
● Irréflexive (pas de boucle)
● ∀ x ∈ A, ¬(x R x)
● Symétrique (passage de non-orienté → orienté)
● ∀ x, y ∈ A2, x R y => y R x
● Anti-symétrique
● ∀ x, y ∈ A2, x R y ∧ y R x => x = y
● Transitive (calcul de chemin)
● ∀ x, y, z ∈ A3, x R y ∧ y R z => x R z
Propriétés (2)
● Ordre
● Partiel strict : transitive et anti-symétrique
– Exemple : x < y => ¬(y < x) x < y ∧ y < z => x < z
● Total
– Exemple : x < y ∨ y < x
– valable pour les entiers mais pas les complexes
● Partitions
● P = { X1, X2, ..., Xn}
● X1 ∪ X2 ∪ … ∪ Xn = A
● ∀ i, j, i≠ j, Xi ∩ Xj = ∅
Composition/inverse de relation
● Départ : Matrice d'adjacence (binaire)
● Composition de relation (o) → produit matriciel
(x) avec l'algèbre de Boole
● Mc = Mr2 o r1 = Mr1 x Mr2
● Réciproque de relation (r) → transposée
● Mr = t M
Numérique
● ∑ d-(x) = ∑ d+(x) = m
● ∑ d(x) = 2 * m
Numérique
● Nombre chromatique (γ(G))
● Graphe sans boucle, effectue une partition en stables
● γ(G) d'un graphe planaire est au plus de 4
● n : ordre du graphe (|G|)
● α(G) : le cardinal du plus grand stable
● r : degré maximal d'un noeud du graphe
● n / α(G) ≤ γ(G) ≤ r + 1
n = 3, α(G) = 2, γ(G) = 2, r = 2
Cycles (Représentation)
● Graphe avec m arcs orientés
● Vecteur à m dimensions (a1, ..., am)
● μ+ : {arcs pris dans le sens}
● μ- : {arcs pris à contresens}
● Cycle : vecteur à m dimensions
● +1 si ai ∈ μ+ / -1 si ai ∈ μ- / 0 si ai ∉ μ+ ∪ μ-
● Indépendances de p vecteurs
● λ1 μ1 + … + λp μp = 0 => ∀ i= 1, .. p, λi = 0
Cycles (propriétés)
● Base de cycles :
● Ensemble minimal de cycles indépendants tel que
tout vecteur représentant un cycle du graphe
s'exprime comme combinaison linéaire de cycles de
la base
● Dimension de la base : nombre cyclomatique (ν(G))
● n sommets, m arcs, p composantes connexes
ν(G) = m – n + p
Complexité
● Dijkstra :
●
Principe : |X|2
● Optimisation : (|X| + |U|) * log |X|
● Sans cycle :
●
Principe : (|X| + |U|)2
Formules
● Multi-graphe orienté, fini, connexe a un circuit
Eulérien <=> ∀ x ∈ X d+(x) = d-(x)
● Multi-graphe orienté, fini connexe a un chemin
Eulérien <=>
● ∀ x ∈ X - {x0, x1} d+(x) = d-(x)
● d+(x0) = d-(x0) + 1
● d-(x1) = d+(x1) + 1
Formules (2)
● G non orienté
● G admet un cycle Eulérien <=> ∀ x ∈ U, ∃ k ∈ N /
d(x) = 2k
Formules (2)
● Graphe G orienté, simple / ∀ x ∈ X d+(x) = d-(x)
● G est fortement connexe <=> G connexe
● Dem : il possède un circuit Eulérien donc il est
fortement connexe
● Graphe G orienté, simple
● G sans cycle <=> ∃ x / d-(x) = 0 ∧ ∀ x / d-(x) = 0 G –
{x} est sans cycle
Jeux
● Modélisation par graphes acycliques :
● Pas de retour arrière, modélisation par des états
● Noyau unique
● Exemples :
● Marienbad : celui qui commence perd obligatoirement
– De l'ordre de 400 noeuds, noyau : 48 noeuds
● Morpion : celui qui commence est sur de ne pas
perdre (ne signifie pas gagner !)
– De l'ordre de 600 000 noeuds (sans optimisation)
● Puissance 4 : …
