Nicăieri flux zero

Un flux nicăieri zero în teoria grafurilor  este un tip special de flux de rețea care este legat (prin dualitate) de colorarea grafurilor plane .

Definiție

Fie G = (V,E)  un grafic direcționat și fie M  un grup abelian . O mapare φ: E → M se numește flux sau M - flux dacă pentru orice vârf v ∈ V ,

unde δ + (v) denotă setul de muchii care ies din v , iar δ - (v)  este setul de muchii care intră în v . Uneori, această afecțiune este tratată ca regula lui Kirchhoff . Dacă φ(e) ≠ 0 pentru orice vârf e ∈ E , vorbim despre φ ca un flux nicăieri-zero . Dacă M = Z  este grupul de numere întregi prin adunare și k  este un număr pozitiv astfel încât - k < φ(e) < k pentru orice muchie e , atunci M -flow φ se mai numește și k -flow .

Fie G = (V,E)  un grafic nedirecționat. O orientare a arcelor în E se numește k - flux modular dacă

pentru toate vârfurile v ∈ V .

Proprietăți

Schimbați fluxul φ nicăieri zero pe graficul G alegând un arc e , schimbând direcția arcului și înlocuind φ(e) cu -φ(e) . După astfel de modificări, fluxul nu va rămâne nicăieri zero. În plus, dacă φ a fost inițial un k -flux, atunci fluxul rezultat va rămâne așa. Astfel, existența unui flux M sau k -flux nu nicaieri nu depinde de direcțiile arcelor graficului. Putem spune că un graf nedirecționat G are un flux M diferit de zero sau un flux k dacă vreo orientare (și, prin urmare, orice) a arcelor lui G are un astfel de flux.

Și mai surprinzător este că dacă M este un grup abelian finit de mărime k , atunci numărul de fluxuri M nicăieri zero pe unele grafice nu depinde de structura lui M , ci doar de k , dimensiunea lui M . Mai mult, existența unui M -flux coincide cu existența unui k -flux. Aceste două rezultate au fost dovedite de Tatt în 1953 [1] .

Dualitate de fluxuri și colorații

Fie G = (V,E)  un grafic dirijat fără punți desenate pe plan și să presupunem că regiunile (fețele) sunt colorate corect cu k culori {0, 1, 2, .., k  - 1}. Să construim o mapare φ: E(G) → {-( k  - 1), …, −1, 0, 1, …, k  - 1} după următoarea regulă: dacă arcul e are culoarea x pe stânga și colorați y în dreapta, setăm φ (e) = x  - y . Este ușor de verificat că φ este un k -flux. Mai mult, dacă regiunile sunt colorate corect, φ nu este nicăieri zero k -flow. Acest lucru rezultă din construcție, deoarece dacă G și G* sunt grafice duale plane și G*  este k -colorabil, atunci G are un k -flux nul nicăieri . Tutt a dovedit că și inversul acestei afirmații este adevărat. Astfel, pentru graficele plane, fluxurile nicăieri-zero sunt duale cu colorarea. Deoarece fluxurile nicăieri zero au sens pentru graficele arbitrare (nu doar cele care pot fi desenate în plan), studiul lor poate fi văzut ca o extensie a teoriei colorării la graficele neplanare.

Teorie

Probleme nerezolvate în matematică : Un grafic arbitrar fără punți are un flux de 5 nicăieri zero? Are un graf arbitrar fără punți și fără grafuri Petersen ca minore un flux de 4 nicăieri zero?

Deoarece niciun grafic în buclă nu are o colorare obișnuită, niciun grafic cu punte nu poate avea un flux diferit de zero oriunde (în orice grup). Este ușor să arăți că orice grafic fără punte are un flux Z nicăieri zero (din teorema lui Robbins ), dar apare o întrebare interesantă atunci când încercăm să găsim un flux k nicăieri zero pentru valori mici ale lui k . Două teoreme elegante în această direcție sunt teorema lui Jaeger cu 4 fluxuri (orice graf conectat cu 4 muchii are un 4-flow zero zero) [2] și teorema lui Seymour cu 6 fluxuri (orice grafic fără punți are un 6-flow zero zero) [3] .

Tutt a presupus că orice graf fără punte are un flux de 5 nicăieri zero [4] și că orice graf fără punte care nu conține graful Petersen ca minor are un flux de 4 nicăieri zero [5] . Pentru graficele cubice care nu conțin minorul Petersen, existența unui flux 4 rezultă din teorema snark , dar pentru graficele arbitrare conjectura rămâne deschisă.

Vezi și

Note

  1. ↑ William Thomas Tutte. O contribuție la teoria polinoamelor cromatice. — 1953.
  2. ↑ F. Jaeger, Fluxuri și teoreme de colorare generalizate în grafice, J. Comb. set teorie. B, 26 (1979), 205-216.
  3. ↑ P.D. Seymour, Nowhere-zero 6-flows, J. Comb. Theory Ser B, 30 (1981), 130-135.
  4. ↑ 5-flow Conjecture Arhivat 8 februarie 2012 la Wayback Machine , Open Problem Garden.
  5. ↑ 4-flow Conjecture Arhivat 8 februarie 2012 la Wayback Machine , Open Problem Garden.

Link -uri