[PDF] [PDF] Algorithmique des graphes - Cours 1 – Introduction - LaBRI

View - Download [PDF] Algorithmique des graphes - Cours 1 – Introduction - LaBRI

Previous PDF

Next PDF

Algorithmique des graphes

Cours 1 - Introduction

František Kardoš

frantisek.kardos@u-bordeaux.fr

Organisation de l"UE

121h20 de cours

122h40 de TDDS le 4 novembre (semaine 45)

examen mi-décembre (semaine 50 ou 51)groupe 1 : Olivier Delmas groupe 2 : Olivier Baudon groupe 3 : Giuliana Bianchi groupe 4 : Mohamed Lamine Lamali groupe 5 : Adrien Boussicault groupe MI + CMI : Antoine Laumondwww.labri.fr/perso/fkardos

Organisation de l"UE

121h20 de cours

122h40 de TDDS le 4 novembre (semaine 45)

examen mi-décembre (semaine 50 ou 51)groupe 1 : Olivier Delmas groupe 2 : Olivier Baudon groupe 3 : Giuliana Bianchi groupe 4 : Mohamed Lamine Lamali groupe 5 : Adrien Boussicault groupe MI + CMI : Antoine Laumondwww.labri.fr/perso/fkardos

Organisation de l"UE

121h20 de cours

122h40 de TDDS le 4 novembre (semaine 45)

examen mi-décembre (semaine 50 ou 51)groupe 1 : Olivier Delmas groupe 2 : Olivier Baudon groupe 3 : Giuliana Bianchi groupe 4 : Mohamed Lamine Lamali groupe 5 : Adrien Boussicault groupe MI + CMI : Antoine Laumondwww.labri.fr/perso/fkardos

Organisation de l"UE

121h20 de cours

122h40 de TDDS le 4 novembre (semaine 45)

examen mi-décembre (semaine 50 ou 51)groupe 1 : Olivier Delmas groupe 2 : Olivier Baudon groupe 3 : Giuliana Bianchi groupe 4 : Mohamed Lamine Lamali groupe 5 : Adrien Boussicault groupe MI + CMI : Antoine Laumondwww.labri.fr/perso/fkardos

Contenu de l"UE

I graphes et leurs représentations I algorithmes d"exploration I parcours en largeur

Iparcours en profondeur

I algorithmes d"optimisation I arbre couvrant le moins cher

Icalcul de distances (plus cours chemin)

Ioptimisation de flots

I complexité d"algorithmes

Qu"est-ce qu"un graphe?

Qu"est-ce qu"un graphe?

Qu"est-ce qu"un graphe?

Graphes - définitions

Un grapheG= (V;E)est un couple d"ensembles finis, dont I

Vest l"ensemble desommetsdeG(représentant des

objets), et I

Eest l"ensemble d"arêtesdeG(représenant des

liens/relations entre des objets). Une arête relie deux sommets (pas nécessairement distincts). Si l"arêteerelie les sommetsuetv, on écrite=uv, on dit que uetvsontvoisinsouadjacents.

Graphes - définitions

Pour un grapheG, on note

I

V(G)l"ensemble des sommets deG

I n=jV(G)jle nombre de sommets deG- l"ordredeG I

E(G)l"ensemble des arêtes deG

I m=jE(G)jle nombre d"arêtes deG- latailledeG

Graphes - définitions

Une arête reliant un sommet à lui-même est uneboucle. Des arêtes reliant la même paire de sommets sont des arêtes parallèles (des arêtes multiples).

Un graphe est ditsimples"il n"a ni boucles ni arêtes multiples.Y a-t-il un graphe simple parmi ces deux-ci?

Graphes - définitions

Une arête reliant un sommet à lui-même est uneboucle. Des arêtes reliant la même paire de sommets sont des arêtes parallèles (des arêtes multiples).

Un graphe est ditsimples"il n"a ni boucles ni arêtes multiples.Y a-t-il un graphe simple parmi ces deux-ci?

Graphes - représentations

I Les listes d"adjacence : pour chaque sommet du graphe la liste de ses voisins;A B C D

EA: [B;C;C]

B: [A;D;E]

C: [A;A;D]

D: [B;C;E]

E: [B;D;E;E]

Graphes - représentations

I Les listes d"adjacence : pour chaque sommet du graphe la liste de ses voisins; I La matrice d"adjacence : pour chaque paire de sommets il est indiqué s"ils sont voisins ou pas;v5v 1 v 2 v 3v4v

1v2v3v4v5v

10 1 1 0 1

v

21 0 1 0 1

v

31 1 0 1 0

v

40 0 1 0 1

v

51 1 0 1 0

Graphes - représentations

I Les listes d"adjacence : pour chaque sommet du graphe la liste de ses voisins; I La matrice d"adjacence : pour chaque paire de sommets il est indiqué s"ils sont voisins ou pas; I La matrice d"incidence : pour chaque sommet et pour chaque arête il est indiqué s"ils sont incidents ou pas.v5v 1 v 2 v 3v4e

1e2e3e4e5e6e7v

11 1 1 0 0 0 0

v

21 0 0 1 1 0 0

v

30 1 0 1 0 1 0

v

40 0 0 0 0 1 1

v

50 0 1 0 1 0 1

Degrés

Ledegré deg(v)d"un sommetvest la longueur de la liste d"adjacence dev. Dans un graphe simple,deg(v)est égal au nombre d"arêtes qui lui sont incidentes.e

1e2e3e4e5e6e7v

11 1 1 0 0 0 0

v

21 0 0 1 1 0 0

v

30 1 0 1 0 1 0

v

40 0 0 0 0 1 1

v

50 0 1 0 1 0 1

Quel est le degré dev2?

Degrés

Ledegré deg(v)d"un sommetvest la longueur de la liste d"adjacence dev. Dans un graphe simple,deg(v)est égal au nombre d"arêtes qui lui sont incidentes.e

1e2e3e4e5e6e7v

11 1 1 0 0 0 0

v

21 0 0 1 1 0 0

v

30 1 0 1 0 1 0

v

40 0 0 0 0 1 1

v

50 0 1 0 1 0 1

Quel est le degré dev2?

Degrés

Théorème (lemme des poignées de main)

Soit G un graphe. La somme des degrés de sommets de G est

égale au double du nombre d"arêtes de G :

X v2V(G)deg(v) =2 jE(G)j:Démo.(par double comptage) Posons sur chaque sommet du graphe autant de jetons que son degré. Il y aP v2V(G)deg(v)de jetons au total.Tout sommet passe un jeton à toute arête incidente.

Chaque arête reçoit deux jetons.

Il y a donc 2mjetons, d"où l"égalité.

Degrés

Théorème (lemme des poignées de main)

Soit G un graphe. La somme des degrés de sommets de G est

égale au double du nombre d"arêtes de G :

X v2V(G)deg(v) =2 jE(G)j:Démo.(par double comptage) Posons sur chaque sommet du graphe autant de jetons que son degré. Il y aP v2V(G)deg(v)de jetons au total.Tout sommet passe un jeton à toute arête incidente.

Chaque arête reçoit deux jetons.

Il y a donc 2mjetons, d"où l"égalité.

Degrés

Théorème (lemme des poignées de main)

Soit G un graphe. La somme des degrés de sommets de G est

égale au double du nombre d"arêtes de G :

X v2V(G)deg(v) =2 jE(G)j:Démo.(par double comptage) Posons sur chaque sommet du graphe autant de jetons que son degré. Il y aP v2V(G)deg(v)de jetons au total.Tout sommet passe un jeton à toute arête incidente.

Chaque arête reçoit deux jetons.

Il y a donc 2mjetons, d"où l"égalité.

Degrés

Théorème (lemme des poignées de main)

Soit G un graphe. La somme des degrés de sommets de G est

égale au double du nombre d"arêtes de G :

X v2V(G)deg(v) =2 jE(G)j:Démo.(par double comptage) Posons sur chaque sommet du graphe autant de jetons que son degré. Il y aP v2V(G)deg(v)de jetons au total.Tout sommet passe un jeton à toute arête incidente.

Chaque arête reçoit deux jetons.

quotesdbs_dbs4.pdfusesText_8

[PDF] graphe sans circuit

[PDF] graphes et algorithmes gondran minoux pdf

[PDF] algorithme des graphes exercices corrigés

[PDF] les graphes en c openclassroom

[PDF] algorithme de recherche des composantes connexes d'un graphe

[PDF] algorithme composante connexe graphe

[PDF] théorie des graphes livre gratuit

[PDF] suite graphique théorie des graphes

[PDF] histoire de la théorie des graphes

[PDF] théorie des graphes cours et exercices corrigés

[PDF] le gone du chaaba analyse

[PDF] le gone du chaaba azouz begag commentaire

[PDF] les différentes théories des organisations

[PDF] théorie des organisations résumé

[PDF] le gone du chaaba texte intégral