Hiçbir yerde sıfır akış - Nowhere-zero flow - Wikipedia

İçinde grafik teorisi, bir hiçbir yerde sıfır akış veya NZ akışı bir ağ akışı orası sıfır değil. (Dualite ile) yakından bağlantılıdır. boyama düzlemsel grafikler.

Tanımlar

İzin Vermek G = (V,E) olmak digraph ve izin ver M fasulye değişmeli grup. Bir harita φ: EM bir Mdolaşım her biri için tepe vV

nerede δ+(v) dışında kalan kenarları gösterir v ve δ(v) kenar kümesini gösterir v. Bazen bu durum şu şekilde anılır: Kirchhoff kanunu.

Eğer φ(e) ≠ 0 eE, Biz ararız φ a hiçbir yerde sıfır akış, bir M-akış, veya bir NZ akışı. Eğer k bir tamsayıdır ve 0 < |φ(e)| < k sonra φ bir k-akış.[1]

Diğer kavramlar

İzin Vermek G = (V,E) fasulye yönsüz grafik. Bir yönelim E bir modüler k-akış eğer her köşe içinv ∈ V sahibiz:

Özellikleri

  • Kümesi M- Bir kenardaki iki akışın toplamı 0'a eklenebileceğinden akışlar mutlaka bir grup oluşturmaz.
  • (Tutte 1950) Bir grafik G var M-akış ancak ve ancak bir |M| -akış. Sonuç olarak, bir akış, ancak ve ancak bir k-akış var.[1] Sonuç olarak G itiraf ediyor k-akış, sonra kabul eder hnereye akıyor .
  • Oryantasyon bağımsızlığı. Sıfır olmayan bir akışı değiştirin φ bir grafikte G bir kenar seçerek e, tersine çevirin ve sonra değiştirin φ(e) ile -φ(e). Bu ayarlamadan sonra, φ hala sıfır olmayan bir akış. Ayrıca, eğer φ başlangıçta bir k-akış, sonra ortaya çıkan φ aynı zamanda bir k-akış. Böylece hiçbir yerde sıfırın varlığı M-akış veya hiçbir yere sıfır k-akış, grafiğin yönünden bağımsızdır. Böylece yönsüz bir grafik G hiçbir yerde sıfır olduğu söylenir M-akış veya hiçbir yerde-sıfır k-bazı (ve dolayısıyla her) yönelim ise G böyle bir akışı var.

Akış polinomu

İzin Vermek sayısı olmak M-akar G. Tatmin eder silme-daraltma formülü:[1]

Bunu indüksiyonla birleştirerek gösterebiliriz bir polinomdur nerede ... sipariş Grubun M. Biz ararız akış polinomu nın-nin G ve değişmeli grup M.

Yukarıdakiler, eşit sıradaki iki grubun eşit sayıda NZ akışına sahip olduğu anlamına gelir. Sıra, önemli olan tek grup parametresidir, yapısı değil M. Özellikle Eğer

Yukarıdaki sonuçlar tarafından kanıtlandı Tutte 1953'te okurken Tutte polinomu akış polinomunun bir genellemesi.[2]

Akış renklendirme ikiliği

Köprüsüz Düzlemsel Grafikler

Arasında bir ikilik var k-yüz renklendirmeler ve k-için akışlar köprüsüz düzlemsel grafikler. Bunu görmek için izin ver G uygun bir yönlendirilmiş köprüsüz düzlemsel grafik olmak k- renklerle yüz boyama Bir harita oluşturun

aşağıdaki kurala göre: eğer kenar e yüzü renkli x solda ve renkli bir yüz y sağa, sonra bırak φ(e) = xy. Sonra φ bir (NZ) k-den beri akış x ve y farklı renkler olmalı.

Öyleyse G ve G * düzlemsel ikili grafikler ve G * dır-dir krenklendirilebilir (yüzlerin rengi vardır G), sonra G Yeni Zelanda var k-akış. İndüksiyon kullanma |E(G) | Tutte, sohbetin de doğru olduğunu kanıtladı. Bu kısaca şu şekilde ifade edilebilir:[1]

RHS nerede akış numarası, en küçük k hangisi için G izin verir k-akış.

Genel Grafikler

Dualite genel için doğrudur M-akışlar da:

  • İzin Vermek değerlerle yüz renklendirme işlevi M.
  • Tanımlamak nerede r1 solundaki yüz e ve r2 sağdadır.
  • Her biri için Mdolaşım bir renklendirme işlevi var c öyle ki (tümevarım ile kanıtlanmıştır).
  • c bir |E(G) | -yalnızca ve ancak Yeni Zelanda mı M-akış (basit).

Dualite, son iki noktayı birleştirerek izler. Uzmanlaşabiliriz benzer sonuçları elde etmek için k- yukarıda tartışılan akışlar. Yeni Zelanda akışları ve renklendirmeler arasındaki bu ikilik göz önüne alındığında ve rasgele grafikler (yalnızca düzlemsel değil) için Yeni Zelanda akışları tanımlayabildiğimiz için, bunu yüz renklendirmelerini düzlemsel olmayan grafiklere genişletmek için kullanabiliriz.[1]

Başvurular

  • G 2 yüzü renklendirilebilir ancak ve ancak her köşe eşit dereceye sahipse (NZ 2 akışlarını düşünün).[1]
  • İzin Vermek ol Klein-4 grubu. Sonra bir kübik grafik var K- eğer ve sadece 3- ise akışkenar renklendirilebilir. Sonuç olarak, 3 kenarlı renklendirilebilir kübik bir grafik 4 yüzlü renklendirilebilir.[1]
  • Bir grafik, ancak ve ancak NZ 4 akışına izin veriyorsa 4 yüzü renklendirilebilir (bkz. Dört renk teoremi ). Petersen grafiği NZ 4 akışına sahip değildir ve bu 4 akış varsayımına yol açmıştır (aşağıya bakınız).
  • Eğer G o zaman bir nirengi G 3- (köşe) renklendirilebilir ancak ve ancak her köşe eşit dereceye sahipse. İlk madde işaretiyle, ikili grafik G* 2 renklidir ve dolayısıyla iki parçalı ve düzlemsel kübik. Yani G* NZ 3 akışına sahiptir ve bu nedenle 3 yüzü renklendirilebilir, G 3-köşe renklendirilebilir.[1]
  • Tıpkı bir grafiğin olmaması gibi döngü kenar uygun bir köşe rengine sahiptir, köprü Yeni Zelanda olabilir Mherhangi bir grup için akış M. Tersine, her köprüsüz grafik Yeni Zelanda var -akış (bir tür Robbins teoremi ).[3]

Varoluş kakışlar

Soru, Web Fundamentals.svgMatematikte çözülmemiş problem:
Her köprüsüz grafiğin hiçbir yerde sıfır 5-akışı var mı? Bir minör olarak Petersen grafiğine sahip olmayan her köprüsüz grafiğin hiçbir yerde sıfır 4-akışı var mı?
(matematikte daha fazla çözülmemiş problem)

Hiçbir yerde sıfır bulmaya çalışırken ilginç sorular ortaya çıkıyor kküçük değerler için akışlar k. Aşağıdakiler kanıtlanmıştır:

Jaeger'in 4-akış Teoremi. Her 4-kenara bağlı grafik 4 akışlıdır.[4]
Seymour 6-akış Teoremi. Her köprüsüz grafiğin 6-akışı vardır.[5]

3 akışlı, 4 akışlı ve 5 akışlı varsayımlar

2019 itibariyle, aşağıdakiler şu anda çözülmemiştir (nedeniyle Tutte ):

3-akışlı Varsayım. Her 4 kenara bağlı grafiğin hiçbir yerde sıfır olmayan 3 akışı vardır.[6]
4-akışlı Varsayım. Sahip olmayan her köprüsüz grafik Petersen grafiği olarak minör hiçbir yere sıfır 4 akışa sahiptir.[7]
5-akış Varsayımı. Her köprüsüz grafiğin hiçbir yerde sıfır 5 akışı vardır.[8]

4 akışlı Varsayımın tersi, tam grafik K11 Petersen grafiği içerir ve 4 akışlı.[1] Köprüsüz için kübik grafikler Petersen minör olmadan, 4-akış snark teoremi (Seymour, et al 1998, henüz yayınlanmadı). dört renk teoremi hiçbir kıvrımın düzlemsel olmadığı ifadesine eşdeğerdir.[1]

Ayrıca bakınız

Referanslar

  1. ^ a b c d e f g h ben j Diestel, Reinhard, 1959 - Verfasser. (30 Haziran 2017). Grafik teorisi. ISBN  9783662536216. OCLC  1048203362.CS1 bakimi: birden çok ad: yazarlar listesi (bağlantı)
  2. ^ Tutte, William Thomas (1953). "Kromatik polinom teorisine bir katkı". Alıntı dergisi gerektirir | günlük = (Yardım)
  3. ^ Numaralandırmada daha güçlü bir sonuç için - yine Robbins teoremini tamamen çevrimsel oryantasyonlarda kullanarak kenar başına maksimum akış miktarına bağlı akışlar, bakınız Teorem 2 Kochol, Martin (2002), "Hiçbir yerde sıfır olmayan akışlarla ilişkili polinomlar", Kombinatoryal Teori Dergisi, B Serisi, 84 (2): 260–269, doi:10.1006 / jctb.2001.2081, BAY  1889258
  4. ^ F. Jaeger, Akışlar ve grafiklerde genelleştirilmiş renklendirme teoremleri, J. Comb. Teori Seti. B, 26 (1979), 205–216.
  5. ^ P. D. Seymour, Nohere-zero 6-flows, J. Comb. Teori Ser B, 30 (1981), 130–135.
  6. ^ [1], Açık Problem Bahçesi.
  7. ^ [2], Açık Problem Bahçesi.
  8. ^ [3], Açık Problem Bahçesi.

daha fazla okuma