NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 29/05/2018

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique       Brèves de Maths    

            

Géométrie

 

Débutants

Géométrie

TOPOLOGIE

 

Glossaire

Géométrie

 

 

INDEX

 

Géométrie

 

Topologie

 

Logique

Index

Introduction

Glossaire

Poincaré

Nœuds

Curiosités

Croisements – Courbes (1/2)

Croisements – Graphes

Croisements – k-sécantes (2/2)

 

Sommaire de cette page

>>> Graphe à quatre sommets – K4 – Approche

>>> Graphe à cinq sommets – K5

>>> Graphe à six sommets – K6

>>> Nombre de croisements – Formules

>>> Graphes bipartis – Kn,m

>>> Anglais

 

 

 

 

 

 

 

Nombre de CROISEMENTS des graphes

Graph Crossing numbers

 

En topologie et en théorie des graphes, on connait la théorie des nœuds. On connait aussi cette célèbre énigme des trois maisons à alimenter en eau, gaz et électricité sans croisement de réseaux. Problème généralisé sous le nom de la brique de Turan (Turan brick factory problem).

Ici, on s'intéresse aux graphes qui présentent des croisements inévitables. Pour un graphe donné, quelle est la quantité d'intersections inévitables (Anglais: graph crossing number).

 

 

Vocabulaire

Sommet ou nœuds du graphe (one vertex or vertice, several vertices).

Arêtes ou lien (edge).

 

 

 

Graphe à quatre sommets – K4 – Approche

 

Quatre points

Quatre points quelconques non alignés sont reliés entre eux.

Aucun croisement.

Les arêtes découpent le plan en quatre régions numérotées de 1 à 4.

 

Et si un cinquième point ?

Un cinquième point ferait partie d'une des quatre régions (T): triangle ou extérieur à un triangle (pseudo-triangle). À ce titre, il est facile de le relier aux trois sommets de T. Par contre, pour relier le quatrième sommet, le segment devra traverser une frontière de T en créant nécessairement un croisement.

 

NC(K4) = 0

 

 

Graphe à cinq sommets – K5

 

Avec cinq sommets disposés en pentagone ou en carré centré (le cinquième point à l'intérieur ou à l'extérieur du quadrilatère formé par les quatre autres), il est impossible de les relier tous entre eux sans créer une intersection, un croisement.

 

Le nombre de croisements minimum pour le graphe K5 est 1.

 

Définition: le nombre de croisements d'un graphe est la quantité minimale de croisements entre arêtes pour tous les dessins possibles du graphe dans le plan.

 

Un graphe planaire est un graphe dont le nombre de croisements est nul. Le nombre de croisements est alors une indication du degré d'éloignement du graphe planaire.

 

En imposant des arêtes droites, on définit le  nombre de croisements rectilignes

 

Type de problème: calculer le nombre de croisements d'un graphe est un problème compliqué. C'est un problème NP-Complet.

 

 

NC(K5) = 1 (en rouge)

 

Démonstration

Si le graphe est planaire, il représente un polyèdre auquel on peut appliquer la relation d'Euler: F + S = A + 2 => F + 5 = 10 + 2 => F = 7.

Ces 7 faces mettent en jeu au moins  7 x 3  = 21 arêtes. Chacune étant comptée deux fois, il y a au moins 10,5 arêtes dans le polyèdre. Or, notre vrai graphe n'en compte que 10. Incompatible. Le graphe K5 ne peut pas être planaire.

 

 

Graphe à six sommets – K6

 

Démonstration 1 – NC (6) = 3

Supposons que le graphe ne présente que deux croisements. Ceux-ci impliqueraient quatre sommets.

Comme K6 en a six, pour deux d'entre eux, il y a formation d'une configuration en V (ici, dessin du bas, en bleu et en vert).

Supposons que l'on retire un de ces deux sommets. Non seulement on retire un sommet, mais avec lui les deux croisements. Ce qui voudrait dire que le nouveau graphe K5 serait planaire. Or, on sait que K5 ne l'est pas.

Contradiction. K6 n'est pas planaire et comporte plus de deux croisements. La figure de droite montre qu'il est possible de dessiner le graphe avec trois croisements pas plus.

 

Démonstration 2

K6 complet => 6 sommets et 15 arêtes

Supposons deux croisements, en retirant deux arêtes, on obtient un graphe planaire: 6 sommets et 13 arêtes.

Or, dans un graphe planaire: 13  3 x 6 – 6 = 12, ce qui est faux. K6 a plus de deux croisements.

 

Graphe K6

NC(K6) = 3 (en rouge)

 

Deux croisements dans K6

 

 

Nombre de croisements – Formules

 

Graphe planaire

pour un graphe de n sommets et a arêtes

Voir Relation d'Euler et graphes planaires

 

a   3n – 6

 

Inégalité pour le nombre de croisements

pour un graphe de n sommets et a arêtes

 

Exemple

Avec 10 sommets, le graphe complet compte ½ 9 x 10 = 45 arêtes.

 

NC(n)  a – 3n

 

 

NC(6)  45 – 30 = 15

La valeur exacte est 60

Conjecture de Hill (1958, prouvée par Guy (1972) jusqu'à 10 et étendue à 12 par Pan et Richter (2007).

 

Elle concerne les graphes complets (tous les sommets sont reliés entre eux) à n sommets.

 

 

ou encore

 

Valeurs

 

Valeurs prouvées

 

Suite jusqu'à n = 25 (conjecture): 225, 315, 441, 588, 784, 1008, 1296, 1620, 2025, 2475, 3025, 3630, 4356 …

Par exemple: K(13) = {217, 219, 221, 223 ou 225}

 

 

 

Graphes bipartis – K(n,m)

 

Définitions

Un graphe biparti (n, m) représente la distribution de n points vers m points. Cas typique des réseaux de distribution. Il est complet si toutes les liaisons possibles sont réalisées.

En l'occurrence on cherche à minimiser les croisements.

 

Formule

La conjecture de Zarnkiewicz (1954), indique que:

 

Elle est vérifiée jusqu'à K(7,7) et au-delà elle surestime le nombre de croisements.

En 1993, Woodall prouve m  8 et m  10.

On connait aussi:

 

 

Valeurs (exemple K(4,3) = 2)

 

 

 

Graphe K(2, 2)

NC(K2,2) = 0

 

 

 

Graphe K(3, 3)

 

NC(K3,3) = 1

Démonstration pour K(3, 3) non planaire (Semblable à celle de K5)

Formule d'Euler pour le polyèdre représentatif: F + S = A + 2 => F + 6 = 9 + 2 => F = 5.

Chaque face n'est pas triangle, sinon il y aurait des arêtes entre points n ou points m.

Quantité minimale d'arêtes: 5 x 4  / 2 = 10. Impossible pour le graphe K(3, 3) qui n'a que 9 arêtes. Le graphe n'est pas planaire.

 

 

 

English corner

 

The crossing number of a graph is the least possible number of edge crossings of a plane drawing of the graph.

A crossing means a point that is not a vertex where edges meet.

The drawing of a graph is made so that no three edges cross at a single point.

The complete bipartite graph K(m,n) is the graph connecting a set of m vertices to a set of n vertices, with every eligible pair of vertices joined by an edge.

 

Le nombre de croisements d'un  graphe est la quantité minimale d'intersections d'arêtes sur le dessin d'un graphe.

Une intersection est un point de croisement des arêtes qui n'est pas un sommet.

Le dessin du graphe est réalisé de sorte que trois arêtes ne soient pas concourantes.

 

Un graphe biparti complet K(m, n) est le graphe reliant un jeu de m sommets à un jeu de n sommets tel que toute paire admissible de sommets forme une arête.

 

 

 

 

 

 

 

Suite

*    Problème du mariage heureux

*    TopologieIndex

Voir

*      Combinatoire Index

*      Le problème des quatre couleurs

Sites

*      What is the crossing number of K5

*      Graph crossing number – Wolfram MathWorld

*      Graph crossing number – Wikipédia

*      OEIS – A000241 – Crossing number of complete graph with n nodes.

*      Crossing number of a graph – Cut-The-Knot

*      Crossing numbers – Carl Joshua Quines – 2016

*    The Graph Crossing Number and its Variants: A Survey – Marcu Schaefer – 2017 – 113 pages – Toutes les sortes de crossing numbers

Cette page

http://villemin.gerard.free.fr/aMaths/Topologi/Crosnber.htm