Édition du: 02/04/2023 |
INDEX |
GRAPHES |
||
Faites
un double-clic pour un retour en haut de
page
GRAPHES PLANAIRES Des circuits qui ne se croisent jamais. C'est le cas des circuits imprimés. Le courant doit aller d'un
point à un autre en parcourant une piste sans
croiser une autre piste. Ce n'est pas toujours possible. Il faut alors
ajouter une nouvelle couche de circuits. Le plus simple étant le double-face,
mais certains circuits complexes peuvent compter huit ou dix couches. |
||
|
Sommaire de cette page >>> Approche >>> Définitions >>> Relations >>> Propriétés avancées >>> English corner |
Débutants Glossaire |
Circuits
imprimés multicouches; multilayer printed circuit board
Graphe complet: tous les sommets sont reliés entre eux.
Avec n sommets, le graphe comporte n (n – 1) / 2 arêtes. Graphe k-facteur: chaque sommet ne
reçoit que k arêtes. Graphe planaire: sur un plan, les
arêtes ne se croisent jamais. |
Voir Exemple
et emploi de graphes complets et 1-facteur / Vocabulaire
des graphes
|
||
|
Sommet ou nœud; Arête ou arc. |
|
|
|
|
Le graphe K5 n'est pas planaire. |
|
|
Il est facile de montrer que
K5 est non-planaire. Voyez la figure: il est
impossible de placer le cinquième point (E) dans une région sans qu'une des liaisons
n'en traverse une autre:
|
Autre démonstration >>> |
Voir la célèbre énigme du
Pont de Königsberg
Le
deuxième graphe planaire impossible est le K3,3.
Un exemple est donné par l'énigme des trois maisons. Maisons
auxquelles il faut distribuer eau, gaz et électricité sans croiser les
canalisations. Exemples de graphes complets
Un graphe comme K5 est dit complet: un sommet est relié
à chacun des autres. Il est unique pour tout Kn. Un graphe comme K3, 3 est un graphe biparti complet: un
sommet d'un groupe est relié à chaque sommet de l'autre groupe. |
Voir Nombres
chromatiques
|
||
|
Étant donné un graphe, dès qu'on peut trouver une configuration
planaire, le graphe est planaire. Par contre, dire qu'un graphe n'est pas planaire n'est pas facile.
Jusqu'où faut-il chercher? Quand a-t-on épuisé toutes les possibilités? |
|
|
Autre exemple |
|
La somme de tous les degrés est égale au double du nombre d'arêtes. |
Graphe d'ordre 5 qui comporte cinq faces, sans oublier celle externe. Il a: 1 sommet de degré 2; 2 de
degré 3; 2 de degré 4. |
|
Voir Types de graphes
|
||
Théorème de
Descartes-Euler Pour un graphe planaire connexe
(d'un seul tenant): S
+ F = A + 2 Faces + Sommets = Arêtes +
2.
Relation degrés et faces Pour un graphe quelconque:
Somme des degrés des sommets
= deux fois la quantité d'arêtes. Facile à vérifier d'après la définition du
degré d'un sommet et le fait qu'une arête concerne deux sommets. |
5 faces, 5 sommets et
8 arêtes On vérifie que: 5 + 5
= 8 + 2 Somme degrés: 2 + 3 +
3 + 4 + 4 = 16 Quantité de faces: 8 On vérifie: 16 = 2 x 8
|
|
Chaque face est entourée de
trois arêtes. Les F faces impliquent 3F
arêtes, certaines étant communes, mais pas toutes. D'où l'inégalité indiquée. Avec la relation de
Descartes-Euler. Soit l'inégalité indiquée. Et la conclusion importante. |
F = A + 2 – S Dans un graphe planaire la quantité d'arêtes est inférieure à trois fois
la quantité de sommets |
|
Un graphe complet à cinq
sommets (K5): s'il était planaire, il comporterait moins de 3 x 5 – 6 = 9
arêtes. Or, comptez bien, il y en a
10. Le graphe K5 ne peut pas être planaire. |
|
|
Un graphe planaire connexe
(d'un seul tenant) dont la face la plus petite comporte P arêtes |
La somme des arêtes des faces est égale deux fois la quantité
d'arêtes. Il y en aura au minimum: P.F
Avec la relation de
Descartes-Euler: 2A 2A 2A PA – 2A A(P – 2) |
Un graphe planaire connexe sans
triangle contient au plus: A Sur cet exemple du graphe K3,3, pour deux arêtes
qui partent d'un sommet, il n'y a pas de liaison entre les deux sommets
d'arrivée (pas de triangle). Nous comptons 9 arêtes pour
6 sommets. Or 9 > 12 – 4 = 8. Le graphe K3,3 n'est pas planaire |
Sans triangle, les faces comportent au
moins 4 arêtes. Avec P = 4, la relation précédente devient: 2A |
|
||
Les deux graphes non
planaires (K3,3 et K5) sont caractéristiques de la non-planéarité. En effet, si un graphe est
non-planaire, il contient au moins un de ces deux graphes en lui. |
Théorème de Casimir Kuratowski
(1929) Un graphe est planaire si et seulement si l'on ne peut en extraire
aucun graphe du type K3,3 ou K5. |
|
Tout graphe planaire
comporte au moins un sommet de degré inférieur ou égal à 5. |
|
|
When a
connected graph can be drawn without any edges crossing, it is called planar.
When a planar graph is drawn in this way, it divides the plane into regions
called faces. Euler's
Formula for Planar Graphs: for any
connected planar graph with v vertices,
e edges and f faces, we have: v – e + f = 2. |
Voir
Anglais pour le bac et pour les affaires
Retour |
|
|
Suite |
|
|
Voir |
|
|
Site |
|
|
Livre |
|
|
Cette page |
http://villemin.gerard.free.fr/aMaths/Topologi/aaaGraph/Planaire.htm
|