Nulle part-zéro flux

En théorie des graphes , un flot nulle part nul ou flot NZ est un flot réseau nulle part nul. Il est intimement lié (par dualité) à la coloration des graphes planaires .

Soit G = ( V , E ) un digraphe et soit M un groupe abélien . Une application φ : E → M est une M -circulation si pour tout sommet v ∈ V

où δ ⁺ ( v ) désigne l'ensemble des arêtes sortant de v et δ ⁻ ( v ) désigne l'ensemble des arêtes entrant dans v . Cette condition est parfois appelée loi de Kirchhoff .

Si φ ( e ) ≠ 0 pour tout e ∈ E , on appelle φ un flux nulle part, un flux M ou un flux NZ. Si k est un entier et 0 < | φ ( e )| < k alors φ est un flux k .

Soit G = ( V , E ) un graphe non orienté . Une orientation de E est un k - flot modulaire si pour tout sommet v ∈ V on a :

• L'ensemble des M -flux ne forme pas nécessairement un groupe car la somme de deux flux sur un bord peut être égale à 0.

• (Tutte 1950) Un graphe G possède un M -flux si et seulement s'il possède un | M |-flux. Par conséquent, un flot existe si et seulement si un k -flux existe. Par conséquent, si G admet un k -flux alors il admet un h -flux où .

• Indépendance de l'orientation. Modifiez un flot nul φ sur un graphe G en choisissant une arête e , en l'inversant, puis en remplaçant φ ( e ) par − φ ( e ). Après cet ajustement, φ est toujours un flot nul. De plus, si φ était à l'origine un k -flot, alors le φ résultant est aussi un k -flot. Ainsi, l'existence d'un M -flot nul ou d'un k -flot nul est indépendante de l'orientation du graphe. Ainsi, un graphe non orienté G est dit avoir un M -flot nul ou un k -flot nul si une orientation (et donc chaque) de G a un tel flot.

Soit le nombre de M -flux sur G . Il satisfait la formule de suppression–contraction :

En combinant cela avec l'induction, nous pouvons montrer qu'il s'agit d'un polynôme dans où est l' ordre du groupe M. Nous appelons le polynôme de flux de G et du groupe abélien M.

Ce qui précède implique que deux groupes d'ordre égal ont un nombre égal de flux NZ. L'ordre est le seul paramètre de groupe qui compte, pas la structure de M. En particulier si

Les résultats ci-dessus ont été prouvés par Tutte en 1953 alors qu'il étudiait le polynôme de Tutte , une généralisation du polynôme de flux.

Il existe une dualité entre les colorations à k faces et les k flots pour les graphes planaires sans pont . Pour voir cela, soit G un graphe planaire sans pont orienté avec une coloration à k faces appropriée avec des couleurs Construire une carte

par la règle suivante : si l'arête e a une face de couleur x à gauche et une face de couleur y à droite, alors soit φ ( e ) = x – y . Alors φ est un (NZ) k -flux puisque x et y doivent être de couleurs différentes.

Donc si G et G* sont des graphes duaux planaires et que G* est k -colorable (il y a une coloration des faces de G ), alors G possède un k -flux NZ . En utilisant l'induction sur | E ( G )| Tutte a prouvé que la réciproque est également vraie. Ceci peut être exprimé de manière concise comme :

où le RHS est le nombre de flux , le plus petit k pour lequel G autorise un k -flux.

La dualité est également vraie pour les flux M généraux :

• Soit la fonction de coloration du visage avec des valeurs dans M .

• Définissez où r ₁ est la face à gauche de e et r ₂ est à droite.

• Pour toute M -circulation il existe une fonction de coloration c telle que (démontré par récurrence).

• c est un | E ( G )|-coloration de face si et seulement si est un flux NZ M (simple).

La dualité résulte de la combinaison des deux derniers points. Nous pouvons nous spécialiser pour obtenir les résultats similaires pour les k -flux discutés ci-dessus. Étant donné cette dualité entre les flux NZ et les colorations, et puisque nous pouvons définir des flux NZ pour des graphes arbitraires (pas seulement planaires), nous pouvons l'utiliser pour étendre les colorations de faces aux graphes non planaires.

• G est colorable sur 2 faces si et seulement si chaque sommet a un degré pair (considérez les 2-flux NZ).

• Soit le groupe de Klein-4 . Alors un graphe cubique a un K -flux si et seulement s'il est colorable sur 3 arêtes . En corollaire, un graphe cubique colorable sur 3 arêtes est colorable sur 4 faces.

• Un graphe est colorable à 4 faces si et seulement s'il permet un 4-flux NZ (voir le théorème des quatre couleurs ). Le graphe de Petersen n'a pas de 4-flux NZ, ce qui a conduit à la conjecture du 4-flux (voir ci-dessous).

• Si G est une triangulation alors G est colorable en 3-(sommets) si et seulement si chaque sommet a un degré pair. D'après la première puce, le graphe dual G * est 2-colorable et donc bipartite et cubique planaire. Donc G * a un 3-flux NZ et est donc colorable en 3-faces, ce qui rend G colorable en 3-sommets.

• De même qu'aucun graphe avec une arête de boucle n'a de coloration de sommet appropriée, aucun graphe avec un pont ne peut avoir un flux NZ M pour aucun groupe M . Inversement, tout graphe sans pont a un flux NZ (une forme du théorème de Robbins ).

Des questions intéressantes se posent lorsqu'on essaie de trouver des flux k nulle part pour de petites valeurs de k . Les éléments suivants ont été prouvés :

Théorème de Jaeger sur les flux à 4 arêtes. Chaque graphe connexe à 4 arêtes possède un flux à 4 arêtes.

Théorème de Seymour à 6 flux. Chaque graphe sans pont a un 6-flux.

En 2019, les problèmes suivants n'ont pas encore été résolus (à cause de Tutte ) :

Conjecture du flux triple. Tout graphe connexe à 4 arêtes possède un flux triple nulle part.

Conjecture du flux à 4. Tout graphe sans pont qui n'a pas le graphe de Petersen comme mineur a un flux à 4 nulle part nul.

Conjecture du flux 5. Tout graphe sans pont a un flux 5 nulle part nul.

La réciproque de la conjecture du 4-flux n'est pas valable puisque le graphe complet K ₁₁ contient un graphe de Petersen et un 4-flux. Pour les graphes cubiques sans pont et sans mineur de Petersen, les 4-flux existent par le théorème de snark (Seymour, et al 1998, pas encore publié). Le théorème des quatre couleurs est équivalent à l'affirmation selon laquelle aucun snark n'est planaire.