Dans un graphe planaire topologique, les zones délimitées par des arêtes qui les entourent sont appelées des « faces ». Par exemple, dans le graphe qui représente la villa des Courtel, on a 6 faces notées de f1 à f6. Notons que le contour extérieur d’un graphe planaire topologique est également une face.
Chaque face a une fronti`ere d´etermin´ee par au moins 4arˆetes. On en tire que 4f ? 2a, i.e.
2f ? a. De la formule d’Euler, 2a?2f =2s?4, on en tire que a? 2s?4. Or, K3,3est un graphe biparti simple qui poss`ede 6sommets et 9 arˆetes. Il ne peut donc pas ˆetre planaire car 9? 2.6?4. Graphes planaires.
d’arˆetes maximales d’un graphe planaire simple en fonction du nombre de sommets. En e?et, en consid´erant aussi le fait qu’une arˆete s´epare toujours deux faces , et en consid´erant que toutes les faces d’un graphe ont au moins trois arˆetes pour pourtour, il d´ecoule que 2e(G) ? 3f, et en remplacant dans la relation, il vient :, A Acyclique graphe ne contenant pas de cycle. Adjacence une liste d’adjacence est une structure de données constituée d’un tableau dont le -ème élément correspond à la liste des voisins du -ème sommet. Adjacence une matrice d’adjacence est une matrice carrée usuellement notée , de dimensions | | × | |, dont chaque élément est égal au nombre d’arêtes incidentes (ayant pour …
Deux autres nombres attaches a un graphe peuvent etre recherches : A(G), epaisseur du graphe G, est le nombre minimal de graphes planaires dont G est Punion. y (G), genre du graphe, est le genre minimal d’une surface orientable sur laquelle il peut etre trace sans que deux de ses aretes ne se coupent (si Ton considere une surface orientable S comme une « sphere munie d’anses.
Tout graphe planaire est 6 colorable. Preuve : Formule d’Euler Pour tout graphe planaire, S A+ F = 2: On a F 2A=3. En re-injectant dans la formule d’Euler on obtient : A 3S 6. Comme P x2S deg(x) = 2A, il existe un sommet de degr e au plus 5. N. Bousquet Coloration de graphes: algorithmes et structures, Un graphe orient´e est un couple (X,U) ou` X est un ensemble de sommets et U est inclus dans X × X r {(x,x) | x ? X}. U est un ensemble d’arcs. On autorise ´egalement parfois les boucles ou arcs multiples. D´e?nitions (Adjacence, incidence, voisinage, degr´e). Deux sommets x et y d’un graphe G = (X,E) sont adjacents si xy ? E.
sommets d’un graphe et un lien entre deux pages est une ar^ete entre ces deux sommets. 1 Dans le parcours en largeur, on utilise une le. On en le le sommet de d epart (on visite la page index du site). 2 On visite les voisins de la t^ete de le (pages cibl ees par la page de, Si v 0 = a et v k = b, on dira que la chaîne relie a et b. En plus, on dira que la chaîne a longueur k (c’est le nombre d’arêtes de la chaîne). Une chaîne doit comporter au moins une arête. Le graphe ci-contre contient par exemple les chaînes (v 1 , e 3, v 3, e 4 ,v 4) et (v 4, e 4, v 3, e 2, v 2, e 1, v 1 ).
